IVN
0%

Array(2)

Posted on Edited on In
Symbols count in article: 20k Reading time ≈ 18 mins.

Array好题选编（2）

334. Increasing Triplet Subsequence

Follow up: Could you implement a solution that runs in O(n) time complexity and O(1) space complexity?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public boolean increasingTriplet(int[] nums) {
            int n=nums.length;
    if(n<3){
        return false;
    }
    int left=Integer.MAX_VALUE;
    int mid=Integer.MAX_VALUE;
    for (int i = 0; i < n; i++) {
        if(nums[i]>mid){
            return true;
        }
        if(nums[i]>left && nums[i]<mid){
            mid=nums[i];
            continue;
        }
        if(nums[i]<left){
            left=nums[i];
        }
    }
    return false;
}

361. Bomb Enemy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public int maxKilledEnemies(char[][] grid) {
    int row=grid.length;
    int col=grid[0].length;
    int res=0;
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            if(grid[i][j]=='0'){
                int count=0;
                for(int x=i-1; x>=0 ; x--){
                    if(grid[x][j]=='W'){
                        break;
                    }
                    if(grid[x][j]=='E'){
                        count++;
                    }
                }
                for(int x=i+1; x<row ; x++){
                    if(grid[x][j]=='W'){
                        break;
                    }
                    if(grid[x][j]=='E'){
                        count++;
                    }
                }
                for(int y=j-1; y>=0 ; y--){
                    if(grid[i][y]=='W'){
                        break;
                    }
                    if(grid[i][y]=='E'){
                        count++;
                    }
                }
                for(int y=j+1; y<col ; y++){
                    if(grid[i][y]=='W'){
                        break;
                    }
                    if(grid[i][y]=='E'){
                        count++;
                    }
                }
                res=Math.max(res,count);
            }
        }
    }
    return res;
}

325. Maximum Size Subarray Sum Equals k

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int maxSubArrayLen(int[] nums, int k) {
            int currSum = 0, maxLen = 0; // set initial values for cumulative sum and max length sum to k
    HashMap<Integer, Integer> sumToIndexMap = new HashMap<Integer, Integer>(); // key: cumulative sum until index i, value: i
    for (int i = 0; i < nums.length; i++) {
        currSum = currSum + nums[i]; // update cumulative sum
        
        // two cases where we can update maxLen
        if (currSum == k) maxLen = i + 1; // case 1: cumulative sum is k, update maxLen for sure
        else if (sumToIndexMap.containsKey(currSum - k)) maxLen = Math.max(maxLen, i - sumToIndexMap.get(currSum - k)); // case 2: cumulative sum is more than k, but we can truncate a prefix of the array
        
        // store cumulative sum in map, only if it is not seen
        // because only the earlier (thus shorter) subarray is valuable, when we want to get the maxLen after truncation
        if (!sumToIndexMap.containsKey(currSum)) sumToIndexMap.put(currSum, i);
    }
    return maxLen;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int maxSubArrayLen(int[] nums, int k) {
    Map<Integer,Integer> map=new HashMap<>();
    int n=nums.length;
    int curSum=0;
    int res=0;
    for (int i = 0; i < n; i++) {
        curSum+=nums[i];    //[0,i]
        if(curSum==k){
            res=Math.max(res,i+1);
        }else if(map.containsKey(curSum-k)){
            int index=map.get(curSum-k);    //[0,index]
            //[index+1,i] = k
            res=Math.max(res,i-index);
        }
        if(!map.containsKey(curSum)){
            map.put(curSum,i);
        }
    }
    return res;
}

373. Find K Pairs with Smallest Sums

法一：没看懂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<int[]> que = new PriorityQueue<>((a,b)->a[0]+a[1]-b[0]-b[1]);
        List<int[]> res = new ArrayList<>();
        if(nums1.length==0 || nums2.length==0 || k==0) return res;
        for(int i=0; i<nums1.length && i<k; i++) que.offer(new int[]{nums1[i], nums2[0], 0});
        while(k-- > 0 && !que.isEmpty()){
            int[] cur = que.poll();
            res.add(new int[]{cur[0], cur[1]});
            if(cur[2] == nums2.length-1) continue;
            que.offer(new int[]{cur[0],nums2[cur[2]+1], cur[2]+1});
        }
        return res;
    }
}

