[每天两道题]坚持找到工作为止

75. Sort Colors
这个题要求不能用排序类库，必须in-place，还必须one-pass，且O(1)的空间复杂度。也就是不能写普通的二分排序，必须一个循环一遍过。

普通排序不行的话，那就只能想办法用指针，然后交换数字了。
一开始我完全没思路，后来想到只能观察一下数组的特征，发现， 这个数组只有三个数字，012，0一定排在开头，2一定排在末尾。

那么我就可以定义左右两个指针，l = 0, r = n.len - 1。然后，我就可以开始扫描数组了，若是遇到一个0，我就把它和l交换，然后l++，若是遇到一个2，我们把它和r交换，再把r - -.
那么遇到1怎么办？我就想，那么遇到1就跳过好了。只要0，和2都排好，那么1也一定排好了。

不同于for循环的解法，我用的是while循环

1. int l = 0, curr = 0, r = nums.length - 1;
   
2.         while(curr <= r && l <= r) {
   
3.             curr = curr < l ? l : curr;
   
4.             if(nums[curr] == 0) {
   
5.                 swap(nums, curr, l);
   
6.                 l++;
   
7.             }else if(nums[curr] == 1) {
   
8.                 curr++;
   
9.             }else{
   
10.                 swap(nums, curr, r);
    
11.                 r--;
    
12.             }
    
13.         }
    
14.     }
    
15.    
    
16.     private void swap(int[] n, int a, int b) {
    
17.         int temp = n[a];
    
18.         n[a] = n[b];
    
19.         n[b] = temp;
    
20.     }
    

复制代码

79. Word Search
没什么好说的，就是dfs回溯法，遍历每一个数字，当遇到word[0]就开始找dfs。用一个数组记录一下走过的格子即可。每次找上下左右。返回条件是越界，或者不匹配，或者是找到了一个答案，那么就返回。当找到答案的时候，更新全局变量的答案为true;

1. class Solution {
   
2.     //[["A","B","C","E"],
   
3.     // ["S","F","E","S"],
   
4.     // ["A","D","E","E"]]
   
5.     //"ABCESEEEFS"
   
6.     boolean rs = false;
   
7.     public boolean exist(char[][] board, String word) {
   
8.         char[] ws = word.toCharArray();
   
9.    
   
10.         for(int i = 0; i < board.length; i++) {
    
11.             for(int j = 0; j < board[0].length; j++) {
    
12.                 if(ws[0] == board[i][j]){
    
13.                      helper(board, ws, 0, i, j, new int[board.length]  [board[0].length]);
    
14.                 }
    
15.             }
    
16.         }
    
17.         return rs;
    
18.     }
    
19.    
    
20.     private void helper(char[][] b, char[] w, int idx, int x, int y, int[][] seen) {
    
21.        if(idx == w.length) {
    
22.             rs = true;
    
23.             return;
    
24.         }
    
25.         if(x > b.length - 1 || x < 0 ||
    
26.            y > b[0].length - 1 || y < 0 ||
    
27.            b[x][y] != w[idx] || seen[x][y] == 1
    
28.           ) return;
    
29.       
    
30.         seen[x][y] = 1;
    
31.         helper(b, w, idx + 1, x + 1, y, seen);
    
32.         helper(b, w, idx + 1, x -1 , y, seen);
    
33.         helper(b, w, idx + 1, x, y + 1, seen);
    
34.         helper(b, w, idx + 1, x, y - 1, seen);
    
35.         
    
36.         seen[x][y] = 0;
    
37.         
    
38.     }
    
39. }

复制代码

78. Subsets
回溯法，若是你跟我一样背模版比较吃力，建议还是记住思路。回溯法的本质就是遍历一个树。我们生成对应的内容，其实就是进行正确的剪枝。
比如数组为［1，2，3］，那么树为
                 root []
              ／ ｜   \
            1      2      3
         /   \      |
        2   3     3
     /
   3
