九章算法_九章算法(杭州)科技有限公司

 1  public class BSTIterator {
 2     //@param root: The root of binary tree.
 3     TreeNode next = null;
 4     Stack<TreeNode> stack = new Stack<TreeNode>();
 5     public BSTIterator(TreeNode root) {
 6         // write your code here
 7         next = root;
 8     }
 9 
10     //@return: True if there has next node, or false
11     public boolean hasNext() {
12         // write your code here
13         while(next != null) {
14             stack.push(next);
15             next = next.left;
16         }
17         if(stack.isEmpty()) return false;
18         return true;
19     }
20     
21     //@return: return next node
22     public TreeNode next() {
23         // write your code here
24         if(!hasNext()) return null;
25         TreeNode cur = stack.pop();
26         if(cur.right == null) next = null;
27         else next = cur.right;
28         return cur;
29     }
30 }

 1 //可以定义一个 ArrayList<Integer> result的成员变量，这样helper中就不需要resul作为参数一直传递添加了。
 2   public ArrayList<Integer> searchRange(TreeNode root, int k1, int k2) {
 3      ArrayList<Integer> result = new ArrayList<Integer> ();
 4      helper(root, result, k1, k2);
 5      return result;
 6  }
 7  private void helper(TreeNode root, ArrayList<Integer>  result, int k1, int k2) {
 8      if(root == null) return;
 9      helper(root.left, result, k1, k2);
10      if(root.val >= k1 && root.val <= k2) result.add(root.val);
11      helper(root.right, result, k1, k2);
12      return;
13  }

 1  public TreeNode insertNode(TreeNode root, TreeNode node) {
 2         // write your code here
 3         if(root == null) {
 4             root = node;
 5             return root;
 6         }
 7         if(root.val <= node.val) {
 8             root.right = insertNode(root.right, node);
 9             
10         } else {
11             root.left = insertNode(root.left, node);
12         }
13         return root;
14     }
15 //非递归
16  public TreeNode insertNode(TreeNode root, TreeNode node) {
17         // write your code here
18         if(root == null) {
19             root = node;
20             return root;
21         }
22         TreeNode last = null, temp = root;
23         while(temp != null) {
24             last = temp;
25             if(temp.val <= node.val) temp = temp.right;
26             else temp = temp.left;
27         }
28         if(last != null) { //可以不判断，last不可能为null
29             if(last.val <= node.val) last.right = node;
30             else last.left = node;
31         }
32         return root;
33     }
34     

 1 public TreeNode removeNode(TreeNode root, int value) {  2 TreeNode dummy = new TreeNode(0); //dummy的值随便取，反正不输出，为了仅仅是给root设个头  3 dummy.left = root;  4  5 TreeNode parent = findNode(dummy, root, value);  6 TreeNode node; //待删结点  7 if (parent.left != null && parent.left.val == value) {  8 node = parent.left;  9 } else if (parent.right != null && parent.right.val == value) { 10 node = parent.right; 11 } else { 12 return dummy.left ; //待删结点不存在 13  } 14 15  deleteNode(parent, node); 16 17 return dummy.left ; 18  } 19 20 private TreeNode findNode(TreeNode parent, TreeNode node, int value) { //返回待删结点的父节点，待删的不存在也返回父节点 21 if (node == null) { 22 return parent; 23  } 24 25 if (node.val == value) { 26 return parent; 27  } 28 if (value < node.val) { 29 return findNode(node, node.left, value); 30 } else { 31 return findNode(node, node.right, value); 32  } 33  } 34 35 private void deleteNode(TreeNode parent, TreeNode node) { 36 if (node.right == null) { 37 if (parent.left == node) { 38 parent.left = node.left; 39 } else { 40 parent.right = node.left; 41  } 42 } else { 43 TreeNode temp = node.right; 44 TreeNode father = node; 45 46 while (temp.left != null) { 47 father = temp; 48 temp = temp.left; 49  } 50 51 if (father.left == temp) { 52 father.left = temp.right; 53 } else { 54 father.right = temp.right; 55  } 56 57 if (parent.left == node) { 58 parent.left = temp; 59 } else { 60 parent.right = temp; 61  } 62 63 temp.left = node.left; 64 temp.right = node.right; 65  } 66 }

 1 //搜索记忆，查找过的结点不需要再查一次，所以复杂度为O(n * n)  2 int[][] triangle = null;  3 int[][] sumMin = null;  4 int n;  5 public int minimumTotal(int[][] triangle) {  6 if(triangle == null || triangle.length == 0 || triangle[0].length == 0) return 0;  7 this.n = triangle.length;  8 this.triangle = triangle;  9 this.sumMin = new int[n][n]; 10 for(int i = 0; i< n; i++) { 11 for(int j = 0; j < n ; j++) sumMin[i][j] = Math.MAX_VALUE; 12  } 13 14 return helper(0, 0); 15 } 16 private int helper(int x, int y) { 17 if(x >= n) return 0; 18 if(sumMin[x][y] != Math.MAX_VALUE) return sumMin[x][y]; 19 sumMin[x][y] = Math.min(helper(x+1, y),helper(x+1,y+1)) + triangle[x][y]; 20 return sumMin[x][y]; 21 } 22 // 同上，用哈希表存查过的结点 23 int[][] triangle = null; 24 HashMap<int[], Integer> sumMin = new HashMap<int[], Integer>(); 25 int n; 26 public int minimumTotal(int[][] triangle) { 27 if(triangle == null || triangle.length == 0 || triangle[0].length == 0) return 0; 28 this.n = triangle.length; 29 this.triangle = triangle; 30 for(int i = 0; i< n; i++) { 31 for(int j = 0; j < n ; j++) sumMin[i][j] = Math.MAX_VALUE; 32  } 33 34 return helper(0, 0); 35 } 36 private int helper(int x, int y) { 37 if(x >= n) return 0; 38 if(sumMin.containsKey({x,y})) return sumMin.get({x,y}); 39 int value = Math.min(helper(x+1, y),helper(x+1,y+1)) + triangle[x][y]; 40  sumMin.put({x,y}, value); 41 return value; 42 } 43 //top - down 44 public int minimumTotal(int[][] triangle) { 45 if(triangle == null || triangle.length == 0 || triangle[0].length == 0) return 0; 46 int row = triangle.length; 47 for(int i =1; i < row; i++) { 48 triangle[i][0] += triangle[i-1][0]; 49 triangle[i][i] += triangle[i-1][i-1]; 50  } 51 for(int i = 2; i < row; i++) { 52 for(int j =1; j < i; j++) { 53 triangle[i][j] += Math.min(triangle[i-1][j],triangle[i-1][j-1]); 54  } 55  } 56 for(int i = 1; i < row; i++) { 57 triangle[row-1][0] = Math.min(triangle[row-1][i],triangle[row-1][0]); 58  } 59 return triangle[row-1][0]; 60 } 61 //down - top 62 public int minimumTotal(int[][] triangle) { 63 if(triangle == null || triangle.length == 0 || triangle[0].length == 0) return 0; 64 int row = triangle.length; 65 for(int i= row -2; i >=0; i--) { 66 for(int j=0; j<= i; j++) 67 triangle[i][j] += Math.min(triangle[i+1][j], triangle[i+1][j+1]); 68  } 69 return triangle[0][0]; 70 }

 1 public int climbStairs(int n) {  2 if(n == 0) return 1;  3 a = 1;  4 b = 1;  5 for(int i = 2; i <= n; i++) {  6 int c = a+ b;  7 c= b;  8 a = b;  9  } 10 return c; 11  } 12 //--------------------- 13 public int climbStairs(int n) { 14 int[] f = new int[n+1]; 15 if(n == 0) return 1; 16 f[0] = 1; 17 f[1] = 1; 18 for(int i = 2; i <= n; i++) { 19 f[i] = f[i - 1] + f[i - 2]; 20  } 21 return f[n]; 22 }

 1 // 递归调用会超时,因为有重复计算的过程  2 public int climbStairs(int n) {  3 if(n == 0) return 1;  4 if(n == 1) return 1;  5 return climbStairs(n-2)+climbStairs(n-1);  6  }  7 // 加入记忆化搜索,还超时  8 int[] result = null;  9 public int climbStairs(int n) { 10 result = new int[n]; 11 Arrays.fill(result, -1); 12 if(n == 0) return 1; 13 if(n == 1) return 1; 14 result[0] = 1, result[1] = 1; 15 return helper(n); 16  } 17 private int helper(n) { 18 if(result[n] != -1) return result[n]; 19 return helper(n-1) + helper(n-2); 20  } 21 // 22 public int climbStairs(int n) { 23 if(n <=1) return 1; 24 int last = 1, last_last = 1; 25 int now = 0; 26 for(int i=1 ; i< n;i++) { 27 now = last + last_last; 28 last_last = last; 29 last = now; 30  } 31 return now; 32 }

 1 // me  2 public boolean canJump(int[] A) {  3 // wirte your code here  4 if(A == null || A.length == 0) return false;  5 int n = A.length;  6 int pos =0;  7 while(pos <= n -1) {  8 if(A[pos] >= n - 1 - pos) return true;  9 else { 10 int temp = pos + A[pos]; 11 while(A[temp] == 0) { 12 temp--; 13 if(temp <= pos) return false; 14  } 15 pos = temp; 16  } 17  } 18 return false; 19  } 20 // greedy 21 public boolean canJump(int[] A) { 22 if(A == null || A.length == 0) return false; 23 int farthest = A[0]; 24 for(int i = 1; i< A.length; i++) { 25 if(farthest >= i && farthest < i+ A[i]) { 26 farthest = i + A[i]; 27  } 28  } 29 return farthest>= A.length - 1; 30 } 31 //dp 32 public boolean canJump(int[] A) { 33 if(A == null || A.length == 0) return false; 34 boolean[] can = new boolean[A.length]; 35 can[0] = true; 36 for(int i = 1; i < A.length; i++) { 37 for(int j = 0; j < i; j++) { 38 if(can[j] && A[j] + j >= i) { 39 can[i] = true; 40 break; 41  } 42  } 43  } 44 return can[A.length - 1]; 45 }

 1 public int jump(int[] A) {  2 // state  3 int[] steps = new int[A.length];  4  5 // initialize  6 steps[0] = 0;  7 for (int i = 1; i < A.length; i++) {  8 steps[i] = Integer.MAX_VALUE;  9  } 10 11 // function 12 for (int i = 1; i < A.length; i++) { 13 for (int j = 0; j < i; j++) { 14 if (steps[j] != Integer.MAX_VALUE && j + A[j] >= i) { 15 //steps[i] = Math.min(steps[i], steps[j] + 1); 16 steps[i] = steps[j] + 1; 17 break; //贪心 18  } 19  } 20  } 21 22 // answer 23 return steps[A.length - 1]; 24 }

 1 //dp  2 public int[] twoSum(int[] numbers, int target) {  3 // write your code here  4 HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();  5 for(int i = 0 ; i< numbers.length; i++) {  6 if(map.get(numbers[i]) != null) {  7 int[] result = {map.get(numbers[i]) + 1, i+1};  8 return result;  9  } 10 // if在前，put在后，一定要这样，先看有没有再放。 11 map.put(target - numbers[i], i); 12  } 13 int[] result = {}; 14 return result; 15  } 16 //--------------------------- 17 public int[] twoSum(int[] numbers, int target) { 18 // write your code here 19 if(numbers == null || numbers.length <= 1) return null; 20 for(int i = 0; i< numbers.length - 1; i++) { 21 for(int j = i+1; j< numbers.length; j++) { 22 if(numbers[i] == target - numbers[j]) return new int[]{i + 1, j + 1}; 23  } 24  } 25 return null; 26 }

 1 public int longestIncreasingContinuousSubsequence(int[] A) {  2 if(A == null || A.length == 0) return 0;  3 int[] result = new int[A.length];  4 Arrays.fill(result, 1);  5 int max = 1;  6 for(int i = 1; i< A.length; i++) {  7 if(result[i -1] == 1) {  8 result[i] =2;  9 if(max < result[i]) max = result[i]; 10 continue; 11  } 12 if(A[i-2] < A[i -1] && A[i-1] < A[i] || 13 A[i-2] > A[i-1] && A[i-1] > A[i]) 14 result[i] = result[i- 1]+1; 15 else result[i] = 2; 16 if(max < result[i]) max = result[i]; 17  } 18 return max; 19 } 20 //------------------------------------------------------------ 21 public int longestIncreasingContinuousSubsequence(int[] A) { 22 if(A == null || A.length == 0) return 0; 23 int max = 1; 24 int length =1; 25 for(int i = 1; i < A.length; i++) { 26 if(A[i] > A[i-1]) length++; 27 else length=1; 28 max= Math.max(length, max); 29  } 30 for(int i = A.length -2; i >=0; i--) { 31 if(A[i+1] < A[i]) length++; 32 else length=1; 33 max= Math.max(length, max); 34  } 35 return max; 36 }

 1 public int longestConsecutive(int[] num) {  2 if(num == null || num.length == 0) return 0;  3 int[] sortArray = bucketSort(num);  4 int[] f= new int[sortArray.length];  5 f[0] = 1;  6 int maxLen = 1;  7 for(int i = 1; i < sortArray.length; i++) {  8 f[i] = 1;  9 if(sortArray[i] == sortArray[i -1] + 1) { 10 f[i] = f[i - 1] + 1; 11 } else if(sortArray[i] == sortArray[i -1]) f[i] = f[i - 1]; 12 if(maxLen < f[i]) maxLen = f[i]; 13  } 14 return maxLen; 15  } 16 private int[] bucketSort(int[] num) { 17 if(num == null || num.length == 0) return null; 18 int max = 0, min = 0; 19 for(int i : num) { 20 if(max <= i) max = i; 21 if(min >= i) min = i; 22  } 23 long[] bucket = new long[max - min + 1]; 24 for(int i : num) { 25 //如果min= 3， 4应该放在1的位置 26 bucket[i - min]++; 27  } 28 int[] result = new int[num.length]; 29 int i = 0; 30 for(int j = 0; j < bucket.length; j++) { 31 if(bucket[j] == 0) continue; 32 while(bucket[j] != 0) { 33 result[i] = j + min; 34 bucket[j] -= 1; 35 i++; 36  } 37  } 38 return result; 39 }

 1 public int longestConsecutive(int[] num) {  2 if(num == null || num.length == 0) return 0;  3 Set<Integer> set = new HashSet<Integer>();  4 for(int i : num) set.add(i);  5 int max = 0;  6 for(int i = 0; i< num.length; i++) {  7 int down = num[i];  8 while(set.contains(down)) {  9  set.remove(down); 10 down--; 11  } 12 int up = num[i] + 1; 13 while(set.contains(up)) { 14  set.remove(up); 15 up++; 16  } 17 max = Math.max(max, up-down - 1); 18  } 19 return max; 20 }

 1 public int longestConsecutive(int[] num) {  2 if(num == null || num.length == 0) return 0;  3 int max = 1;  4  Arrays.sort(num);  5 HashMap<Integer,Integer> map = new HashMap<Integer, Integer>();  6 for(int i = 0; i < num.length; i++) {  7 if(map.get(num[i]) != null) {  8 map.put(num[i] + 1, map.get(num[i]) + 1);  9 } else map.put(num[i] + 1, 1); 10 max = Math.max(max, map.get(num[i] + 1)); 11  } 12 return max; 13 } 14 //用set存放，while循环找顺序序列，而不需要提前排序 15 public int longestConsecutive(int[] num) { 16 if(num == null || num.length == 0) return 0; 17 HashSet<Integer> set = new HashSet<Integer>(); 18 for(int i = 0; i < num.length; i++) { 19  set.add(num[i]); 20  } 21 int max = 1; 22 for(int i=0;i< num.length; i++) { 23 int down = num[i] - 1; 24 while(set.contains(down)) { 25  set.remove(down); 26 down--; 27  } 28 int up = num[i] + 1; 29 while(set.contains(up)) { 30  set.remove(up); 31 up++; 32  } 33 max = Math.max(max, up - down -1); 34  } 35 return max; 36 }

 1 public int maxSubArray(int[] nums) {  2 //错误点： 没有考虑到 4，-1，2,1 这种情况，应该是6，目前结果时4.  3 if(nums == null || nums.length == 0) return 0;  4 int[] f = new int[nums.length];  5 int max = f[0] = nums[0];  6 for(int i = 1; i < nums.length; i++) {  7 if(nums[i] >= 0) {  8 if(f[i - 1] >=0) f[i] = f[i-1] + nums[i];  9 else f[i] = nums[i]; 10 } else { 11 if(f[i - 1] < nums[i]) f[i] = nums[i]; 12 else f[i] = nums[i]; 13 14  } 15 max = Math.max(max, f[i]); 16  } 17 return max; 18 } 19 public int maxSubArray(int[] nums) { 20 if(nums == null || nums.length == 0) return 0; 21 int max = nums[0], sum = 0; 22 for(int i = 0; i < nums.length; i++) { 23 sum +=nums[i]; 24 max = Math.max(sum, max); 25 sum = Math.max(sum, 0); 26  } 27 return max; 28 }

 1 public int maxSubArray(int[] nums) {  2 int max = Integer.MIN_VALUE, sum = 0;  3 if(nums == null || nums.length ==0) return 0;  4 for(int i =0; i < nums.length; i++) {  5 sum += nums[i];  6 max = Math.max(sum, max); //用max记录每次sum后现阶段遇到的最大sum和。  7 sum = Math.max(0, sum); //每次sum的和一定要大于0，否则之前sum的数字就不要了。  8  }  9 return max; 10  } 11 //--------------------------------------------------------------- 12 public int maxSubArray(int[] nums) { 13 int max = Integer.MIN_VALUE, sum = 0; 14 if(nums == null || nums.length ==0) return 0; 15 int[] partMax = new int[nums.length]; 16 int[] globalMax = new int[nums.length]; 17 partMax[0] = globalMax[0] = nums[0]; 18 19 for(int i = 1; i < nums.length; i++) { 20 partMax[i] = Math.max(partMax[i - 1] + nums[i], nums[i]); 21 globalMax = Math.max(partMax[i], globalMax[i-1]); 22  } 23 return globalMax[nums.length - 1]; 24 }

 1 private boolean[][] getInstance(String s) {  2 boolean[][] str = new boolean[s.length()][s.length()];  3 for(int i = 0; i < s.length(); i++) {  4 str[i][i] = true;  5  }  6 for(int i = 0; i < s.length() - 1; i++) {  7 str[i][i+1] = s.charAt(i) == s.charAt(i+1);  8  }  9 for(int len = 2;len <s.length(); len++) { 10 for(int i = 0; i + len < s.length(); i++) { 11 str[i][i+len] = str[i + 1][i+len -1] && s.charAt(i) == s.charAt(i+len); 12  } 13  } 14 return str; 15 } 16 public int minCut(String s) { 17 if(s==null || s.length() ==0) return 0; 18 boolean[][] str = getInstance(s); 19 int[] f = new int[s.length() + 1]; 20 for(int i = 0; i < f.length; i++) { 21 f[i] = i - 1; 22  } 23 for(int i= 1; i <= s.length(); i++) { 24 for(int j = 0; j < i; j++) { 25 if(str[j][i-1]) { 26 f[i]= Math.min(f[i], f[j] + 1); 27  } 28  } 29  } 30 return f[f.length -1]; 31 }

 1 for(int i = 0; i<f.length; i++) {  2 f[i] = i - 1; //i长度的字符串,最多分割i-1刀可以构成回文串，设为Integer.MAX_VALUE也行,关键是f[0]=-1,f[1]=0  3  }  4 for(int i = 1; i <= s.length(); i++) { //长度为i的字符串  5 for(int j = 0; j< i; j++) { //两个子串： 0~j-1, j~i-1，判断是否是回文串。  6 if(str[j][i-1]) {  7 f[i] = Math.min(f[i], f[j] + 1); //f[j]已经在之前求出来了,表示0~j-1这j个字符至少分几刀可以形成回文串  8  }  9  } 10 }

 1 private boolean isPalindrome(String s, int start, int end) {  2 for(int i = start, j = end; i < j; i++,j--) {  3 if(s.charAt(i) != s.charAt(j)) return false;  4  }  5 return true;  6 }  7 private boolean[][] getPalindromeInstance(String s) {  8 boolean[][] str = new boolean[s.length()][s.length()];  9 for(int i = 0; i<s.length(); i++) { 10 str[i][i] = true; 11  } 12 for(int i = 0; i<s.length() - 1; i++) { 13 str[i][i+1] = isPalindrome(s, i, i+1); 14  } 15 for(int len = 2; len < s.length(); len++) { //长度是len+1的子串 16 for(int i = 0; i + len < s.length(); i++) { //len+i代表尾角标位置 17 str[i][i+len] = isPalindrome(s, i + 1, i+len - 1) && s.charAt(i) == s.charAt(i+len); 18  } 19  } 20 return str; 21 } 22 public int minCut(String s) { 23 if(s==null || s.length() == 0) return 0; 24 boolean[][] str = getPalindromeInstance(s); 25 26 int[] f = new int[s.length() + 1]; 27 for(int i = 0; i < f.length; i++) { //长度为i的字符串最多分割i-1次就可以都是回文串，也可以将f[i]设为Integer.MAX_VALUE； 28 f[i] = i - 1; 29  } 30 for(int i = 1; i<= s.length(); i++) {//i个字符构成回文串 31 for(int j = 0; j < i; j++) { 32 if(str[j][i -1]) { 33 f[i] = Math.min(f[i],f[j] + 1); 34  } 35  } 36  } 37 return f[f.length - 1]; 38 }

 1 public boolean wordBreak(String s, Set<String> dict) {  2 if(s == null || s.length() == 0) return true;  3 if(dict == null ||dict.size() == 0) return false;  4 int wordLen = 0;  5 for(String s1 : dict) {  6 wordLen = Math.max(wordLen, s1.length());  7  }  8 boolean f[] = new boolean[s.length() + 1];  9 f[0] = true; 10 for(int i = 1; i <= s.length(); i++) { //i表示包含i个单词，j表示最后一个单词的长度 11 f[i] = false; 12 //0~i-1 0~i-j-1,i-j~i-1 13 for(int j=1;j<=wordLen && j<=i; j++) { 14 if(f[i-j]) { 15 if(dick.contains(s.subString(i-j, i-1))) { 16 f[i] = true; 17 break; 18  } 19  } 20  } 21  } 22 return f[f.length - 1]; 23 }

 1 public boolean wordBreak(String s, Set<String> dict) {  2 if(s == null || dict == null) return false;  3 if(dict.size() == 0) {  4 if(s.length() == 0 ) return true;  5 return false;  6  }  7 int maxLen = 0;  8 for(String s1 : dict) {  9 maxLen = Math.max(s1.length(), maxLen); 10  } 11 boolean[] canBreak = new boolean[s.length() + 1]; 12 canBreak[0] = true; 13 for(int i = 1; i <= s.length(); i++) { 14 canBreak[i] = false; 15 for(int lastWordLen = 1; lastWordLen <=i && lastWordLen <= maxLen; lastWordLen++) { 16 if(canBreak[i - lastWordLen]) { //最后一个单词的下标是 [i - lastWordLen, i) 左开右闭，包含的字符个数为lastWordLen 17 String word = s.substring(i - lastWordLen, i); 18 if(dict.contains(word)) { 19 canBreak[i] = true; 20 break; 21  } 22  } 23  } 24  } 25 return canBreak[s.length()]; 26 }

 1 public int longestCommonSubsequence(String A, String B) {  2 if(A == null || B == null || A.length() == 0 || B.length() == 0) {  3 return 0;  4  }  5 int m = A.length(), n = B.length();  6 int[][] f = new int[m+1][n+1];  7 for(int i = 1; i <=m; i++) {  8 f[i][0] = 0;  9  } 10 for(int i = 0; i <=n; i++) { 11 f[0][i] = 0; 12  } 13 for(int i = 1; i<=m; i++) { 14 for(int j =1; j<=n; j++) { 15 if(A.charAt(i-1) == B.charAt(j-1)) { 16 f[i][j] = f[i-1][j-1]+1; 17 } else { 18 f[i][j] = Math.max(f[i][j-1],f[i-1][j]); 19  } 20  } 21  } 22 return f[m][n]; 23 }

 1 public int longestCommonSubsequence(String A, String B) {  2 if(A == null || B == null || A.length() == 0 || B.length() == 0) return 0;  3 int[][] lcs = new int[A.length() + 1][B.length() + 1];  4 for(int i = 0; i <= A.length(); i++) {  5 lcs[i][0] = 0;  6  }  7 for(int j = 0; j <= B.length(); j++) {  8 lcs[0][j] = 0;  9  } 10 for(int i = 1; i <= A.length(); i++) { 11 for(int j = 1; j <= B.length(); j++) { 12 if(A.charAt(i-1) == B.charAt(j-1)) { 13 lcs[i][j] = Math.max(lcs[i - 1][j - 1]+1, Math.max(lcs[i - 1][j], lcs[i][j - 1])); //只写lcs[]][]+1即可，不用判断的 14 } else { 15 lcs[i][j] = Math.max(lcs[i - 1][j - 1]+0, Math.max(lcs[i - 1][j], lcs[i][j - 1])); 16  } 17  } 18  } 19 return lcs[A.length()][B.length()]; 20 }

 1 public int longestCommonSubstring(String A, String B) {  2 if(A == null || B == null || A.length() == 0 || B.length() == 0) return 0;  3 int max = 0;  4 for(int i = 0; i < A.length(); i++) {  5 for(int j= i + 1; j <= A.length(); j++) {  6 if(B.contains(A.substring(i,j))) max = Math.max(max, j- i);  7  }  8  }  9 return max; //O(n * n * n) 10  } 11 //---------------------------------------------------- 12 public int longestCommonSubstring(String A, String B) { 13 if(A == null || B == null || A.length() == 0 || B.length() == 0) return 0; 14 15 int[][] lcs = new int[A.length() + 1][B.length() + 1]; 16 for(int i = 1; i <= A.length(); i++) { 17 for(int j = 1; j <= B.length(); j++) { 18 if(A.charAt(i-1) == B.charAt(j-1)) { 19 lcs[i][j] = lcs[i - 1][j - 1]+1; 20 } else { 21 lcs[i][j] = 0; 22  } 23  } 24  } 25 26 int max = 0; 27 for(int i = 1; i <= A.length(); i++) { 28 for(int j = 1; j <= B.length(); j++) { 29 max = Math.max(max, lcs[i][j]); 30  } 31  } 32 return max; 33 }

 1 // 为什么要死记公式啊，先求lcs再去匹配一致，考虑并不周全 abc cab   2 public int minDistance(String word1, String word2) {  3 if(word1 == null || word2 == null) {  4 if(word1 != null) return word1.length();  5 if(word2 != null) return word2.length();  6 return 0;  7  }  8 int[][] lcs = new int[word1.length() + 1][word2.length() + 1];  9 for(int i = 1; i <= word1.length(); i++) { 10 for(int j = 1; j <= word2.length(); j++) { 11 if(word1.charAt(i-1) == word2.charAt(j-1)) { 12 lcs[i][j] = lcs[i - 1][j - 1]+1; 13 } else { 14 lcs[i][j] = 0; 15  } 16  } 17  } 18 int max = 0; 19 for(int i = 1; i <= word1.length(); i++) { 20 for(int j = 1; j <= word2.length(); j++) { 21 max = Math.max(max, lcs[i][j]); 22  } 23  } 24 return Math.max(word1.length()-max, word2.length() - max); 25 } 26 //---------------------- 27 public int minDistance(String word1, String word2) { 28 if(word1 == null || word2 == null) { 29 if(word1 != null) return word1.length(); 30 if(word2 != null) return word2.length(); 31 return 0; 32  } 33 int[][] f = new int[word1.length() + 1][word2.length() + 1]; 34 for(int i = 0; i <= word1.length(); i++) f[i][0] = i; 35 for(int j = 0; j <= word2.length(); j++) f[0][j] = j; 36 37 for(int i = 1; i <=word1.length(); i++) { 38 for(int j = 1; j <= word2.length(); j++) { 39 if(word1.charAt(i - 1) == word2.charAt(j - 1)) { 40 f[i][j] = Math.min(Math.min(f[i-1][j] + 1, f[i][j-1]+1),f[i- 1][j - 1]); 41 } else { 42 f[i][j] = Math.min(Math.min(f[i-1][j] + 1, f[i][j-1]+1),f[i- 1][j - 1] + 1); 43  } 44  } 45  } 46 return f[word1.length()][word2.length()]; 47 }

 1 链表的基本操作  2 1. Insert a Node in Sorted List  3 2. Remove a Node from Linked List  4 3. Reverse a Linked List  5 4. Merge Two Linked Lists  6 5. Middle of a Linked List  7  8 1. // 最简单的方法  9 private ListNode reverse(ListNode head) { 10 if(head == null || head.next == null) return head; 11 ListNode prev = null; 12 while(head!= null ) { 13 ListNode temp = head.next; 14 head.next = prev; 15 prev = head; 16 head = temp; 17  } 18 return prev; 19  } 20 //另一种写法 21 private ListNode reverse(ListNode head) { 22 if(head == null || head.next == null) return head; 23 ListNode tail = head; 24 ListNode next =tail.next; 25 while(next != null) { 26 ListNode temp = next.next; 27 next.next =tail; 28 tail = next; 29 next =temp; 30  } 31 head =tail; 32 tail.next = null; 33 return head; 34  } 35 4. private ListNode merge(ListNode left, ListNode right) { 36 ListNode dummy = new ListNode(0), tail = dummy; 37 while(left != null && right != null) { 38 tail.next = left; 39 left = left.next; 40 tail = tail.next; 41 tail.next = right; 42 right.next = right; 43 tail = tail.next; 44  } 45 if(left != null) tail.next = left; 46 else tail.next = right; 47 return dummy.next; 48 } 49 5. 快慢指针 50 private ListNode getMid(ListNode head) {} 51 //12345 要找到3 52 if(head == null || head.next == null) return head; 53 ListNode slow = head, fast = head; 54 while(fast.next != null && fast.next.next != null) { 55 slow = slow.next; 56 fast = fast.next.next; 57  } 58 return slow; 59 //查找倒数第n个结点 60 private ListNode find(ListNode head) { 61 ListNode slow = head, fast = head; 62 // 1 2 3 4 5 找4，倒数第2个，需要在fast走第二步的时候，slow开始走第一步 63 int i = 0; 64 while(fast.next != null) { 65 i++; 66 fast = fast.next; 67 if(i < 2) coutinue; 68 slow = slow.next; 69  } 70 return slow; 71 }

 1 //----------------运行超时  2 public static ListNode deleteDuplicates(ListNode head) {  3 // write your code here  4 if(head == null || head.next == null) return head;  5 ListNode prev = null;  6 ListNode curr = head;  7 Map<ListNode,Integer> map = new HashMap<ListNode,Integer>();  8 int value = 0;  9 while(curr != null) { 10 if(map.get(curr) != null) { 11 map.put(curr,map.get(curr) + 1); 12 } else { 13 map.put(curr,1); 14  } 15  } 16 prev.next = head; 17 curr = head; 18 ListNode currNext = curr.next; 19 while(currNext != null) { 20 if(map.get(currNext) != 1) { 21 curr = currNext; 22 currNext.next = currNext.next; 23  } 24  } 25 return prev.next; 26  } 27 //-------------------------------------------------- 28 public static ListNode deleteDuplicates(ListNode head) { 29 if(head == null || head.next == null) return head; 30 ListNode dummy = new ListNode(0); 31 dummy.next = head; 32 //只要不用next操作，引用再怎么换也不会影响链表。 33 head = dummy; 34 while(head.next != null && head.next.next != null) { 35 if(head.next.val == head.next.next.val) { 36 int val = head.next.val; 37 while(head.next != null && head.next.val == val) { 38 head.next = head.next.next; 39  } 40 } else { 41 head = head.next; 42  } 43  } 44 return dummy.next; 45 }

 1 public static ListNode deleteDuplicates(ListNode head) {  2 // write your code here  3 if(head == null || head.next == null) return head;  4 ListNode dummy = new ListNode(0);  5 dummy.next = head;  6 head = dummy;  7 while(head.next != null && head.next.next != null) {  8 if(head.next.val == head.next.next.val) {  9 head.next = head.next.next; 10 } else head = head.next; 11  } 12 return dummy.next; 13 } 

 1 public ListNode reverse(ListNode head) {  2 // write your code here  3 ListNode prev = null;  4 while(head != null) {  5 ListNode temp = head.next;  6 head.next = prev;  7 prev = head;  8 head = temp;  9  } 10 return prev; 11 }

 1 public ListNode reverseBetween(ListNode head, int m , int n) {  2 if(head == null || m >= n) return head;  3 ListNode dummy = new ListNode(0);  4 dummy.next = head;  5 head = dummy;  6 for (int i = 1; i < m; i++) {  7 if(head != null) head = head.next;  8 else return null;  9  } 10 ListNode mprev = head; 11 ListNode mNode = mprev.next; 12 ListNode nNode = mNode; 13 ListNode nPost = nNode.next; 14 for(int i = m; i < n;i++) { 15 if(nPost == null) return null; 16 ListNode temp = nPost.next; 17 nPost.next = nNode; 18 nNode = nPost; 19 nPost = temp; 20  } 21 mprev.next = nNode; 22 mNode.next = nPost; 23 return dummy.next; 24 25 }

 1 public ListNode partition(ListNode head, int x) {  2 if(head == null) return head;  3 ListNode leftDummy = new ListNode(0);  4 ListNode rightDummy = new ListNode(0);  5 ListNode left = leftDummy, right = rightDummy;  6 while(head != null) {  7 if(head.val < x) {  8 left.next = head;  9 left = head; 10 } else { 11 right.next = head; 12 right = head; 13  } 14 head = head.next; 15  } 16 right.next = null; 17 left.next = rightDummy.next; 18 return leftDummy.next; 19 }

 1 private ListNode findMid(ListNode head) {  2 ListNode slow = head, fast = head.next;  3 while(fast.next != null && fast.next.next != null) {  4 fast = fast.next.next;  5 slow = slow.next;  6  }  7 return slow;  8 // 12345 return 2;  9  } 10 private ListNode merge(ListNode head1, ListNode head2) { 11 //dummy是合并后主链表的头，tail是尾。head1或head2中每当有一个结点链入主链，那链入的那个结点就可以 12 //在原先的链表中删除了，同时把原先的链表的头往后移。因为主链中加入了一个结点，所以主链的tail后移一次。 13 ListNode dummy = new ListNode(0), tail = dummy; 14 while(head1 != null && head2 != null) { 15 if(head1.val < head2.val) { 16 tail.next = head1; 17 head1 = head1.next; 18 } else { 19 tail.next = head2; 20 head2 = head2.next; 21  } 22 tail = tail.next; 23  } 24 //head1或head2有一个都链入主链后，把另一个非空的原先链表在链到主链尾部 25 //（这时原先链表中的后面位置的结点并没有进行排序。） 26 //最后返回的结果只是将head1或者head2进行排序了。（head1为空，则代表它完成排序了） 27 //要保证最后都有序，则head1和head2必须先有序。 28 if(head1 != null) { 29 tail.next = head1; 30 } else { 31 tail.next = head2; 32  } 33 return dummy.next; 34  } 35 36 public ListNode sortList(ListNode head) { 37 if(head == null || head.next == null) return head; 38 ListNode mid = findMid(head); 39 ListNode right = sortList(mid.next); 40 mid.next = null; 41 ListNode left = sortList(head); 42 return merge(left, right); 43 }

 1 public void reorderList(ListNode head) {  2 if(head == null || head.next == null) return;  3 ListNode mid = getMid(head);  4 ListNode right = reverse(mid.next);  5 mid.next = null;  6 head = merge(head, right);  7  }  8  9 private ListNode getMid(ListNode head) {} 10 //12345 15243 要找到3 11 if(head == null || head.next == null) return head; 12 ListNode slow = head, fast = head; 13 while(fast.next != null && fast.next.next != null) { 14 slow = slow.next; 15 fast = fast.next.next; 16  } 17 return slow; 18 } 19 private ListNode reverse(ListNode head) { 20 if(head == null || head.next == null) return head; 21 22 ListNode prev = null; 23 while(head!= null ) { 24 ListNode temp = head.next; 25 head.next = prev; 26 prev = head; 27 head = temp; 28  } 29 return prev; 30 } 31 private ListNode merge(ListNode left, ListNode right) { 32 ListNode dummy = new ListNode(0), tail = dummy; 33 while(left != null && right != null) { 34 tail.next = left; 35 left = left.next; 36 tail = tail.next; 37 tail.next = right; 38 right = right.next; 39 tail = tail.next; 40  } 41 if(left != null) tail.next = left; 42 else tail.next = right; 43 return dummy.next; 44 }

 1 public ListNode detectCycle(ListNode head) {  2 if(head == null || head.next == null) return null;  3 ListNode slow1 = head, fast = head;  4 while(fast.next != null && fast.next.next != null) {  5 slow1= slow1.next;  6 fast = fast.next.next;  7 if(slow1 == fast) {  8 ListNode slow2 = head;  9 while(true) { 10 if(slow1 == slow2) return slow1; 11 slow2 = slow2.next; 12 slow1 = slow1.next; 13  } 14  } 15  } 16 return null; 17 }

 1 public ListNode rotateRight(ListNode head, int k) {  2 if(head == null || head.next == null || k == 0) return head;  3 int len = 0;  4 ListNode temp = head;  5 while( temp != null ) {  6 len++;  7 temp = temp.next;  8  }  9 k = k % len; 10 if(k == 0) return head; 11 ListNode tail= head; 12 int i = 1; 13 while( len - k != i) { 14 i++; 15 tail = tail.next; 16  } 17 ListNode newHead = tail.next, temp1 = newHead; 18 tail.next = null; 19 while(temp1.next != null) { 20 temp1 = temp1.next; 21  } 22 temp1.next = head; 23 return newHead; 24  } 25 //---------------------------------------------------- 26 private int getLength(ListNode head) { 27 int length = 0; 28 while (head != null) { 29 length ++; 30 head = head.next; 31  } 32 return length; 33  } 34 35 public ListNode rotateRight(ListNode head, int n) { 36 if (head == null) { 37 return null; 38  } 39 40 int length = getLength(head); 41 n = n % length; 42 43 ListNode dummy = new ListNode(0); 44 dummy.next = head; 45 head = dummy; 46 47 ListNode tail = dummy; 48 //寻找倒数第n个结点(类似快慢指针实现的) 49 for (int i = 0; i < n; i++) { 50 head = head.next; 51  } 52 while (head.next != null) { 53 tail = tail.next; 54 head = head.next; 55  } 56 57 head.next = dummy.next; 58 dummy.next = tail.next; 59 tail.next = null; 60 return dummy.next; 61 }

 1 //两两合并----------------------------------------------  2 public ListNode mergeKLists(List<ListNode> lists) {  3 if(lists == null || lists.size() == 0) return null;  4  5 while(lists.size() > 1) {  6 List<ListNode> newList = new ArrayList<ListNode>();  7 for(int i = 0; i + 1< lists.size() ; i+=2) {  8 ListNode dummy = new ListNode(0);  9 dummy.next = mergeTwo(lists.get(i), lists.get(i+1)); 10  newList.add(dummy.next); 11  } 12 if(lists.size() % 2 != 0) newList.add(lists.get(lists.size() - 1)); 13 lists = newList; 14  } 15 return lists.get(0); 16  } 17 18 private ListNode mergeTwo(ListNode node1, ListNode node2) { 19 ListNode dummy = new ListNode(0), tail = dummy; 20 while(node1 != null && node2 != null) { 21 if(node1.val < node2.val) { 22 tail.next = node1; 23 node1 = node1.next; 24 } else { 25 tail.next = node2; 26 node2 = node2.next; 27  } 28 tail = tail.next; 29  } 30 if(node1 != null) { 31 tail.next = node1; 32 } else { 33 tail.next = node2; 34  } 35 return dummy.next; 36  } 37 //分治------------------------------------------------- 38 public ListNode mergeKLists(List<ListNode> lists) { 39 if(lists == null || lists.size() == 0) return null; 40 return mergeHelper(lists, 0, lists.size() - 1); 41  } 42 private ListNode mergeHelper(List<ListNode> lists, int start , int end) { 43 if(start == end) return lists.get(start); 44 int mid = start + (end - start) / 2; 45 ListNode left = mergeHelper(lists, start, mid); 46 ListNode right = mergeHelper(lists, mid+1, end); 47 return mergeTwo(left, right); 48  } 49 50 private ListNode mergeTwo(ListNode node1, ListNode node2) { 51 ListNode dummy = new ListNode(0), tail = dummy; 52 while(node1 != null && node2 != null) { 53 if(node1.val < node2.val) { 54 tail.next = node1; 55 node1 = node1.next; 56 } else { 57 tail.next = node2; 58 node2 = node2.next; 59  } 60 tail = tail.next; 61  } 62 if(node1 != null) { 63 tail.next = node1; 64 } else { 65 tail.next = node2; 66  } 67 return dummy.next; 68 }

 1 public RandomListNode copyRandomList(RandomListNode head) {  2 if(head == null) return head;  3 head = insert(head);  4 RandomListNode dummy = new RandomListNode(0);  5 dummy.next = head;  6 while(head != null) {  7 if(head.random == null) {  8 head.next.random = null;  9 } else { 10 head.next.random = head.random.next; 11  } 12 head = head.next.next; 13  } 14 dummy.next = remove(dummy.next); 15 return dummy.next; 16 17  } 18 private RandomListNode insert(RandomListNode head) { 19 if(head == null) return head; 20 RandomListNode dummy = new RandomListNode(0); 21 dummy.next = head; 22 while(head != null) { 23 RandomListNode temp = new RandomListNode(head.label); 24 temp.next = head.next; 25 head.next = temp; 26 head = head.next.next; 27  } 28 return dummy.next; 29  } 30 private RandomListNode remove(RandomListNode head) { 31 RandomListNode dummy = new RandomListNode(0); 32 dummy.next = head.next; 33 while(head.next.next != null) { 34 RandomListNode temp = head.next.next; 35 head.next.next = head.next.next.next; 36 head = temp; 37  } 38 return dummy.next; 39 }

 1 public void mergeSortedArray(int[] A, int m, int[] B, int n) {  2 int index = m+n-1, i = m - 1, j = n - 1;  3 while(i >=0 && j >=0) {  4 if(A[i] > B[j]) {  5 A[index--] = A[i--];  6  7 } else {  8 A[index--] = B[j--];  9  } 10  } 11 while(i >= 0) { 12 A[index--] = A[i--]; 13  } 14 while(j >= 0) { 15 A[index--] = B[j--]; 16  } 17 18 }

 1 // A = 2 3 4 5 6 7  2 // B = 1  3 // 找中点，第k = 4大的数，则先去掉 k/2 = 2 个数，之后再从剩下的数中找第k-k/2 = 2大的数。  4 // 去2个数时，由于B不包含2个数，所以把A的前2个数去掉，剩下： 4 5 6 7 和 1;  5 // 从它们中找第2大的数就是结果。去掉的数不一定非要是A，B中最小的前几个数，只要保证去掉的数比要找的数小，那要找的数的相对位置就不会变。  6 // 在4 5 6 7 和 1中找第2个大的数时，先去掉1个数，在从剩下的里面找第一个大的数就是结果。所以把1去掉，剩下了4 5 6 7 。这时第1个大的数是4，也就是最后结果。  7  8 public double findMedianSortedArrays(int[] A, int[] B) {  9 int len = A.length + B.length; 10 if(len % 2 == 1) return findKth(A, 0, B, 0, len/2+1); 11 else return (findKth(A, 0, B, 0, len/2) + findKth(A, 0, B, 0, len/2+1)) / 2.0; 12 } 13 //函数含义：A数组从AStart角标开始，B从BStart开始，寻找A，B中第k个大的数 14 private int findKth(int[] A, int AStart, int[] B, int BStart, int k) { 15 if(AStart >= A.length) return B[BStart + k - 1]; 16 if(BStart >= B.length) return A[AStart + k - 1]; 17 18 if(k == 1) { 19 return Math.min(A[AStart], B[BStart]); 20  } 21 22 //找第k个，先去掉前k/2个数,AValue和BValue不可能都是MAX_VALUE 23 int AValue = AStart + k/2 - 1 < A.length ? A[AStart + k/2 - 1] : Integer.MAX_VALUE; 24 int BValue = BStart + k/2 - 1 < B.length ? B[BStart + k/2 - 1] : Integer.MAX_VALUE; 25 if(AValue <= BValue) { 26 //去A的前k/2个数，则去掉后的角标从AStart+k/2开始 27 return findKth(A, AStart+k/2, B, BStart, k - k/2); //递归的终止条件是k-k/2=1,一定会走到1，因为1+2+...+ k/2 = k - 1 k是偶数，1+1+2+...+ k/2 = k - 1 k是奇数 28 } else { 29 return findKth(A, AStart, B, BStart + k/2, k - k/2); 30  } 31 }

 1 //最大子数组答案 http://www.lintcode.com/zh-cn/problem/maximum-subarray/  2 public int maxSubArray(int[] nums) {  3 if(nums == null || nums.length == 0) return 0;  4 int sum = 0, preFixSum = 0, max = Integer.MIN_VALUE;  5 //理解不了的话，只需要知道这个操作能实现功能就行,死记代码  6 for(int i = 0; i< nums.length; i++) {  7 sum+= nums[i];  8 max = Math.max(max, sum - preFixSum);  9 preFixSum = Math.min(preFixSum, sum); 10  } 11 return max; 12  } 13 14 public int maxTwoSubArrays(List<Integer> nums) { 15 if(nums == null || nums.size() <= 1) return 0; 16 // i是分割线位置，i+1就是分割线之后的第一个位置的坐标 17 int result = Integer.MIN_VALUE; 18 for(int i = 0; i < nums.size() - 1; i++) { 19 int max1 = Integer.MIN_VALUE, max2 = max1; 20 int sum1 = 0, sum2 = 0, preFix1 = 0, preFix2 = 0; 21 for(int j = 0; j <=i; j++) { 22 sum1+=nums.get(j); 23 max1 = Math.max(max1, sum1 - preFix1); 24 preFix1 = Math.min(preFix1, sum1); 25  } 26 for(int j = i+1; j < nums.size(); j++) { 27 sum2+=nums.get(j); 28 max2 = Math.max(max2, sum2 - preFix2); 29 preFix1 = Math.min(preFix2, sum2); 30  } 31 result = Math.max(result, max1+max2); 32  } 33 return result; 34  } 35 //O(n)--------------------------------------------- 36 public int maxTwoSubArrays(List<Integer> nums) { 37 int[] left = new int[nums.size()]; 38 int[] right = new int[nums.size()]; 39 int sum = 0, preFixSum = 0, max = Integer.MIN_VALUE; 40 for(int i = 0; i< nums.size(); i++) { 41 sum+= nums[i]; 42 max = Math.max(max, sum - preFixSum); 43 preFixSum = Math.min(preFixSum, sum); 44 left[i] = max; 45  } 46 sum = 0, preFixSum = 0, max = Integer.MIN_VALUE; 47 for(int i = nums.size() - 1; i >= 0; i--) { 48 sum+= nums[i]; 49 max = Math.max(max, sum - preFixSum); 50 preFixSum = Math.min(preFixSum, sum); 51 right[i] = max; 52  } 53 int result = Integer.MIN_VALUE; 54 for(int i = 0; i < nums.size() - 1; i++) { 55 result = Math.max(result, left[i] + right[i+1]); 56  } 57 return result; 58 }

 1 //错误逻辑，思路都理不清，代码更写不出来。   2 public int maxProfit(int[] prices) {  3 if(prices == null || prices.length <= 1) return 0;  4 int profit = 0, min = 0;  5 for(int i : prices) {  6 min = Math.min(min, i);  7 profit + = i - min;  8  }  9 return profit; 10 } 11 // 当天有盈利，代表着当天卖出和前一天买入。连续三天盈利，每隔天的买入卖出正好合下来是三天前买入，三天后卖出的情况。 1 2 3 4 12 public int maxProfit(int[] prices) { 13 int profit = 0; 14 for(int i = 0; i < prices.length- 1; i++) { 15 int diff = prices[i + 1] - prices[i]; 16 if(diff > 0) profit += diff; 17  } 18 return profit; 19 }

 1 //-----------------------------------------------------------  2 // 暴力激活成功教程  3 public int maxProfit(int[] prices) {  4 if(prices == null || prices.length == 0) return 0;  5 int max =0 ;  6 for(int i = 1; i< prices.length; i++) {  7 int sum = 0;  8 for(int j = 0; j < i; j++) {  9 max= Math.max(max, prices[i] - prices[j]); 10  } 11  } 12 return max; 13  } 14 //------------------------------------------------------ 15 public int maxProfit(int[] prices) { 16 if(prices == null || prices.length == 0) return 0; 17 int min = Integer.MAX_VALUE, profit = 0; 18 for(int i : prices) { 19 min = Math.min(i, min); // min = i < min ? i : min; 20 profit = Math.max(i - min, profit); 21  } 22 return profit; 23  } 24 25 //股票二------------------------------------------ 26 public int maxProfit(int[] prices) { 27 int profit = 0; 28 for(int i = 0; i < prices.length- 1; i++) { 29 int diff = prices[i + 1] - prices[i]; 30 if(diff > 0) profit += diff; 31  } 32 return profit; 33 } 34 35 //股票三----------------------------------------------- 36 public int maxProfit(int[] prices) { 37 if (prices == null || prices.length <= 1) { 38 return 0; 39  } 40 41 int[] left = int[prices.length]; 42 int[] right = int[prices.length]; 43 44 //从左往右看，不依赖于右侧，能卖出的最大利润。通过更新买入的最小值(min)来计算 DP 45 int min = prices[0], left[0] = 0; 46 for(int i = 1; i < prices.length; i++) { 47 min = math.min(min, prices[i]); 48 left[i] = Math.max(left[i - 1], prices[i] - min); 49  } 50 51 //从右往左看，不依赖于左侧，能卖出的最大利润。通过更新卖出的最大值(max)来计算 52 int max = prices[prices.length - 1], right[prices.length - 1] = 0; 53 for(int i = prices.length -2; i>=0; i--) { 54 max = Math.max(prices[i], max); 55 right[i] = Math.max(right[i + 1], max - prices[i]); 56  } 57 58 //类似分割线，left和right不交叉 59 int maxProfit = 0; 60 for(int i = 0; i < prices.length; i++) { 61 maxProfit = Math.max(maxProfit, left[i] + right[i]); 62  } 63 return maxProfit; 64 }

 1 //O(n * n)---------------------------------------------------------------  2 public int[] twoSum(int[] numbers, int target) {  3 if(numbers == null || numbers.length == 0) return new int[]{-1, -1};  4 for(int i = 0; i < numbers.length - 1; i++) {  5 for(int j = i +1; j < numbers.length; j++) {  6 if(numbers[i] + numbers[j] == target) return new int[]{i +1, j+1};  7  }  8  }  9 return new int[]{-1, -1}; 10 11 //O(nlogn)-------------------------- 12 public int[] twoSum(int[] numbers, int target) { 13 //先排序，获得排序数组nlogn,下面的操作是O(n)，最后总体的时间复杂度nlogn. 14 if(numbers == null || numbers.length <=1) return new int[]{-1, -1}; 15 for(int i = 0, j = numbers.length - 1; i < j;) { 16 if(numbers[i] + numbers[j] == target) return new int[]{i + 1,j + 1}; 17 else if ( numbers[i] + numbers[j] < target) i++; 18 else j--; 19  } 20 return new int[]{-1, -1}; 21 22 } 23 //O(n)------------------------------ 24 public int[] twoSum(int[] numbers, int target) { 25 if(numbers == null || numbers.length == 0) return null; 26 Map<Integer, Integer> map = new HashMap<Integer, Integer>(); 27 for(int i = 0; i < numbers.length; i++) { 28 if(map.containsKey(numbers[i])) { 29 return new int[] {map.get(numbers[i]) + 1, i+1}; 30  } 31 map.put(target - numbers[i], i); 32  } 33 return null;

 1 //报错，rainb里不设置startColo会排序出问题，所以这种换位的快排操作到底会产生什么结果？----------------------------------------------  2 public void sortColors2(int[] colors, int k) {  3 if (colors == null || colors.length == 0) {  4 return;  5  }  6 rainbowSort(colors, 0, colors.length - 1);  7  8 }  9 10 private void rainbowSort(int[] colors, int start, int end) { 11 if(colors == null || colors.length <= 1) return; 12 if(start >= end) return; 13 int mid = start + (end - start) / 2; 14 int k = colors[mid]; 15 int i = start, j = end; 16 while(i <= j) { 17 while(i <=j && colors[i] < k) i++; 18 while(i <=j && colors[j] >= k) j--; 19 if(i <= j) { 20 int temp = colors[i]; 21 colors[i] = colors[j]; 22 colors[j] = temp; 23 i++; 24 j--; 25  } 26  } 27 rainbowSort(colors, start, i - 1); 28 rainbowSort(colors,i + 1, end); 29 } 30 //能用---------------------------------------------------------------------------------  31 public void sortColors2(int[] colors, int k) { 32 if (colors == null || colors.length == 0) { 33 return; 34  } 35 rainbowSort(colors, 0, colors.length - 1, 1,k); 36 37 } 38 39 private void rainbowSort(int[] colors, int start, int end, int startColor, int endColor) { 40 if (startColor == endColor) { 41 return; 42  } 43 if(colors == null || colors.length <= 1) return; 44 if(start >= end) return; 45 int midColor = (startColor + endColor)/2; 46 int i = start, j = end; 47 while(i <= j) { 48 //为啥？？？？？？？？？？？？？？ 49 //这里必须 <= midColor, 不能是< 50 while(i <=j && colors[i] <= midColor) i++; 51 while(i <=j && colors[j] > midColor) j--; 52 if(i <= j) { 53 int temp = colors[i]; 54 colors[i] = colors[j]; 55 colors[j] = temp; 56 i++; 57 j--; 58  } 59  } 60 //这里必须是midColor，不能是midColor+1 61  rainbowSort(colors, start, i, startColor, midColor); 62 rainbowSort(colors,i,end, midColor+1, endColor); 63 }

 1 public int partitionArray(int[] nums, int k) {  2 if(nums == null | nums.length <= 0) return -1;  3 int i = 0, j = nums.length - 1;  4 while(i <= j) {  5 while(nums[i] < k) i++;  6 while(nums[j] >= k) j--;  7 if(i <= j) {  8 int temp = nums[j];  9 nums[j] = nums[i]; 10 nums[i] = temp; 11  } 12  } 13 return i; 14 }

 1 class Pair {  2 //记录前几个数的和  3 int sum;  4 int index;  5 public Pair(int s, int i) {  6 this.sum = s;  7 this.index = i;  8  }  9  } 10 11 public class Solution { 12 13 public int[] subarraySumClosest(int[] nums) { 14 if(nums == null || nums.length == 0) return null; 15 if(nums.length == 1) return new int[]{0, 0}; 16 //结果集数组 17 int[] res = new int[2]; 18 19 int len = nums.length; 20 //遍历一次nums，获得Pair数组,其中，前0个数的和是0 21 Pair[] sums = new Pair[len + 1]; 22 sums[0] = new Pair(0,0); 23 for(int i = 1; i <= len; i++) { 24 sums[i] = new Pair(sums[i - 1].sum + nums[i - 1], i); 25  } 26 27 Arrays.sort(sums, new Comparator<Pair>(){ 28 public int compare(Pair p1, Pair p2) { 29 return p1.sum - p2.sum; 30  } 31  }); 32 33 //排序完成后，遍历sums数组，找到离0最近的子数组，从角标1开始。 34 int ans = Integer.MAX_VALUE; //answer 35 for(int i = 1; i <= len; i++) { 36 if(ans > sums[i].sum - sums[i - 1].sum) { 37 ans = sums[i].sum - sums[i - 1].sum; 38 //Pair 记录的是前几个数的和，前0,1,2个等等，对应nums中的角标需要-1； 39 int[] temp = new int[]{sums[i].index - 1, sums[i - 1].index - 1}; 40  Arrays.sort(temp); 41 //前5个数的和-前3个数的和离0最近，则需要返回的是第4，第5个的角标，所以temp[0]+1； 42 res[0] = temp[0] + 1; 43 res[1] = temp[1]; 44  } 45  } 46 return res; 47  } 48 }

 1 public ArrayList<Integer> subarraySum(int[] nums) {  2 if(nums == null || nums.length == 0) return null;  3 ArrayList<Integer> res = new ArrayList<Integer>();  4 Map<Integer, Integer> map = new HashMap();  5 map.put(0, -1);  6 int sum = 0;  7 for(int i = 0; i < nums.length; i++) {  8 sum += nums[i];  9 if(map.get(sum) != null) { 10 res.add(map.get(sum) + 1); 11  res.add(i); 12 return res; 13  } 14  map.put(sum, i); 15  } 16 return null; 17 }

 1 public class MinStack {  2  3 //minStack的构造放到构造函数中比较好。  4 Stack<Integer> minStack = new Stack<Integer>();  5 Stack<Integer> s ;  6  7 public MinStack() {  8 // do initialize if necessary  9 s = new Stack<Integer>(); 10  } 11 12 public void push(int number) { 13 // write your code here 14  s.push(number); 15 if(minStack.isEmpty() || minStack.peek() >= number) minStack.push(number); 16  } 17 18 public int pop() { 19 // write your code here 20 int number = s.pop(); 21 if(number == minStack.peek()) minStack.pop(); 22 return number; 23  } 24 25 public int min() { 26 // write your code here 27 28 return minStack.peek(); 29  } 30 }

 1 public int largestRectangleArea(int[] height) {  2 if(height == null || height.length == 0) return 0;  3 Stack<Integer> s = new Stack<Integer>();  4 int max = 0;  5 for(int i = 0; i <= height.length; i++) {  6 int currHeight = (i == height.length)?-1:height[i];  7 while(!s.isEmpty() && currHeight <= height[s.peek()]) {  8 int h = height[s.pop()];  9 int w = s.isEmpty()? i: i - s.peek() - 1; 10 max = Math.max(max, h*w); 11  } 12  s.push(i); 13  } 14 return max; 15 }

 1 public void hashFunc(String key) {  2 //hash本身就是杂乱无章的表示。所以不要去理解表达的含义，大概类似于把key按33进制表示出来，同时让他最后的值处于HASH_TABLE_SIZE的范围中。  3 int sum = 0;  4 for(int i = 0; i < key.length(); i++ ) {  5 sum = sum * 33 + (int)key.charAt(i);  6 sum = sum % HASH_TABLE_SIZE; //如果不包含这一步，则相当于把key当成33进制数表示出来。 1234 按十进制表达： ((1*10 + 2)*10+3)*10 + 4;  7 //HASH_TABLE_SIZE 表示开辟的数组大小，实际存储的数据size/HASH_TABLE_SIZE = 1/10 最好，否则size再大，  8 //产生冲突的概率会增大。每一次操作都保证sum在HASH_TABLE_SIZE的范围内。  9 10  } 11 return sum; 12 } 

 1 public ListNode[] rehashing(ListNode[] hashTable) {  2 if(hashTable == null || hashTable.length == 0) return hashTable;  3 ListNode[] newHash = new ListNode[hashTable.length * 2];  4 int len = newHash.length;  5 for(int i = 0; i < hashTable.length; i++) {  6 ListNode node = hashTable[i];  7 int index = 0;  8 while(node != null ) {  9 index = (node.val%len + len) % len; 10 if(newHash[index] == null) { 11 newHash[index] = new ListNode(node.val); 12 node = node.next; 13 continue; 14  } 15 ListNode head = newHash[index]; 16 while( head.next != null) { 17 head = head.next; 18  } 19 head = new ListNode(node.val); 20 21 node = node.next; 22  } 23  } 24 return newHash; 25 }

 1 private int getNextHappy(int n) {  2 int sum = 0;  3 while (n != 0) {  4 sum += (n % 10) * (n % 10);  5 n /= 10;  6  }  7 return sum;  8  }  9 10 public boolean isHappy(int n) { 11 HashSet<Integer> hash = new HashSet<Integer>(); 12 while (n != 1) { 13 if (hash.contains(n)) { 14 return false; 15  } 16  hash.add(n); 17 n = getNextHappy(n); 18  } 19 return true; 20 }

 1 public int[] medianII(int[] nums) {  2 // write your code here   3 if(nums == null || nums.length == 0) return null;  4 PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();  5 PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(1, new Comparator<Integer>(){  6 //@Override 可以不写，但是compare方法参数必须是Integer，不能是int  7 public int compare(Integer x, Integer y) {  8 return y - x;  9  } 10  }); 11 int[] res = new int[nums.length]; 12 res[0] = nums[0]; 13 maxHeap.offer(nums[0]); 14 for(int i = 1; i < nums.length; i++) { 15 if(nums[i] <= maxHeap.peek()) { 16  maxHeap.offer(nums[i]); 17 } else { 18  minHeap.offer(nums[i]); 19  } 20 21 //开始进入两个元素时，size上，maxHeap = minHeap 或者 maxHeap = minHeap +2，经过下面的if语句，转变成maxHeap = minHeap 22 // 每一轮进来后，只会出现maxHeap = minHeap 或者maxHeap = minHeap +1两种情况。（类似一种递推的关系） 23 if(maxHeap.size() > minHeap.size() + 1) { 24  minHeap.offer(maxHeap.poll()); 25 } else if( maxHeap.size() < minHeap.size()) { 26  maxHeap.offer(minHeap.poll()); 27  } 28 res[i] = maxHeap.peek(); 29  } 30 return res; 31 }

 1 // 0 1 2 3 4 5 6 7 len = 8, mid = 3 对于位置i，两个子树2i+1，2i+2；对于位置i-1，子树2(i-1) +1, 2(i-1) +2,即2i-1和2i。  2 //也就是说 i-1,i-1恰好能连续覆盖掉2i-1,2i，2i+1，2i+2；  3 // 0 1 2 3 4 5 6 7 8 len = 9, mid = 4  4  5 public void heapify(int[] A) {  6 // write your code here  7 //O(n)完成，只遍历一次，但是遍历的方式不是简单的从头到尾，而是从中间往左。  8 int mid = (A.length - 1)/2;  9 for(int i = mid; i >=0; i--) { 10  siftdown(A, i); 11  } 12 13  } 14 15 private void siftdown(int[] A, int k) { 16 int son = 0; 17 while(2*k+1 < A.length) { //从后往前保证 两个子树比根小，即有一定顺序。如果靠前的位置发生过swap，那也要保证swap之后，后面的位置还是有序 18 //所以有k = son 19 son = 2*k+1; 20 if(2*k+2 < A.length && A[2*k+2] <= A[son] ) son = 2*k+2; //son是两个子树中的较小的一个 21 22 if(A[son] < A[k]) { 23  swap(A, son, k); 24 k = son; 25 } else { 26 break; 27  } 28  } 29 30  } 31 private void swap(int[] A, int x, int y) { 32 int temp = A[x]; 33 A[x] = A[y]; 34 A[y] = temp; 35 }

 1 public int nthUglyNumber(int n) {  2 int[] uglyArr = new int[n];  3 uglyArr[0] = 1;  4 //p2,p3,p5代表三个指针，指向uglyArr数组的索引。  5 int p2 = 0, p3=0, p5 = 0;  6 for(int i= 1; i < n; i++) {  7 // <= 说明此索引位置的丑数已经乘以过2了，即已有的丑数数组中已经包含由此位置丑数*2所对应的丑数了，  8 // 那么下一轮再乘的时候，就不能用此位置的丑数*2了，要用下一个丑数来乘。  9 // 所以p2表示：当前待乘以2来候选作为下一个丑数的数的角标 10 //为啥不是用uglyArr[i - 1]来乘2呢，比如1， 2，，3 用 3 *2 显然比 2* 2大，所以下一个丑数不是3*2。 11 //所以应该记录的是之前的丑数，1,2，3是否乘过2,3,5，p2= 1,p3= 1, p5 = 0表示5还没有乘过角标0的数，2没有乘过角标1的数,3没有乘过角标1的数。 12 if(uglyArr[p2] * 2 <= uglyArr[i - 1]) p2++; 13 if(uglyArr[p3] * 3 <= uglyArr[i - 1]) p3++; 14 if(uglyArr[p5] * 5 <= uglyArr[i - 1]) p5++; 15 16 //这一轮最小值是乘的2,3还是5会在下一轮通过if判断出来，判断出来后，p2,p3,p5中有且只有一个指针会移动1个位置。 17 uglyArr[i] = Math.min(uglyArr[p2] * 2, 18 Math.min(uglyArr[p3] * 3, uglyArr[p5] * 5)); 19  } 20 return uglyArr[n - 1]; 21 }

 1 /** 验证下面的结论是否普遍成立：  2  * 1%11*10%11*10%11=100%11=1 power  3  * 5%11*10%11*10%11= 5 =1 * 5  4  * 结论是：成立  5 */  6 public static void main(String[] args) {  7 int HASH_SIZE=1000000;  8 for(int numberSize = 2; numberSize < 10; numberSize++) {  9 int power = 1; 10 for(int i = 0; i <4; i++) { 11 power = (power*31)%HASH_SIZE; 12  } 13 for(int i =1; i < 10; i++) { 14 int count = 0; 15 int num = i; 16 int count0 = (num* power)%HASH_SIZE; 17 for(int j = 0; j < 5; j++) { 18 if(j != 0) num = 0; 19 count = (count*31+num)%HASH_SIZE; 20  } 21 if(count != count0){ 22  System.out.println(i); 23 break; 24  } 25  } 26 System.out.println(numberSize+"::finish"); 27  } 28 }

 1 private int HASH_SIZE = 1000000;  2  3 public int strStr(String source, String target) {  4 // Write your code here  5 if (source == null || target == null) {  6 return -1;  7  }  8 int m = source.length();  9 int n = target.length(); 10 if (n == 0) { 11 return 0; 12  } 13 if (m == 0) { 14 return -1; 15  } 16 int targetCode = 0; 17 for (int i = 0; i < n; i++) { 18 targetCode = (targetCode * 31 + target.charAt(i)) % HASH_SIZE; 19  } 20 int power = 1; 21 for (int i = 0; i < n; i++) { 22 power = (power * 31) % HASH_SIZE; 23  } 24 int hashCode = 0; 25 for (int i = 0; i < m; i++) { 26 //只有一开始i = n-1 时hashCode记录的是n个数的hash值， 27 //之后一直记录的是n+1个数的值，所以power才要乘31^n 而不是31^(n-1) 28 hashCode = (hashCode * 31 + source.charAt(i)) % HASH_SIZE; 29 if (i < n - 1) { 30 continue; 31  } 32 if (i >= n) { 33 hashCode = hashCode - (source.charAt(i - n) * power)% HASH_SIZE ; 34 //为啥可能出现hashcode<0? 因为新添加的一位导致hashcode的值>HASH_SIZE,出现了取模的情况， 35 // 而 a%b = (a+b)%b,所以<0的情况，原本的hashcode计算方式应该是： 36 // hashcode = hashCode + HASH_SIZE - (source.charAt(i - n) * power)% HASH_SIZE ; 37 // 所以如果遇到<0的情况，加HASH_SIZE就好了。 38 if (hashCode < 0) { 39 hashCode += HASH_SIZE; 40  } 41  } 42 // 0~n-1 i=n-1, 0 = i - n+1 43 // 1~n i=n, 1 = i - n+1 44 if (hashCode == targetCode) { 45 if (source.substring(i - n + 1, i + 1).equals(target)) { 46 return i - n + 1; 47  } 48 49  } 50  } 51 return -1; 52 }

 1 public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {  2 //图的BFS，类似二叉树的BFS，不过需要统计邻居关系，避免已经访问过的邻居重复访问，所以用Map+ Queue实现。  3 //Queue可以用ArrayList + 头索引的位置来表示  4 if(node == null) return node;  5 ArrayList<UndirectedGraphNode> list = new ArrayList(); //放原先的结点  6 Map<UndirectedGraphNode,UndirectedGraphNode> map = new HashMap(); //放复制节点和原先结点的映射关系  7 int start = 0;  8  9  list.add(node); 10 map.put(node, new UndirectedGraphNode(node.label)); 11 while(start < list.size()) { 12 UndirectedGraphNode curr = list.get(start++); 13 for(int i = 0; i < curr.neighbors.size(); i++) { 14 if(!map.containsKey(curr.neighbors.get(i))) { 15  list.add(curr.neighbors.get(i)); 16 map.put(curr.neighbors.get(i), new UndirectedGraphNode(curr.neighbors.get(i).label)); 17  } 18  } 19  } 20 21 // copy edge 22 for(int i = 0; i < list.size(); i++) { 23 UndirectedGraphNode curr = list.get(i); 24 for(int j = 0; j < curr.neighbors.size(); j++) { 25  map.get(curr).neighbors.add(map.get(curr.neighbors.get(j))); 26  } 27  } 28 return map.get(node); 29 }

 1 public List<List<Integer>> permute(int[] nums) {  2 // write your code here  3 if(nums == null) return null;  4 List<List<Integer>> rst = new ArrayList<List<Integer>>();  5 ArrayList<Integer> list = new ArrayList<Integer>();  6 if(nums.length == 0) {  7  rst.add(list);  8 return rst;  9  } 10  helper(rst, list, nums ); 11 return rst; 12 } 13 14 public void helper(List<List<Integer>> rst, ArrayList<Integer> list, int[] nums){ 15 if(list.size() == nums.length) { 16 //不能rst.add(list) 地址传递，最后内容都没了 17 rst.add(new ArrayList<Integer>(list)); 18 return; 19  } 20 for(int i = 0; i < nums.length; i++) { //假设nums={1,2,3,4}，最外的循环进来，for4次对应四种情况： [ ] 21 // |--[1] 22 // |--[2] 23 // |--[3] 24 // |--[4] 25 //对于每一种情况，比如[1]，又分为了三种 [1] 26 // |--[2] 27 // |--[3] 28 // |--[4] 29 //......最后直到list.size()==nums.length,所有元素都放进去了，才作为一次结果返回。 30 31 if(list.contains(nums[i])) { 32 continue; 33  } 34  list.add(nums[i]); 35  helper(rst, list, nums); 36 list.remove(list.size() - 1); 37  } 38 }

 1 ArrayList<ArrayList<String>> solveNQueens(int n) {  2 if(n <= 0) return null;  3 ArrayList<ArrayList<String>> rst = new ArrayList<ArrayList<String>>();  4 search(rst, new ArrayList<Integer>(), n);  5 return rst;  6  7  }  8  9 private void search(ArrayList<ArrayList<String>> rst, ArrayList<Integer> cols, int n) { 10 if(cols.size() == n) { 11  rst.add(drawChess(cols)); 12 return; 13  } 14 for(int i = 0; i < n; i++) { 15 if(!isValid(cols, i)) { 16 continue; 17  } 18  cols.add(i); 19  search(rst, cols, n); 20 cols.remove(cols.size() - 1); 21  } 22  } 23 //查看第cols.size()行的第colIndex 列是否合法 24 //根据cols元素的放法的定义，不可能出现同一行，只可能有同一列或者同一斜行的情况。 25 private boolean isValid(ArrayList<Integer> cols, int colIndex) { 26 int rowIndex = cols.size(); 27 for(int i = 0; i < rowIndex; i++) { 28 if(cols.get(i) == colIndex) return false; 29 // right-top to left-down 30 // 。Q 。 。 31 // 。。 Q 。 左上到右下情况下的相同斜线： (0, 1) (1,2) 行序号-列序号的值相等。 32 33 // 。。 。 Q 34 // 。。 Q 。 右上到左下情况下的相同斜线： (0, 3) (1,2) 行序号+列序号的值相等。 35 if(cols.get(i) + i == rowIndex + colIndex) return false; 36 if(cols.get(i) - i == colIndex - rowIndex ) return false; 37  } 38 return true; 39  } 40 private ArrayList<String> drawChess(ArrayList<Integer> cols) { 41 ArrayList<String> list = new ArrayList<String>(); 42 for(int i = 0; i < cols.size(); i++) { 43 StringBuilder sb = new StringBuilder(); 44 for(int j = 0; j < cols.size(); j++) { 45 //(cols.get(i) == j)?sb.append('Q'):sb.append('.'); 46 sb.append(j == cols.get(i) ? 'Q' : '.'); 47  } 48  list.add(sb.toString()); 49  } 50 return list; 51 }

 1 public int ladderLength(String start, String end, Set<String> dict) {  2 // 超时了，dict很大的时候，isValidChange 用时过长。  3 if(start == null || end == null || dict == null) return 0;  4 if(isValidChange(start,end)) return 2;  5 List<String> list = new ArrayList<String>();  6  list.add(start);  7 return searchValidChange(list, dict, end);  8 }  9 private int searchValidChange(List<String> list, Set<String> dict,String end) {  10 int level = 1;  11 int pos = 0;  12 while(list.size() < dict.size() + 1) {  13 int len = list.size();  14 while(pos < len) {  15 for(String s1 : dict) {  16 if(list.contains(s1)) continue;  17 if(isValidChange(list.get(pos), s1)) {  18 if(isValidChange(s1, end)) return level+2;  19  list.add(s1);  20  }  21  }  22 pos++;  23  }  24 level++;  25  }  26 return 0;  27 }  28 private boolean isValidChange(String s1, String s2) {  29 if(s1.length() != s2.length()) return false;  30 int count = 0;  31 for(int i = 0; i < s1.length(); i++) {  32 if(s1.charAt(i) == s2.charAt(i)) continue;  33 count++;  34 //if(count > 1) return false;  35  }  36 return count == 1;  37 }  38 //----------------------------------------------------  39 public int ladderLength(String start, String end, Set<String> dict) {  40 if (dict == null) {  41 return 0;  42  }  43  44 if (start.equals(end)) {  45 return 1;  46  }  47  48  dict.add(start);  49  dict.add(end);  50  51 HashSet<String> hash = new HashSet<String>();  52 Queue<String> queue = new LinkedList<String>();  53  queue.offer(start);  54  hash.add(start);  55  56 int length = 1;  57 while(!queue.isEmpty()) {  58 length++;  59 int size = queue.size();  60 for (int i = 0; i < size; i++) {  61 String word = queue.poll();  62 for (String nextWord: getNextWords(word, dict)) {  63 if (hash.contains(nextWord)) {  64 continue;  65  }  66 if (nextWord.equals(end)) {  67 return length;  68  }  69  70  hash.add(nextWord);  71  queue.offer(nextWord);  72  }  73  }  74  }  75 return 0;  76  }  77  78 // replace character of a string at given index to a given character  79 // return a new string  80 private String replace(String s, int index, char c) {  81 char[] chars = s.toCharArray();  82 chars[index] = c;  83 return new String(chars);  84  }  85  86 // get connections with given word.  87 // for example, given word = 'hot', dict = {'hot', 'hit', 'hog'}  88 // it will return ['hit', 'hog']  89 private ArrayList<String> getNextWords(String word, Set<String> dict) {  90 ArrayList<String> nextWords = new ArrayList<String>();  91 for (char c = 'a'; c <= 'z'; c++) {  92 for (int i = 0; i < word.length(); i++) {  93 if (c == word.charAt(i)) {  94 continue;  95  }  96 String nextWord = replace(word, i, c);  97 if (dict.contains(nextWord)) {  98  nextWords.add(nextWord);  99  } 100  } 101  } 102 return nextWords; 103 }

 1 //懒得看了，bfs写的就问题很大。用一个队列就能解决的问题，套了半天map，死循环，还绕。  2 private Map<String, Integer> map;  3 private int minLen = Integer.MAX_VALUE;  4 private List<List<String>> rsts;  5 private Set<String> dict;  6 public List<List<String>> findLadders(String start, String end, Set<String> dict) {  7 // write your code here   8 if(start == null || end == null) return null;  9 rsts = new ArrayList<>(); 10 List<String> rst = new ArrayList<String>(); 11  rst.add(start); 12 if(start.equals(end)) { 13 rsts.add(new ArrayList<String>(rst)); 14 return rsts; 15  } 16 if(dict == null) return null; 17 map = findShortestLen(dict, end); 18 this.dict = dict; 19  dict.add(end); 20 //dict.add(start); 21  dfs(rst, start, end); 22 return rsts; 23 } 24 //dfs 25 private void dfs(List<String> rst,String start, String end) { 26 if(map.get(start) != null && map.get(start) == 2 && rst.size() + 1 == minLen) { 27 List<String> addRst = new ArrayList<String>(rst); 28  addRst.add(end); 29  rsts.add(addRst); 30  } 31 List<String> list = findNextWords(dict, start); 32 for(String s : list) { 33 //List<String> addList = new ArrayList<String>(); 34 if(!map.containsKey(s)) continue; 35 if(minLen < rst.size() + map.get(s)) continue; 36 else { 37 minLen = rst.size() + map.get(s); 38  rst.add(s); 39  dfs(rst, s, end ); 40 rst.remove(rst.size() - 1); 41  } 42 43  } 44 return; 45 } 46 //bfs  47 private Map<String, Integer> findShortestLen(Set<String> dict, String end) { 48 Map<String, Integer> map = new HashMap<>(); 49 map.put(end, 1); 50 int len = 1; 51 while(map.size() < dict.size()) { ///zzz, abc, abd, zzz永远也放不进map，死循环，先不管。  52 Map<String, Integer> temp = new HashMap<>(); 53 for(String s1 : map.keySet()) { 54 if(map.get(s1) != len) continue; 55 List<String> list = findNextWords(dict, s1); 56 if(list == null) continue; 57 for(String s2 : list) { 58 if(map.containsKey(s2) || temp.containsKey(s2)) continue; 59 temp.put(s2, len + 1); 60  } 61  } 62 len++; 63  map.putAll(temp); 64  } 65 return map; 66 } 67 private List<String> findNextWords(Set<String> dict, String end) { 68 List<String> list = new ArrayList<String>(); 69 for(int i = 'a'; i <= 'z'; i++) { 70 for(int j = 0; j < end.length(); j++) { 71 if(i == end.charAt(j)) continue; 72 String s = replaceOneChar(end, j, (char)i); 73 if(dict.contains(s)) list.add(s); 74  } 75  } 76 return list; 77 } 78 private String replaceOneChar(String end, int pos, char c) { 79 char[] chars = end.toCharArray(); 80 chars[pos] = c; 81 return Arrays.toString(chars); 82 }

 1 public List<List<String>> findLadders(String start, String end, Set<String> dict) {  2 List<List<String>> rsts = new ArrayList<>();  3 List<String> rst = new ArrayList<String>();  4 Map<String,List<String>> map = new HashMap();  5 Map<String, Integer> distance = new HashMap();  6  dict.add(start);  7 dict.add(end); //避免dict中有无start和end造成的分类讨论  8  bfs(map, distance, start , end, dict);  9  dfs(rsts,map, distance,rst, end, start); 10 return rsts; 11 } 12 //从end开始添加 13 private void dfs(List<List<String>> rsts, Map<String,List<String>> map, Map<String, Integer> distance, List<String> rst, String curr, 14  String start) { 15  rst.add(curr); 16 if(curr.equals(start)) { 17  Collections.reverse(rst); 18 rsts.add(new ArrayList(rst)); 19  Collections.reverse(rst); 20 return; 21  } 22 /* 不要这样取元素 23  List<String> nexts = findNexts(dict, curr); 24  for(String next : nexts) { 25  if(distance.get(next) +1 == distance.get(curr)) { 26  dfs(rsts,map, distance, rst, next, start, dict); 27  } 28  }*/ 29 /* 这样只能取出一种结果来 30  List<String> list = map.get(curr); 31  dfs(rsts,map, distance, rst, list.get(list.size() - 1) , start, dict);*/ 32 List<String> list = map.get(curr); 33 for(String s : list) { 34 if(distance.get(s) +1 == distance.get(curr)) { 35  dfs(rsts,map, distance, rst, s , start); 36  } 37  } 38 rst.remove(rst.size() - 1); 39 40 } 41 //计算每一个字符串到start的路径距离  42 private void bfs(Map<String,List<String>> map, Map<String, Integer> distance, String start, String end, Set<String> dict) { 43 Queue<String> q = new LinkedList(); 44  q.offer(start); 45 distance.put(start, 0); 46 for(String s : dict) { 47 map.put(s, new ArrayList()); 48  } 49 while(!q.isEmpty()) { 50 String curr = q.poll(); 51 List<String> nexts = findNexts(dict, curr); 52 for(String next : nexts) { 53 /* 这样只能取出一种接过来 54  if(distance.containsKey(next)) continue; 55  distance.put(next, distance.get(curr) + 1); 56  map.get(next).add(curr); 57  q.offer(next);*/ 58  map.get(next).add(curr); 59 if(!distance.containsKey(next)) { 60 distance.put(next, distance.get(curr) + 1); 61  q.offer(next); 62  } 63  } 64  } 65 } 66 private List<String> findNexts(Set<String> dict, String curr) { 67 List<String> nexts = new ArrayList(); 68 for(char ch = 'a'; ch <='z'; ch++) { 69 for(int i = 0; i < curr.length(); i++) { 70 if (ch == curr.charAt(i)) continue; 71 String s = curr.substring(0, i) + ch + curr.substring(i+1); 72 if(dict.contains(s)) { 73  nexts.add(s); 74  } 75  } 76  } 77 return nexts; 78 }