I was asked this question in a top company’s onsite interview. I presented this approach specifically the index pair approach like @EddieCarrillo ‘s and the interviewer didn’t buy it. He thought this will not work as when you poll index pair [i, j] out, the next could be [i + 1, j] or [i, j + 1], why did you only add [i, j + 1] to the queue? I tried to explain it in different ways, like thinking it as multiple linked lists, showing an example, and so on. He didn’t agree and still considered this as a wrong approach.

I came back and kept asking myself, how could I have explained this better? Here is they way I would have done:

When index pair [i, j] is polled out from the Priority Queue, it’s guaranteed that there is a pair [i + 1, x] is in the queue. (except its the last pair which we don’t need next pair)
Why is it? because we added all the smallest possible pairs [0, 0], [1, 0]…..[Min(k, n), 0].
Now for x, there are three cases:

  • if x < j, that means [i +1, x] is smaller than [i + 1, j]. Thus, [i + 1, j] won’t be a candidate. And it will be reached later by increasing x in [i + 1, x].
  • if x > j, that means [i + 1, x] is larger than [i + 1, j]. Thus, [i + 1, j] is already in the result, we should not consider it again.
  • if x = j, that’s the same pair. We should not add it to queue.

The damage on me is done. I just hope the interviewer come across this post and have an aha moment so that the future interviewees won’t be affected.

法二：想象成有序二维数组 好！

1
2
3
4
5
6
7
# # # # # ? . .
# # # ? . . . .
# ? . . . . . .   "#" means pair already in the output
# ? . . . . . .   "?" means pair currently in the queue
# ? . . . . . .
? . . . . . . .
. . . . . . . .
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
    List<List<Integer>> res=new ArrayList<>();
    PriorityQueue<int[]> pq=new PriorityQueue<>((a,b)->(a[2]-b[2]));
    int n1=nums1.length;
    int n2=nums2.length;
    //[0,n1-1]  j
    //...
    //i
    //n2-1
    pq.offer(new int[]{0,0,nums1[0]+nums2[0]});
    while(!pq.isEmpty() && k-->0){
        int[] cur=pq.poll();
        int i=cur[1];
        int j=cur[0];
        res.add(Arrays.asList(nums1[j],nums2[i]));
        if(j!=n1-1){
            pq.offer(new int[]{j+1,i,nums1[j+1]+nums2[i]});
        }
        if(j==0 && i+1<n2){
            pq.offer(new int[]{j,i+1,nums1[j]+nums2[i+1]});
        }
    }
    return res;
}

23. Merge k Sorted Lists

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public ListNode mergeKLists(ListNode[] lists) {
    
    PriorityQueue<ListNode> heap=new PriorityQueue<>((Comparator<ListNode>)(o1,o2)->o1.val-o2.val); //升序
    for (ListNode node : lists) {
        if(node!=null){
            heap.offer(node); //按优先级插入各个链表的头结点
        }
    }
    ListNode pre=new ListNode(-1);//空白头结点，指向新链表的第一个结点
    ListNode temp=pre;
    while(!heap.isEmpty()){
        ListNode curr=heap.poll(); //获取并移除队列头(当前最小值)
        temp.next=new ListNode(curr.val);//头插入新链表
        if(curr.next!=null){//若该原链表非空，则还有剩余结点
            heap.offer(curr.next);//将当前最小值的后一个结点入队
        }
        temp=temp.next;
    }
    return pre.next;
}

初代hard不如中代medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public ListNode mergeKLists(ListNode[] lists) {
  if(lists.length==0){
      return null;
  }
    PriorityQueue<ListNode> pq=new PriorityQueue<>((a,b)->(a.val-b.val));
    ListNode dummy=new ListNode(-1);
    ListNode pre=dummy;
    ListNode p=null;
    for (ListNode list : lists) {
        if(list!=null){
            pq.offer(list);
        }
    }
    while(!pq.isEmpty()){
        p=pq.poll();
        if(p.next!=null){
            pq.offer(p.next);
        }
        pre.next=p;
        pre=pre.next;
    }
    return dummy.next;
}

368. Largest Divisible Subset