规律就是每个节点的孩子都是1 2 3三个节点，但是我们只走比母节点下标数值更大的孩子。
所以定义一个idx, 表示孩子在原数组的下标。 每次我们把idx + 1送到下一个递归里。这里唯一的坑就是，我们要先把当前的路径添加进最终答案，再判断要不要返回。因为idx > 2时候，curr = [1, 2, 3]，此时还是一个合法的有效答案，要先添加最终答案。
所以最后的代码就是

1. class Solution {
   
2.     //         root []
   
3.     //      1      2       3
   
4.     //   2   3    3
   
5.     //  3        
   
6.      List<List<Integer>> rs ;
   
7.     public List<List<Integer>> subsets(int[] nums) {
   
8.         rs = new ArrayList<>();
   
9.         helper(nums, new ArrayList<>(), 0);
   
10.         return rs;
    
11.     }
    
12.     private void helper(int[] nums, List<Integer> curr, int idx) {
    
13.         rs.add(new ArrayList<>(curr));
    
14.         if(idx > nums.length - 1) return;
    
15.         //System.out.println(rs.toString());
    
16.         for(int i = idx; i < nums.length; i++) {
    
17.             //System.out.println(idx + " " + i);
    
18.             curr.add(nums[i]);
    
19.             helper(nums, curr, i + 1);
    
20.             curr.remove(curr.size() - 1);
    
21.         }
    
22.     }
    
23. }

复制代码

77. Combinations
数组有n个数字，给出所有k个数字的组合。
还是回溯法，建议画出树
比如 数组是 ［1 ， 2， 3, 4］。 k = 2
                    []root
                /       |        \   
             1        2        3
         /   |  \       |   \      |      
       2    3  4     3   4     4
这样条件都很明确了,用一个idx记录当前的数字， 然后每一层，从idx+ 1开始进入下一层。
当树的高度 ＝ k + 1的时候，就添加当前路径进入最终的答案里。
代码就是

1. class Solution {
   
2.      List<List<Integer>> rs;
   
3.     public List<List<Integer>> combine(int n, int k) {
   
4.         rs = new ArrayList<>();
   
5.         helper(n, k ,1, new ArrayList<>());
   
6.         return rs;
   
7.     }
   
8.    
   
9.     private void helper(int n, int k, int idx, List<Integer> curr) {
   
10.         if(k == curr.size()) {
    
11.             rs.add(new ArrayList<>(curr));
    
12.             return;
    
13.         }
    
14.         
    
15.         for(int i = idx; i <= n; i++) {
    
16.             curr.add(i);
    
17.             helper(n, k, i + 1, curr);
    
18.             curr.remove(curr.size() - 1);
    
19.         }
    
20.     }
    
21. }

复制代码

今天是整一个月。正好做了80道题。若是600~800才能进大厂的话，还需要8到9个月，也就是明年春节才能有希望开始面试。

84 Largest Rectangle in Histogram
经典题，用单调栈。

1. class Solution {
   
2.     public int largestRectangleArea(int[] heights) {
   
3.         Stack<Integer> stack = new Stack<>();
   
4.         
   
5.         int max = 0;
   
6.         for(int i = 0; i < heights.length; i++) {
   
7.             if(stack.isEmpty()) {
   
8.                 stack.add(i);
   
9.                 continue;
   
10.             }
    
11.             
    
12.            
    
13.             while(!stack.isEmpty() && heights[i] < heights[stack.peek()]) {
    
14.                 int curr =stack.pop();
    
15.                 int left = stack.isEmpty() ? -1 : stack.peek();
    
16.                 int area = (i - 1 - left) * heights[curr];
    
17.                 max = Math.max(area, max);
    
18.             }
    
19.             stack.add(i);
    
20.             
    
21.         }
    
22.         
    
23.      
    
24.         while(!stack.isEmpty()) {
    
25.             int curr = stack.pop();
    
26.             int left = -1;
    
27.             while(!stack.isEmpty() && curr == stack.peek()) curr = stack.pop();
    
28.             
    
29.             left = stack.isEmpty() ? -1 : stack.peek();
    
30.             int area = (heights.length - 1- left) * heights[curr];
    
31.             max = Math.max(area, max);
    
32.         }
    
33.         
    
34.         return max;
    
35.     }
    
36. }

