人到中年，失业1年多，现在重新开始

刚才又做了这一题，我的教训是，

res[curr++] = nums[deque.peekLast()];   我写成了   res[curr++] = deque.peekLast();   始终忘记，单调栈里面存放的是index

1. class Solution {
   
2. 
   
3.     public int[] maxSlidingWindow(int[] nums, int k) {
   
4.         
   
5.         if(nums == null || nums.length < k){
   
6.             return new int[]{};
   
7.         }
   
8. 
   
9.         Deque<Integer> deque = new ArrayDeque<>();
   
10. 
    
11.         int[] res = new int[nums.length - k + 1];
    
12.         int curr = 0;
    
13. 
    
14.         for(int i = 0; i <= nums.length - 1; i++){
    
15. 
    
16.             while(!deque.isEmpty() && nums[i] > nums[deque.peekFirst()]){
    
17.                 deque.removeFirst();
    
18.             }
    
19. 
    
20.             deque.offerFirst(i);
    
21.   
    
22.             if(deque.peekLast() == i - k){
    
23.                 deque.removeLast();
    
24.             }
    
25. 
    
26.             if( i >= k - 1){
    
27.                 res[curr++] = nums[deque.peekLast()];
    
28.             }
    
29.         }
    
30. 
    
31.         return res;  
    
32.     }
    
33. }

复制代码

加油！ zszs

今天用heap sort写了一下 912题

总结:

1. size--; 和 siftDown(nums, 0, size); 写反了。所以错了。这里要先size--，才能去siftdown
2.

1. class Solution {
   
2. 
   
3.     public int[] sortArray(int[] nums) {
   
4.         
   
5.         if(nums == null || nums.length == 0){
   
6.             return nums;
   
7.         }        
   
8. 
   
9.         int size = nums.length;
   
10.         
    
11.         heapify(nums, size);
    
12. 
    
13.         while(size > 0){
    
14. 
    
15.             swap(nums, 0, size - 1);
    
16. 
    
17.             size--;
    
18. 
    
19.             siftDown(nums, 0, size);
    
20.         }
    
21. 
    
22.         return nums;
    
23.     }
    
24. 
    
25.     private void heapify(int[] nums, int size){
    
26.         for(int i = (nums.length - 2)/2; i >= 0; i--){            
    
27.             siftDown(nums, i, size);
    
28.         }
    
29.     }
    
30. 
    
31.     private void siftDown(int[] nums, int index, int size){
    
32. 
    
33.         while(index * 2 + 1 <= size - 1){
    
34. 
    
35.             int leftChild = index * 2 + 1;
    
36. 
    
37.             int biggerChild = leftChild;
    
38. 
    
39.             if(index * 2 + 2 <= size - 1){
    
40. 
    
41.                int rightChild = index * 2 + 2;
    
42. 
    
43.                if(nums[leftChild] >= nums[rightChild]){
    
44.                     biggerChild = leftChild;
    
45.                 } else {
    
46.                     biggerChild = rightChild;
    
47.                 }
    
48.             }   
    
49. 
    
50.             if(nums[index] < nums[biggerChild]){
    
51.                 swap(nums, index, biggerChild);
    
52.                 index = biggerChild;  
    
53.             } else {
    
54.                 break;
    
55.             }
    
56.         }
    
57. 
    
58.     }
    
59. 
    
60.     private void swap(int[] nums, int a, int b){
    
61.         int tmp = nums[a];
    
62.         nums[a] = nums[b];
    
63.         nums[b] = tmp;
    
64.     }
    
65. 
    
66. }

复制代码

加油。继续。看好你

加油加油，已加米

加油加油！ 看好你

楼主加油！！！一定可以的，挺你💪💪💪

加油！重新出发，一切都会好起来的

加油楼主！ 会越来越好！

第一轮面试过了。躺了10天，现在要继续鸡血，迎接10天后的4轮panel interview


216. Combination Sum III  



今天是这一题:

1. class Solution {
   
2. 
   
3. 
   
4.    public List<List<Integer>> combinationSum3(int k, int n) {
   
5. 
   
6. 
   
7.        List<List<Integer>> res = new LinkedList<>();
   
8. 
   
9. 
   
10.        if(k == 0){
    
11.            return res;
    
12.        }
    
13. 
    
14. 
    
15.        helper(res, new LinkedList<>(), 0, 1, k, n);
    
16. 
    
17. 
    
18.        return res;
    
19.    }
    
20. 
    
21. 
    
22.    public void helper(List<List<Integer>> res, List<Integer> tmp, int currSum, int start, int k, int n){
    
23. 
    
24. 
    
25.        if(currSum > n || tmp.size() > k){
    
26.            return;
    
27.        }
    
28. 
    
29. 
    
30.        if(currSum == n && tmp.size() == k){
    
31.            res.add(new LinkedList<>(tmp));
    
32.            return;
    
33.        }
    
34. 
    
35. 
    
36.        for(int i = start; i <= 9; i++){
    
37. 
    
38. 
    
39.            tmp.add(i);
    
40.            currSum += i;
    
41.            helper(res, tmp, currSum, i + 1, k, n);
    
42. 
    
43. 
    
44.            tmp.remove(tmp.size() - 1);
    
45.            currSum -= i;         
    
46.        }
    
47.    }
    
48. }
    
49. 
    
50. Not confirm yet
    
51. 
    
52. Time: (9! * K) / (9-k)!
    
53. Space: K

复制代码

这题的时间复杂度要怎么分析?  我真的百思不得其解。。。