注意：

  • 若只需求subset的大小，则只需dp数组
  • 还需要求subset的每个元素，则需要另一个数组prev，记录当前元素的前一个元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public List<Integer> largestDivisibleSubset(int[] nums) {
    int n=nums.length;
    Arrays.sort(nums);
    int max=0;
    int index=-1;
    int[] dp=new int[n];
    int[] prev=new int[n];
    Arrays.fill(prev,-1);
    for (int i = 0; i < n; i++) {
        dp[i]=1;
        for (int j = i-1; j >= 0; j--) {
            if(nums[i]%nums[j]==0 && dp[i]<dp[j]+1){
                dp[i]=dp[j]+1;
                prev[i]=j;
            }
        }
        if(dp[i]>max){
            max=dp[i];
            index=i;
        }
    }
    List<Integer> res=new ArrayList<>();
    while(index!=-1){
        res.add(nums[index]);
        index=prev[index];
    }
    return res;
}

377. Combination Sum IV

无脑backtracking超时！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int res=0;
int n;
public int combinationSum4(int[] nums, int target) {
    Arrays.sort(nums);
    n=nums.length;
    for (int i = 0; i < n; i++) {
        backtracking(nums,target-nums[i]);
    }
    return res;
}

void backtracking(int[] nums,  int target){
    if(target<=0){
        if(target==0){
            res++;
        }
        return;
    }
    for (int i = 0; i < n; i++) {
        if(target-nums[i]<0){
            break;
        }
        backtracking(nums,target-nums[i]);
    }
}

用map减少重复运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int n;
Map<Integer,Integer> map=new HashMap<>();
public int combinationSum4(int[] nums, int target) {
    Arrays.sort(nums);
    n=nums.length;
    return backtracking(nums,target);
}

int backtracking(int[] nums,  int target){
    if(target<=0){
        if(target==0){
            return 1;
        }
        return 0;
    }
    if(map.containsKey(target)){
        return map.get(target);
    }
    int res=0;
    for (int i = 0; i < n; i++) {
        if(target-nums[i]<0){
            break;
        }
        res+=backtracking(nums,target-nums[i]);
    }
    map.put(target,res);
    return res;
}

378. Kth Smallest Element in a Sorted Matrix

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int kthSmallest(int[][] matrix, int k) {
    PriorityQueue<int[]> pq=new PriorityQueue<>((a,b)->(a[2]-b[2]));
    int row=matrix.length;
    int col=matrix[0].length;
    pq.offer(new int[]{0,0,matrix[0][0]});
    int idx=1;
    while(true){
        int[] cur=pq.poll();
        if(idx==k){
            return cur[2];
        }
        int i=cur[0];
        int j=cur[1];
        idx++;
        if(j+1<col){
            pq.offer(new int[]{i,j+1,matrix[i][j+1]});
        }
        if(j==0 && i+1<row){
            pq.offer(new int[]{i+1,j,matrix[i+1][j]});
        }
    }
}

413. Arithmetic Slices

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int numberOfArithmeticSlices(int[] nums) {
    int n=nums.length;
    int res=0;
    for (int i = 0; i <= n-3; i++) {
        //[n-3,n-2,n-1]
        if(nums[i+1]-nums[i]==nums[i+2]-nums[i+1]){
            res++;
            int dif=nums[i+1]-nums[i];
            int j=i+3;
            while(j<n && nums[j]-nums[j-1]==dif){
                j++;
                res++;
            }
        }
    }
    return res;
}

477. Total Hamming Distance

Approach #1 Brute Force [Time Limit Exceeded]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int totalHammingDistance(int[] nums) {
    int n=nums.length;
    int res=0;
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            res+=hamming(nums[i],nums[j]);
        }
    }
    return res;
}

int hamming(int a, int b){
    int c=a^b;
    int res=0;
    while(c!=0){
        if((c&1)==1){
            res++;
        }
        c>>=1;
    }
    return res;
}

Approach #2 Loop over the bits! [Accepted]

For each bit position 1-32 in a 32-bit integer, we count the number of integers in the array which have that bit set. Then, if there are n integers in the array and k of them have a particular bit set and (n-k) do not, then that bit contributes k*(n-k) hamming distance to the total.