复制代码

82. Remove Duplicates from Sorted List II
难点是判断尾巴，因为要去掉重复的，而不是保留。

1. /**
   
2. * Definition for singly-linked list.
   
3. * public class ListNode {
   
4. *     int val;
   
5. *     ListNode next;
   
6. *     ListNode() {}
   
7. *     ListNode(int val) { this.val = val; }
   
8. *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
   
9. * }
   
10. */
    
11. class Solution {
    
12.     public ListNode deleteDuplicates(ListNode head) {
    
13.       
    
14.         ListNode curr = head;
    
15.         ListNode pre = new ListNode();
    
16.         pre.next = head;
    
17.         ListNode dummy = pre;      
    
18.         
    
19.         while(curr != null) {
    
20.             boolean dup = false;
    
21.             
    
22.             while(curr.next != null && curr.val == curr.next.val) {
    
23.                 dup = true;
    
24.                 curr = curr.next;
    
25.             }
    
26.             
    
27.             if(dup) {
    
28.                  pre.next = curr.next;
    
29.             } else {
    
30.                 pre = curr;
    
31.             }
    
32.             
    
33.             curr = curr.next;
    
34.         }
    
35.         return dummy.next;
    
36.     }
    
37. }

复制代码

80. Remove Duplicates from Sorted Array II

1. class Solution {
   
2.     public int removeDuplicates(int[] nums) {
   
3.         //[0,1,1,2,3,3,2,3,3]
   
4.         //                 ^               
   
5.         //           ^         
   
6.         int i = 0;
   
7.         for(int num : nums) {
   
8.             if(i < 2 || num > nums[i - 2]) {
   
9.                 nums[i] = num;
   
10.                 i++;
    
11.             }
    
12.         }
    
13.         
    
14.         return i;
    
15.         
    
16.     }
    
17. }

复制代码

81. Search in Rotated Sorted Array II

1. class Solution {
   
2.     public boolean search(int[] nums, int target) {
   
3.         int l = 0;
   
4.         int r = nums.length - 1;
   
5.         
   
6.         if(nums.length == 1) return nums[0] == target;
   
7.         while(l <= r) {
   
8.             //System.out.println(l + " " + r);
   
9.             int mid = l + ((r - l) >> 1);
   
10.             
    
11.             if(nums[mid] == target) {
    
12.                 return true;
    
13.             }else if(nums[mid] > nums[r]) {
    
14.                 if(nums[mid] > target && target >= nums[l]) {
    
15.                     r = mid - 1;
    
16.                 }else l = mid + 1;
    
17.             }else if(nums[mid] < nums[r]) {
    
18.                 if(nums[mid] < target && target <= nums[r]) {
    
19.                     l = mid + 1;
    
20.                 }else r = mid - 1;
    
21.             }else --r;
    
22.         }
    
23.         ///System.out.println(l + " " + r);
    
24.         return false;
    
25.                      
    
26.     }
    
27. }

复制代码

83. Remove Duplicates from Sorted List

1. /**
   
2. * Definition for singly-linked list.
   
3. * public class ListNode {
   
4. *     int val;
   
5. *     ListNode next;
   
6. *     ListNode() {}
   
7. *     ListNode(int val) { this.val = val; }
   
8. *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
   
9. * }
   
10. */
    
11. class Solution {
    
12.     public ListNode deleteDuplicates(ListNode head) {
    
13.         //[   1,1,2,3,3]
    
14.         //            ^
    
15.         //          ^
    
16.         
    
17.       
    
18.         ListNode dummy = new ListNode();
    
19.         dummy.next = head;
    
20.         
    
21.         ListNode curr = head;
    
22.         ListNode pre = head;
    
23.         
    
24.         while(curr != null) {
    
25.             while(curr.next != null && curr.val == curr.next.val) {
    
26.                 curr = curr.next;
    
27.             }
    
28.             pre.next = curr.next;
    
29.             curr = curr.next;
    
30.             pre = pre.next;
    
31.         }
    
32.         return dummy.next;
    
33.     }
    
34. }

复制代码