剑指Offer：最小的K个数
题目输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
思路1 + 代码维护一个最小堆，该最小堆即为所求。
类似题目
1234567891011121314import java.util.*;public class Solution { public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) { if(input==null || input.length==0 || k>input.length) return new ArrayList<Integer>(); PriorityQueue<Integer> pq = new PriorityQueue<Integer>((o1, o2) -> o2-o1); for(int num:input){ ...
剑指Offer：字符串的排列
题目输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述：
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
思路 + 代码典型回溯法，同 全排列 解法类似。
123456789101112131415161718192021222324252627import java.util.ArrayList;public class Solution { public ArrayList<String> Permutation(String str) { ArrayList<String> res = new ArrayList<String>(); backtracking(res, str.toCharArray(), new StringBuilder(), new boolean[str.length()]); return res; ...
Leetcode 46.全排列
题目给定一个没有重复数字的序列，返回其所有可能的全排列。
示例：12345678910输入: [1,2,3]输出:[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
思路 + 代码回溯问题。
如果遇到一个问题，不用穷举所有情况找不出答案，就采用回溯。
回溯是DFS的一种，遍历完一条路径后，回退一步，继续寻找下一可能路径。
它与暴力法的区别在于，可以通过剪枝规避掉很多无意义的尝试，且不用每次都从头开始遍历到尾部。
讲解可以参考https://www.cis.upenn.edu/~matuszek/cit594-2012/Pages/backtracking.html
12345678910111213141516171819202122232425262728class Solution { public List<List<Integer>> permute(int[] nums) { List<List<Integer>> r ...
剑指Offer：二叉搜索树与双向链表
题目输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
思路 + 代码二叉搜索树的中序遍历即为一个排序的顺序，按照该顺序依次构建双向链表即可。
123456789101112131415161718192021222324252627282930313233343536/**public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; }}*/public class Solution { private TreeNode firstHead = null; private TreeNode preHead = null; public TreeNode Convert(TreeNode pRootOfTree) { ...
剑指Offer：复杂链表的复制
题目输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
思路 + 代码参考 https://github.com/CyC2018/CS-Notes/blob/master/notes/%E5%89%91%E6%8C%87%20Offer%20%E9%A2%98%E8%A7%A3%20-%2030~39.md#35-%E5%A4%8D%E6%9D%82%E9%93%BE%E8%A1%A8%E7%9A%84%E5%A4%8D%E5%88%B6
分为三步：
1. 在每个节点的后面插入复制的节点。
2. 每个复制的节点 random 赋值。
3. 拆分。
12345678910111213141516171819202122232425262728293031323334353637383940414243/*public class RandomListNode { int label; RandomL ...
剑指Offer：二叉树和为某一值的路径
题目输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)
思路 + 代码递归求解，左右子树分别遍历（深度优先）。
遍历终止条件为节点为null或者是叶子节点且和为目标值。
否则回退列表，寻找更短的路径。
1234567891011121314151617181920212223242526272829303132333435import java.util.ArrayList;/**public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; }}*/public class Solution { private ArrayList<ArrayLis ...
剑指Offer：二叉搜索树的后序遍历序列
题目输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
思路 + 代码二叉搜索树的左子树所有节点小于根节点，右子树的所有节点大于根节点。
后序遍历是先访问左子树，后访问右子树。
因此，根节点永远在序列的最后位置。找到根节点数值后，根据前面节点数值与根节点的大小关系，找到左右子树的分割位置，递归求解。
123456789101112131415161718192021222324252627public class Solution { public boolean VerifySquenceOfBST(int [] sequence) { // 初始条件判断 if(sequence==null || sequence.length==0) return false; // 调用重写的辅助函数 return VerifySquenceOfBST(sequence, 0, sequence.lengt ...
剑指Offer：从上往下打印二叉树
题目从上往下打印出二叉树的每个节点，同层节点从左至右打印。
思路 + 代码二叉树的层次遍历，用队列保存同一层次的树节点，然后依次遍历。
类似题目http://sunyunzeng.com/Leetcode-102-%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E6%AC%A1%E9%81%8D%E5%8E%86/
1234567891011121314151617181920212223242526272829303132333435import java.util.*;/**public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; }}*/public class Solution { public ArrayList<Integer> P ...
剑指Offer：矩阵中的路径
题目请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如 a b c e s f c s a d e e 矩阵中包含一条字符串”bcced”的路径，但是矩阵中不包含”abcb”路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
思路 + 代码没有接触过类似的题型，因此看了讲解。
题目给出的是待查询的矩阵字符串与对应的行与列。
首先需要转化为矩阵。
然后利用回溯法，起始点依次选择矩阵中的每一个位置，上下左右进行遍历。
需要设置一个哨兵矩阵，记录已经访问的，防止重复访问产生无限循环。思想跟http://sunyunzeng.com/Leetcode-%E5%B2%9B%E5%B1%BF%E6%9C%80%E5%A4%A7%E7%9A%84%E9%9D%A2%E7%A7%AF/类似。
判定成功条件：回溯的路径长度与查询路径长度一致。
1234567891011121314 ...
设计模式：Java枚举类与注解
枚举类替代整形常量枚举类的基本形式如下：12public enum Apple { FUJI, PIPPIN, GRANNY_SMITH }public enum Orange { NAVEL, TEMPLE, BLOOD }
enum关键字指明一个类继承 abstractEnum。
该类有两个重要的方法：
ordinal(). 返回整形序列值（从0开始）
1234567public enum Season{ SPRING, SUMMER, FALL, WINTER}System.out.println(Season.SPRING.ordinal())// 打印 0
Enum(). 只能被继承Enum的类调用的构造方法，枚举类中每个实例调用该方法实现赋值，每个实例的构造方法都是私有的。
1234protected Enum(String name, int ordinal) { this.name = name; this.ordinal = ordinal; } ...