1
2
3
4
5
6
7
8
9
10
public int totalHammingDistance(int[] nums) {
    int total = 0, n = nums.length;
    for (int j=0;j<32;j++) {
        int bitCount = 0;
        for (int i=0;i<n;i++) 
            bitCount += (nums[i] >> j) & 1;
        total += bitCount*(n - bitCount);
    }
    return total;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int totalHammingDistance(int[] nums) {
    int res=0;
    int n=nums.length;
    for (int i = 0; i < 32; i++) {
        int count=0;
        for (int num : nums) {
            if((num&(1<<i))!=0){
                count++;
            }
        }
        res+=count*(n-count);
    }
    return res;
}

31. Next Permutation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public void nextPermutation(int[] nums) {
    //find first non-ascending, i
    //find first > i , j
    //swap i,j
    //reverse [i+1,end]
    int n=nums.length;
    int i=n-1;
    while(i>0 && nums[i-1]>=nums[i]){
        i--;
    }
    i--;
    if(i<0){
        reverse(nums,0,n-1);
        return;
    }
    int j=n-1;
    for( ;j>i; j--){
        if(nums[j]>nums[i]){
            break;
        }
    }
    swap(nums,i,j);
    reverse(nums,i+1,n-1);
}

void reverse(int[] nums, int start, int end){
    while(start<end){
        swap(nums,start++,end--);
    }
}

void swap(int[] nums, int i, int j){
    int temp=nums[i];
    nums[i]=nums[j];
    nums[j]=temp;
}

498. Diagonal Traverse

法一：

easy to think but requires extra space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public int[] findDiagonalOrder(int[][] mat) {
    TreeMap<Integer, LinkedList<Integer>> map=new TreeMap<>();
    int row=mat.length;
    int col=mat[0].length;
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            int idx=i+j;
            map.putIfAbsent(idx,new LinkedList<>());
            if(idx%2==0){
                map.get(idx).addFirst(mat[i][j]);
            }else{
                map.get(idx).add(mat[i][j]);
            }
        }
    }
    int[] res=new int[row*col];
    int i=0;
    for (Integer idx : map.keySet()) {
        for (Integer num : map.get(idx)) {
            res[i++]=num;
        }
    }
    return res;
}

法二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public int[] findDiagonalOrder(int[][] matrix) {
if (matrix == null || matrix.length == 0) return new int[0];

int row = 0, col = 0, pos = 0, m = matrix.length, n=matrix[0].length, output [] = new int[m * n];

for (pos = 0; pos < m * n; pos++) {
    output[pos] = matrix[row][col];

    if ((row + col) % 2 == 0) {
        // The direction is always up when the sum of row & col is even
        
        // For last column, go down
        if (col == n-1) { row++; }                
        
        // For first row & non-last columns, go right
        else if (row == 0) { col++; }
        
        // For not first row & non-last columns, go up and to the right
        else { row--; col++; }

    } else {
        // The direction is always down when the sum of row & col is odd

        // For last row, go right
        if (row == m-1) { col++; } 
        
        //  For non-last row & first column, go down
        else if (col == 0) { row++; }
        
        // For non-last row & non-first column, go down and to the left
        else { row++; col--; }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public int[] findDiagonalOrder(int[][] mat) {
    int row=mat.length;
    int col=mat[0].length;
    int[] res=new int[row*col];
    int i=0;
    int x=0;
    int y=0;
    while(i<row*col){
        res[i++]=mat[x][y];
        if((x+y)%2==0){
            if(y==col-1){
                x++;
            }else if(x==0){
                y++;
            }else{
                x--;
                y++;
            }
        }else{
            if(x==row-1){
                y++;
            }else if(y==0){
                x++;
            }else{
                x++;
                y--;
            }
        }
    }
    return res;
}

581. Shortest Unsorted Continuous Subarray

好题！

https://leetcode.com/problems/shortest-unsorted-continuous-subarray/solution/

Approach 4: Using Stack

two monotonic stacks

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int findUnsortedSubarray(int[] nums) {
    int n=nums.length;
    int l=n;
    int r=0;
    Deque<Integer> stack=new LinkedList<>();
    for (int i = 0; i < n; i++) {
        while(!stack.isEmpty() && nums[i]<nums[stack.peek()]){
            l=Math.min(l,stack.pop());
        }
        stack.push(i);
    }
    stack.clear();
    for (int i = n-1; i >= 0; i--) {
        while(!stack.isEmpty() && nums[i]>nums[stack.peek()]){
            r=Math.max(r,stack.pop());
        }
        stack.push(i);
    }
    return l<r ? r-l+1 : 0;
}

Approach 5: Without Using Extra Space

554. Brick Wall

妙用hashmap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int leastBricks(List<List<Integer>> wall) {
    int n=wall.size();
    Map<Integer,Integer> map=new HashMap<>();
    for (List<Integer> row : wall) {
        int i=0;
        for (int j = 0; j < row.size()-1; j++) {
            int brick=row.get(j);
            i+=brick;
            map.put(i,map.getOrDefault(i,0)+1);
        }
    }
    int max=0;
    for (Integer i : map.keySet()) {
        max=Math.max(max,map.get(i));
    }
    return n-max;
}

611. Valid Triangle Number

花里胡哨，不如brute force

why: nums.length较小，未发挥出优势

Constraints:

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 1000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public int triangleNumber(int[] nums) {
    int n=nums.length;
    int[] arr=new int[1001];
    for (int num : nums) {
        arr[num]++;
    }
    Arrays.sort(nums);
    int res=0;
    for (int i = 1; i <= 1000; i++) {
        if(arr[i]==0){
            continue;
        }
        for (int j = i; j <= 1000; j++) {
            if(arr[j]==0){
                continue;
            }
            for (int k = j; k <= 1000; k++) {
                if(i+j<=k){
                    break;
                }
                if(arr[k]==0){
                    continue;
                }
                if(i==j){
                    if(j==k){
                        res+=arr[i]*(arr[i]-1)*(arr[i]-2)/6;
                    }else{
                        res+=arr[i]*(arr[i]-1)*arr[k]/2;
                    }
                }else if(j==k){
                    res+=arr[i]*arr[j]*(arr[j]-1)/2;
                }else{
                    res+=arr[i]*arr[j]*arr[k];
                }
            }
        }
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int triangleNumber(int[] nums) {
    int n=nums.length;
    Arrays.sort(nums);
    int res=0;
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            for (int k = j+1; k < n; k++) {
                if(nums[i]+nums[j]<=nums[k]){
                    break;
                }
                res++;
            }
        }
    }
    return res;
}

much better!

注意k的定义，同一个i共用一个k,避免重复比较

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int triangleNumber(int[] nums) {
    int n= nums.length;;
    Arrays.sort(nums);
    int res=0;
    for (int i = 0; i < n; i++) {
        if(nums[i]==0){
            continue;
        }
        int k=i+2;
        for (int j = i+1; j < n; j++) {
            while(k<n && nums[i]+nums[j]>nums[k]){
                k++;
            }
            //[j+1,k)
            res+=k-j-1;
        }
    }
    return res;
}

616. Add Bold Tag in String

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public String addBoldTag(String s, String[] words) {
    Arrays.sort(words,(a,b)->(b.length()-a.length()));
    int n=s.length();
    int end=0;  //[i,end) is bold
    boolean[] bold=new boolean[n];
    for (int i = 0; i < n; i++) {
        for (String word : words) {
            if(s.startsWith(word,i)){
                end=Math.max(end,i+word.length());
                break;
            }
        }
        bold[i]=end>i;	//神之一手！
    }
    StringBuilder sb=new StringBuilder();
    for (int i = 0; i < n; i++) {
        if(!bold[i]){
            sb.append(s.charAt(i));
            continue;
        }
        int j=i+1;
        while(j<n && bold[j]){
            j++;
        }
        sb.append("<b>");
        sb.append(s.substring(i,j));
        sb.append("</b>");
        i=j-1;
    }
    return sb.toString();
}

621. Task Scheduler

greedy

hard to think

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int leastInterval(char[] tasks, int n) {
    int[] arr=new int[26];
    int total=tasks.length;
    for (char c : tasks) {
        arr[c-'A']++;
    }
    Arrays.sort(arr);
    int max=arr[25]-1;
    int idle=max*n;
    for (int i = 24; i >= 0; i--) {
        if(arr[i]==0){
            break;
        }
        idle-=Math.min(max,arr[i]);
    }
    return total+Math.max(idle,0);
}

2365. Task Scheduler II

tasks that need to be completed in order

老老实实 simulation

1
2
3
4
5
6
7
8
9
10
11
public long taskSchedulerII(int[] tasks, int space) {
    long t=0;
    Map<Integer,Long> next=new HashMap<>();  //next starting time
    for (int task : tasks) {
        long time=next.containsKey(task) ? next.get(task) : 0;
        t=Math.max(t,time);
        t++;
        next.put(task,t+space);
    }
    return t;
}

769. Max Chunks To Make Sorted

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int maxChunksToSorted(int[] arr) {
    //1 0 2 3 4
    //4 1 2 3 0
    //arr[0,i] should be 0,1,2,...,i
    int count=0;
    int max=0;
    int n=arr.length;
    for (int i = 0; i < n; i++) {
        max=Math.max(max,arr[i]);
        if(i==max){
            count++;
        }
    }
    return count;
}

768. Max Chunks To Make Sorted II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int maxChunksToSorted(int[] arr) {
    int n=arr.length;
    int[] rightMin=new int[n];
    rightMin[n-1]=arr[n-1];
    for (int i = n-2; i >= 0; i--) {
        rightMin[i]=Math.min(rightMin[i+1],arr[i]);
    }
    int res=1;
    int leftMax=0;
    for (int i = 0; i < n-1; i++) {
        leftMax=Math.max(leftMax,arr[i]);
        if(leftMax<=rightMin[i+1]){
            res++;
        }
    }
    return res;
}

658. Find K Closest Elements

蛮力：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public List<Integer> findClosestElements(int[] arr, int k, int x) {
    PriorityQueue<Integer> q=new PriorityQueue<>(new Comparator<Integer>() {
        @Override
        public int compare(Integer a, Integer b) {
            int v1=Math.abs(a-x);
            int v2=Math.abs(b-x);
            return v1==v2 ? a-b : v1-v2;
        }
    });
    for (int num : arr) {
        q.offer(num);
    }
    List<Integer> res=new ArrayList<>();
    int i=0;
    while(i++<k){
        res.add(q.poll());
    }
    Collections.sort(res);
    return res;
}

化劲儿：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public List<Integer> findClosestElements(int[] arr, int k, int x) {
    int low=0;
    int high=arr.length-1;
    while(high-low+1>k){
        if(Math.abs(arr[high]-x)<Math.abs(arr[low]-x)){
            low++;
        }else{
            high--;
        }
    }
    List<Integer> res=new ArrayList<>();
    for(int i=low; i<=high; i++){
        res.add(arr[i]);
    }
    return res;
}

735. Asteroid Collision

stack的妙用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public int[] asteroidCollision(int[] asteroids) {
    int n=asteroids.length;
    Deque<Integer> stack=new LinkedList<>();
    for (int i = 0; i < n; i++) {
        if(asteroids[i]>0){
            stack.push(asteroids[i]);
        }else{
            int val=-asteroids[i];
            while(!stack.isEmpty() && stack.peek()>0 && stack.peek()<val){
                stack.pop();
            }
            if(stack.isEmpty() || stack.peek()<0){
                stack.push(asteroids[i]);
            }else if(stack.peek()==val){
                stack.pop();
            }
        }
    }
    int len=stack.size();
    int[] res=new int[len];
    for (int i = len-1; i >= 0; i--) {
        res[i]=stack.pop();
    }
    return res;
}

274. H-Index

1
2
3
4
5
6
7
8
9
public int hIndex(int[] citations) {
    int n=citations.length;
    Arrays.sort(citations);
    int i=0;
    while(i<n && citations[n-1-i]>=i+1){
        i++;
    }
    return i;
}

630. Course Schedule III

注意：

  • it’s always better to take courses with smaller end time first
  • if unable to take, swap with the longest previous course
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int scheduleCourse(int[][] courses) {
    PriorityQueue<Integer> pq=new PriorityQueue<>((a,b)->(b-a));
    Arrays.sort(courses,(a,b)->(a[1]-b[1]));
    int n=courses.length;
    int time=0;
    for (int i = 0; i < n; i++) {
        int[] c=courses[i];
        if(time+c[0]<=c[1]){
            pq.offer(c[0]);
            time+=c[0];
        }else{
            if(!pq.isEmpty() && pq.peek()>c[0]){
                time+=c[0]-pq.poll();
                pq.offer(c[0]);
            }
        }
    }
    return pq.size();
}