IVN
0%

tag题-2

Posted on Edited on In
Symbols count in article: 24k Reading time ≈ 22 mins.

tag题选编2

632. Smallest Range Covering Elements from K Lists

法一：sliding window

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
public int[] smallestRange(List<List<Integer>> nums) {
    List<int[]> list=new ArrayList<>();
    int k=nums.size();
    for (int i = 0; i < nums.size(); i++) {
        List<Integer> cur=nums.get(i);
        for (int j = 0; j < cur.size(); j++) {
            list.add(new int[]{cur.get(j),i});
        }
    }
    Collections.sort(list,(a,b)->(a[0]-b[0]));
    Map<Integer,Integer> map=new HashMap<>();
    int[] res=new int[2];
    int min=Integer.MAX_VALUE;
    int l=0;
    int r=0;
    //[l,r)
    while(r<list.size()){
        int[] arr=list.get(r++);
        map.put(arr[1],map.getOrDefault(arr[1],0)+1);
        while(map.keySet().size()>=k){
            int[] left=list.get(l);
            if(arr[0]-left[0]<min){
                min=arr[0]-left[0];
                res[1]=arr[0];
                res[0]=left[0];
            }
            map.put(left[1],map.get(left[1])-1);
            if(map.get(left[1])==0){
                map.remove(left[1]);
            }
            l++;
        }
    }
    return res;
}

法二：PriorityQueue

https://leetcode.com/problems/smallest-range-covering-elements-from-k-lists/discuss/104893/Java-Code-using-PriorityQueue.-similar-to-merge-k-array

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
public int[] smallestRange(List<List<Integer>> nums) {
    PriorityQueue<int[]> pq=new PriorityQueue<>((a,b)->(a[0]-b[0]));
    int max=Integer.MIN_VALUE;
    int k=nums.size();
    int start=Integer.MIN_VALUE;
    int dif=Integer.MAX_VALUE;
    for (int i = 0; i < nums.size(); i++) {
        //val, i, j
        pq.offer(new int[]{nums.get(i).get(0),i,0});
        max=Math.max(max,nums.get(i).get(0));
    }

    while(pq.size()==k){
        int[] p=pq.poll();
        if(max-p[0]<dif){
            start=p[0];
            dif=max-p[0];
        }
        if(p[2]+1<nums.get(p[1]).size()){
            p[2]++;
            p[0]=nums.get(p[1]).get(p[2]);
            max=Math.max(max,p[0]);
            pq.offer(p);
        }
    }
    return new int[]{start,start+dif};
}

909. Snakes and Ladders

shortest path请老老实实用bfs，别dfs瞎折腾了！

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 int snakesAndLadders(int[][] board) {
    int n=board.length;
    Deque<Integer> q=new LinkedList<>();
    q.offer(1);
    boolean[] visited=new boolean[n*n+1];
    int move=0;
    while(!q.isEmpty()){
        int size=q.size();
        while(size-->0){
            int cur=q.poll();
            if(cur==n*n){
                return move;
            }
            //int r=n-1-(cur-1)/n;
            //r=n-1: ->
            //r=n-2: <-
            //int c=(r%2!=n%2) ? (cur-1)%n : n-1-(cur-1)%n;
            int min=Math.min(n*n,cur+6);
            for(int next=cur+1; next<=min; next++){
                if(visited[next]){
                    continue;
                }
                visited[next]=true;
                int r=n-1-(next-1)/n;
                int c=(r%2!=n%2) ? (next-1)%n : n-1-(next-1)%n;
                if(board[r][c]!=-1){
                    q.offer(board[r][c]);
                }else{
                    q.offer(next);
                }
            }
        }
        move++;
    }
    return -1;
}

1730. Shortest Path to Get Food

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
public int getFood(char[][] grid) {
    int row=grid.length;
    int col=grid[0].length;
    int[] start=new int[2];
    int[][] d=new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            if(grid[i][j]=='*'){
                start[0]=i;
                start[1]=j;
                break;
            }
        }
    }
    boolean[][] visited=new boolean[row][col];
    PriorityQueue<int[]> pq=new PriorityQueue<>((a,b)->(a[2]-b[2]));
    pq.offer(new int[]{start[0],start[1],0});
    visited[start[0]][start[1]]=true;
    while(!pq.isEmpty()){
        int[] cur=pq.poll();
        if(grid[cur[0]][cur[1]]=='#'){
            return cur[2];
        }
        for (int[] dir : d) {
            int i=cur[0]+dir[0];
            int j=cur[1]+dir[1];
            if(i>=0 && i<row && j>=0 && j<col
                    && grid[i][j]!='X' && !visited[i][j]){
                pq.offer(new int[]{i,j,cur[2]+1});
                visited[i][j]=true;
            }
        }
    }
    return -1;
}

1856. Maximum Subarray Min-Product

直接法（考察每个区间）走不通，考虑间接法（考察每个元素）

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
//直接法pass 10/42, 有bug
/*    public int maxSumMinProduct(int[] nums) {
        long sum=0;
        TreeMap<Integer,Integer> map=new TreeMap<>();
        for (int num : nums) {
            sum+=num;
            map.put(num,map.getOrDefault(num,0)+1);
        }
        int min=map.firstKey();
        long p=sum*min;
        int n=nums.length;
        int l=0;
        int r=n-1;
        while(l<r){
            if(chooseLeft(l,r,nums)){
                sum-=nums[l];
                map.put(nums[l],map.get(nums[l])-1);
                if(map.get(nums[l])==0){
                    map.remove(nums[l]);
                }
                l++;
            }else{
                sum-=nums[r];
                map.put(nums[r],map.get(nums[r])-1);
                if(map.get(nums[r])==0){
                    map.remove(nums[r]);
                }
                r--;
            }
            min=map.firstKey();
            p=Math.max(p,sum*min);
        }
        return (int)p%((int)1e9+7);
    }

    boolean chooseLeft(int l, int r, int[] nums){
        while(l<r && nums[l]==nums[r]){
            l++;
            r--;
        }
        return nums[l]-nums[r]<=0;
    }*/
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
public int maxSumMinProduct(int[] nums) {
    int n=nums.length;
    int[] left=new int[n];// next smaller element on left
    int[] right=new int[n];//next smaller element on right
    Deque<Integer> stack=new LinkedList<>();
    stack.push(0);
    for (int i = 1; i < n; i++) {
        while(!stack.isEmpty() && nums[i]<=nums[stack.peek()]){
            stack.pop();
        }
        if(!stack.isEmpty()){
            left[i]=stack.peek()+1;
        }
        stack.push(i);
    }
    stack.clear();
    stack.push(n-1);
    Arrays.fill(right,n-1);
    for (int i = n-2; i >= 0; i--) {
        while(!stack.isEmpty() && nums[i]<=nums[stack.peek()]){
            stack.pop();
        }
        if(!stack.isEmpty()){
            right[i]=stack.peek()-1;
        }
        stack.push(i);
    }
    long[] prefix=new long[n];
    prefix[0]=nums[0];
    for (int i = 1; i < n; i++) {
        prefix[i]=prefix[i-1]+nums[i];
    }
    long max=0;
    int mod=(int)1e9+7;
    for (int i = 0; i < n; i++) {
        int l=left[i];
        int r=right[i];
        //[l,r] = prefix[r] - prefix[l-1]
        long sum=l-1>=0 ? prefix[r]-prefix[l-1] : prefix[r];
        max=Math.max(max,sum*nums[i]);
    }
    return (int)(max%mod);
}

1041. Robot Bounded In Circle

https://leetcode.com/problems/robot-bounded-in-circle/discuss/290856/JavaC%2B%2BPython-Let-Chopper-Help-Explain

只需考察终点坐标和终点的方向

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
public boolean isRobotBounded(String instructions) {
    int x=0;
    int y=0;
    int[][] dirs=new int[][]{{0,1},{1,0},{0,-1},{-1,0}};
    int idx=0;
    for (int i = 0; i < instructions.length(); i++) {
        char c=instructions.charAt(i);
        switch (c){
            case 'G':
                x+=dirs[idx][0];
                y+=dirs[idx][1];
                break;
            case 'L':
                idx--;
                if(idx<0){
                    idx=3;
                }
                break;
            default:
                idx++;
                if(idx>=4){
                    idx=0;
                }
        }
    }
    return x==0 && y==0 || idx!=0;
}

1834. Single-Threaded CPU

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[] getOrder(int[][] tasks) {
    //non preemptive SJF
    int n=tasks.length;
    List<int[]> list=new ArrayList<>();
    for (int i = 0; i < n; i++) {
        //enqueueTime, processingTime, idx
        list.add(new int[]{tasks[i][0],tasks[i][1],i});
    }
    //list of task arrival
    Collections.sort(list,(a,b)->(a[0]-b[0]));
    //waiting list of tasks
    PriorityQueue<int[]> waiting=new PriorityQueue<>((a,b)->(a[1]!=b[1] ? a[1]-b[1] : a[2]-b[2]));
    int idx=0;
    int curTime=0;
    int[] res=new int[n];
    int i=0;
    while(idx<n || !waiting.isEmpty()){
        //when idle, update time to accept new task(s)
        if(waiting.isEmpty() && list.get(idx)[0]>curTime){
            curTime=list.get(idx)[0];
        }
        //add all arrived tasks to waiting queue
        while(idx<n && list.get(idx)[0]<=curTime){
            waiting.offer(list.get(idx++));
        }
        int[] next=waiting.poll();
        curTime+=next[1];
        res[i++]=next[2];
    }
    return res;
}

1091. Shortest Path in Binary Matrix

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
public int shortestPathBinaryMatrix(int[][] grid) {
    int n=grid.length;
    int[][] dirs=new int[][]{{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
    Deque<int[]> q=new LinkedList<>();
    int depth=1;
    if(grid[0][0]==0){
        q.offer(new int[]{0,0});
        grid[0][0]=1;
    }
    while(!q.isEmpty()){
        int size=q.size();
        while(size-->0){
            int[] cur=q.poll();
            if(cur[0]==n-1 && cur[1]==n-1){
                return depth;
            }
            for (int[] dir : dirs) {
                int i=cur[0]+dir[0];
                int j=cur[1]+dir[1];
                if(i>=0 && i<n && j>=0 && j<n && grid[i][j]==0){
                    q.offer(new int[]{i,j});
                    grid[i][j]=1;
                }
            }
        }
        depth++;
    }
    return -1;
}

688. Knight Probability in Chessboard

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Map<String,Double> memo=new HashMap<>();
int[][] dirs=new int[][]{{1,2},{2,1},{-1,2},{-2,1},{1,-2},{2,-1},{-1,-2},{-2,-1}};
public double knightProbability(int n, int k, int row, int column) {
    if(row<0 || row>=n || column<0 || column>=n){
        return 0;
    }
    if(k==0){
        return 1;
    }
    //stupid memo
    String s=row+","+column+","+k;
    if(memo.containsKey(s)){
        return memo.get(s);
    }
    double res=0;
    for (int[] dir : dirs) {
        int i=row+dir[0];
        int j=column+dir[1];
        res+=knightProbability(n,k-1,i,j);
    }
    res/=8;
    memo.put(s,res);
    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
Map<Integer,Double> memo=new HashMap<>();
int[][] dirs=new int[][]{{1,2},{2,1},{-1,2},{-2,1},{1,-2},{2,-1},{-1,-2},{-2,-1}};
public double knightProbability(int n, int k, int row, int column) {
    if(row<0 || row>=n || column<0 || column>=n){
        return 0;
    }
    if(k==0){
        return 1;
    }
    //smarter, a little bit faster
    int s=k+row*101+column*101*25;
    if(memo.containsKey(s)){
        return memo.get(s);
    }
    double res=0;
    for (int[] dir : dirs) {
        int i=row+dir[0];
        int j=column+dir[1];
        res+=knightProbability(n,k-1,i,j);
    }
    res/=8;
    memo.put(s,res);
    return res;
}

1405. Longest Happy 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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
public String longestDiverseString(int a, int b, int c) {
    PriorityQueue<Pair<Integer,Character>> pq=new PriorityQueue<>((p1,p2)->p2.getKey()-p1.getKey());
    if(a>0){
        pq.offer(new Pair<>(a,'a'));
    }
    if(b>0){
        pq.offer(new Pair<>(b,'b'));
    }
    if(c>0){
        pq.offer(new Pair<>(c,'c'));
    }
    if(pq.isEmpty()){
        return "";
    }
    StringBuilder sb=new StringBuilder();
    while(pq.size()>=2){
        Pair<Integer,Character> first=pq.poll();
        Pair<Integer,Character> second=pq.poll();
        int v1=first.getKey();
        char c1=first.getValue();
        if(v1>=2){
            sb.append(c1);
            sb.append(c1);
            v1-=2;
        }else{
            sb.append(c1);
            v1--;
        }
        int v2=second.getKey();
        char c2=second.getValue();
        //only if secondLarge >= Large, append 2
        if(v2>=2 && v2>=first.getKey()){
            sb.append(c2);
            sb.append(c2);
            v2-=2;
        }else{
            sb.append(c2);
            v2--;
        }
        if(v1>0){
            pq.offer(new Pair<>(v1,c1));
        }
        if(v2>0){
            pq.offer(new Pair<>(v2,c2));
        }
    }
    if(pq.size()==1){
        Pair<Integer,Character> pair=pq.poll();
        int v=pair.getKey();
        char c1=pair.getValue();
        int max=Math.min(v,2);
        while(max-->0){
            sb.append(c1);
        }
    }
    return sb.toString();
}

2158. Amount of New Area Painted Each Day

https://leetcode.com/problems/amount-of-new-area-painted-each-day/discuss/1784268/Java-TreeMap-%2B-Merge-Intervals-Easy-to-Understand-Beats-95.83

思路：

  • 区间左闭右开

  • 妙用floorEntry 和 ceilingEntry

  • 其中floorEntry(start) 只需用一次，考察largest key <= start的区间即可

  • ceilingEntry(start) 可能使用多次，必须去除所有overlap的区间, 直到ceilingEntry(start)> end

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[] amountPainted(int[][] paint) {
    int n=paint.length;
    int[] res=new int[n];
    //[start,end)
    TreeMap<Integer,Integer> map=new TreeMap<>();
    for (int i = 0; i < n; i++) {
        int[] arr=paint[i];
        int start=arr[0];
        int end=arr[1];
        int toPaint=end-start;
        Integer floor = map.floorKey(arr[0]);
        if(floor!=null){
            int e=map.get(floor);
            if(e>=end){
                continue;
            }
            //[start,end)
            //[floor,e)
            if(e>=start){
                toPaint-=Math.min(end,e)-start;
                map.remove(floor);
                start=floor;
            }
        }
        Integer ceil=map.ceilingKey(arr[0]);
        while(ceil!=null && ceil<=end){
            //[start,end)
            //[ceil,e)
            int e=map.get(ceil);
            toPaint-=Math.min(end,e)-ceil;
            end=Math.max(end,e);
            map.remove(ceil);
            ceil=map.ceilingKey(arr[0]);
        }
        map.put(start,end);
        res[i]=toPaint;
    }
    return res;
}

2162. Minimum Cost to Set Cooking Time

难点在于理解题意，读懂了直接干就好

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 minCostSetTime(int startAt, int moveCost, int pushCost, int targetSeconds) {
    int min=targetSeconds/60;
    int sec=targetSeconds%60;
    return Math.min(cost(startAt,moveCost,pushCost,min,sec)
            ,cost(startAt,moveCost,pushCost,min-1,sec+60));
}

int cost(int startAt, int moveCost, int pushCost, int min, int sec){
    if(min<0 || min>99 || sec<0 || sec>99){
        return Integer.MAX_VALUE;
    }
    int res=0;
    char cur=(char)(startAt+'0');
    char[] arr=Integer.toString(min*100+sec).toCharArray();
    for (int i = 0; i < arr.length; i++) {
        char c=arr[i];
        if(c==cur){
            res+=pushCost;
        }else{
            cur=c;
            res+=moveCost+pushCost;
        }
    }
    return res;
}

1101. The Earliest Moment When Everyone Become Friends

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
47
48
49
50
51
52
public int earliestAcq(int[][] logs, int n) {
    UnionFind u=new UnionFind(n);
    Arrays.sort(logs,(a,b)->(a[0]-b[0]));
    for (int[] log : logs) {
        int a=log[1];
        int b=log[2];
        u.union(a,b);
        if(u.total==1){
            return log[0];
        }
    }
    return -1;
}

class UnionFind{
    int[] parent;
    int[] size;
    int total;

    UnionFind(int n){
        parent=new int[n];
        size=new int[n];
        total=n;
        for (int i = 0; i < n; i++) {
            parent[i]=i;
            size[i]=1;
        }
    }

    int find(int i){
        while(i!=parent[i]){
            i=parent[i];
        }
        return i;
    }

    void union(int a, int b){
        int rootA=find(a);
        int rootB=find(b);
        if(rootA==rootB){
            return;
        }
        if(size[rootA]>=size[rootB]){
            size[rootA]+=size[rootB];
            parent[rootB]=rootA;
        }else{
            size[rootB]+=size[rootA];
            parent[rootA]=rootB;
        }
        total--;
    }
}

2018. Check if Word Can Be Placed In Crossword

依然是理解题意后蛮干，考察每个可能起点的所有方向

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 boolean placeWordInCrossword(char[][] board, String word) {
    int row= board.length;
    int col= board[0].length;
    int[][] dirs=new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
    char[] chars=word.toCharArray();
    int n=chars.length;
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            if(board[i][j]==' ' || board[i][j]==chars[0]){
                for (int[] dir : dirs) {
                    if(atBound(board,row,col,i-dir[0],j-dir[1])){
                        int idx=1;
                        int x=i+dir[0];
                        int y=j+dir[1];
                        for(; idx<n; idx++){
                            if(atBound(board,row,col,x,y) ||
                                    board[x][y]!=' ' && board[x][y]!=chars[idx]){
                                break;
                            }
                            x+=dir[0];
                            y+=dir[1];
                        }
                        if(idx==n && atBound(board,row,col,x,y)){
                            return true;
                        }
                    }
                }
            }
        }
    }
    return false;
}

boolean atBound(char[][] board,int row, int col, int i, int j){
    if(i<0 || i>=row || j<0 || j>=col || board[i][j]=='#'){
        return true;
    }
    return false;
}

2013. Detect Squares

https://leetcode.com/problems/detect-squares/discuss/1471958/C%2B%2BJavaPython-2-approaches-using-HashMap-with-Picture-Clean-and-Concise

找对角！

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
class DetectSquares {

    int[][] arr;
    List<int[]> list;
    public DetectSquares() {
        arr=new int[1001][1001]; //[0,1000]
        list=new ArrayList<>();
    }

    public void add(int[] point) {
        int x=point[0];
        int y=point[1];
        if(arr[x][y]==0){
            list.add(point);
        }
        arr[x][y]++;
    }

    public int count(int[] point) {
        int x1=point[0];
        int y1=point[1];
        int res=0;
        for (int[] p : list) {
            int x3=p[0];
            int y3=p[1];
            //secondary diagonal : x1-x3=y1-y3
            //main diagonal : x1-x3=y3-y1
            if(x3==x1 || Math.abs(x1-x3)!=Math.abs(y1-y3)){
                continue;
            }
            //(x1,y3)   (x3,y1)
            res+=arr[x1][y3]*arr[x3][y1]*arr[x3][y3];
        }
        return res;
    }
}

408. Valid Word Abbreviation

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 boolean validWordAbbreviation(String word, String abbr) {
    int i=0;
    int j=0;
    char[] arr1=word.toCharArray();
    char[] arr2=abbr.toCharArray();
    a:while(i<arr1.length && j<arr2.length){
        while(i<arr1.length && j<arr2.length && arr1[i]==arr2[j]){
            i++;
            j++;
            //雷点1：注意及时break,避免进入下面的false判断
            if(i>=arr1.length || j>=arr2.length){
                break a;
            }
        }
        int num=0;
        while(j<arr2.length && Character.isDigit(arr2[j])){
            //雷点2：需禁止leading 0
            if(num==0 && arr2[j]=='0'){
                return false;
            }
            num*=10;
            num+=arr2[j]-'0';
            j++;
        }
        //雷点3：当不匹配且无快进时，判断false
        if(num!=0){
            i+=num;
        }else{
            return false;
        }
    }
    return i==arr1.length && j==arr2.length;
}

2184. Number of Ways to Build Sturdy Brick Wall

难！难！难！

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
Integer[][] dp;
int height;
int width;
int mod=(int)1e9+7;
public int buildWall(int height, int width, int[] bricks) {
    dp=new Integer[height+1][1<<width];
    this.height=height;
    this.width=width;
    //fill from top to bottom
    return dp(bricks,height,0,0,0);
}

private int dp(int[] bricks, int curHeight, int curWidth, int cur, int prev){
    if(dp[curHeight][prev]!=null){
        return dp[curHeight][prev];
    }
    if(curHeight==0){
        return 1;
    }
    if(curWidth==width){
        return dp(bricks,curHeight-1,0,0,cur);
    }
    int ans=0;
    for (int brick : bricks) {
        int sz=curWidth+brick;
        //can not align except at the end
        int nc=sz<width ?  cur | 1<<sz : cur;
        if(sz>width || (nc&prev)!=0){
            continue;
        }
        ans=(ans+dp(bricks,curHeight,sz,nc,prev))%mod;
    }
    return curWidth==0 ? dp[curHeight][prev]=ans : ans;
}

921. Minimum Add to Make Parentheses Valid

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int minAddToMakeValid(String s) {
    int res=0;
    int cur=0;
    for (int i = 0; i < s.length(); i++) {
        char c=s.charAt(i);
        if(c=='('){
            cur++;
        }else{
            cur--;
        }
        if(cur<0){
            res++;
            cur=0;
        }
    }
    res+=cur;
    return res;
}

636. Exclusive Time of Functions

stack + wrapper class

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
public int[] exclusiveTime(int n, List<String> logs) {
    int[] res=new int[n];
    Deque<Log> stack=new LinkedList<>();
    for (String s : logs) {
        Log log=new Log(s);
        if(log.isStart){
            stack.push(log);
        }else{
            Log top=stack.pop();
            res[top.id]+=log.t-top.t+1;
            if(!stack.isEmpty()){
                res[stack.peek().id]-=log.t-top.t+1;
            }
        }
    }
    return res;
}

private class Log{
    int id;
    boolean isStart;
    int t;

    Log(String s){
        String[] split = s.split(":");
        id=Integer.valueOf(split[0]);
        t=Integer.valueOf(split[2]);
        isStart=split[1].equals("start");
    }
}

987. Vertical Order Traversal of a Binary Tree

老朋友

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
public List<List<Integer>> verticalTraversal(TreeNode root) {
    TreeMap<Integer,List<Integer>> map=new TreeMap<>();
    Deque<Pair<Integer,TreeNode>> q=new LinkedList<>();
    q.offer(new Pair<>(0,root));
    while(!q.isEmpty()){
        int size=q.size();
        Map<Integer,List<Integer>> sub=new HashMap<>();
        while(size-->0){
            Pair<Integer, TreeNode> cur = q.poll();
            int idx=cur.getKey();
            TreeNode node=cur.getValue();
            sub.putIfAbsent(idx,new ArrayList<>());
            sub.get(idx).add(node.val);
            if(node.left!=null){
                q.offer(new Pair<>(idx-1,node.left));
            }
            if(node.right!=null){
                q.offer(new Pair<>(idx+1,node.right));
            }
        }
        for (Integer i : sub.keySet()) {
            List<Integer> l=sub.get(i);
            Collections.sort(l);
            for (Integer num : l) {
                map.putIfAbsent(i,new ArrayList<>());
                map.get(i).add(num);
            }
        }
    }
    List<List<Integer>> res=new ArrayList<>(map.values());
    return res;
}

1424. Diagonal Traverse II

TLE: 53/56

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int[] findDiagonalOrder(List<List<Integer>> nums) {
    int n=0;
    for (List<Integer> num : nums) {
        n+=num.size();
    }
    int[] res=new int[n];
    int idx=0;
    int i=0;
    int j=0;
    while(idx<n){
        if(nums.size()>i && nums.get(i).size()>j){
            res[idx++]=nums.get(i).get(j);
        }
        if(i==0){
            i=i+j+1;
            j=0;
        }else{
            i--;
            j++;
        }
    }
    return res;
}

Bucket:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int[] findDiagonalOrder(List<List<Integer>> nums) {
    TreeMap<Integer,List<Integer>> map=new TreeMap<>();
    int n=0;
    for (int i = nums.size()-1; i >=0; i--) {
        List<Integer> list=nums.get(i);
        n+=list.size();
        for (int j = 0; j < list.size(); j++) {
            map.putIfAbsent(i+j,new ArrayList<>());
            map.get(i+j).add(list.get(j));
        }
    }
    int[] res=new int[n];
    int idx=0;
    for (Integer i : map.keySet()) {
        for (Integer num : map.get(i)) {
            res[idx++]=num;
        }
    }
    return res;
}

689. Maximum Sum of 3 Non-Overlapping Subarrays

反思：

  • dp数组不用追求极致的最优，不必增加无谓的思考复杂度
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
47
48
49
public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
    int[] res=new int[3];
    int n=nums.length;
    int[] sum=new int[n+1];
    for (int i = 0; i < n; i++) {
        //[0,i-1]
        sum[i+1]=sum[i]+nums[i];
    }
    //[0,k-1] [k,n-k-1] [n-k,n-1]
    int[] leftMax=new int[n];
    for(int i=k,tot=sum[k]-sum[0]; i<n; i++){
        //[i-k+1,i]
        int cur=sum[i+1]-sum[i-k+1];
        if(cur>tot){
            tot=cur;
            leftMax[i]=i-k+1;
        }else{
            leftMax[i]=leftMax[i-1];
        }
    }
    int[] rightMax=new int[n];
    rightMax[n-k]=n-k;
    for(int i=n-k-1, tot=sum[n]-sum[n-k]; i>=0; i--){
        //[i,i+k-1]
        int cur=sum[i+k]-sum[i];
        if(cur>=tot){
            tot=cur;
            rightMax[i]=i;
        }else{
            rightMax[i]=rightMax[i+1];
        }
    }
    int maxSum=0;
    for(int i=k; i<=n-2*k; i++){
        //[i,i+k-1]
        int s=sum[i+k]-sum[i];
        int l=leftMax[i-1];//[l,l+k-1]
        int left=sum[l+k]-sum[l];
        int r=rightMax[i+k];
        int right=sum[r+k]-sum[r];
        if(left+s+right>maxSum){
            res[0]=l;
            res[1]=i;
            res[2]=r;
            maxSum=left+s+right;
        }
    }
    return res;
}

173. Binary Search Tree Iterator

Follow up:

  • Could you implement next() and hasNext() to run in average O(1) time and use O(h) memory, where h is the height of the tree?

思路：

  1. push左左左到底
  2. 每当pop时，以pop.right为起点，push左左左到底
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class BSTIterator {
    Deque<TreeNode> stack;
    public BSTIterator(TreeNode root) {
        stack=new LinkedList<>();
        pushAll(root);
    }

    public int next() {
        TreeNode top=stack.pop();
        pushAll(top.right);
        return top.val;
    }

    public boolean hasNext() {
        return !stack.isEmpty();
    }

    private void pushAll(TreeNode node){
        while(node!=null){
            stack.push(node);
            node=node.left;
        }
    }
}

1386. Cinema Seat Allocation

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
public int maxNumberOfFamilies(int n, int[][] reservedSeats) {
    TreeMap<Integer, Set<Integer>> map=new TreeMap<>();
    for (int[] arr : reservedSeats) {
        int i=arr[0];
        int j=arr[1];
        map.putIfAbsent(i,new HashSet<>());
        map.get(i).add(j);
    }
    int res=0;
    int row=0;
    for (Integer i : map.keySet()) {
        res+=(i-1-row)*2;
        row=i;
        Set<Integer> set = map.get(i);
        if(set.contains(4) || set.contains(5)){
            if(set.contains(6) || set.contains(7) || set.contains(8) || set.contains(9)){
                continue;
            }
            res++;
            continue;
        }
        if(set.contains(6) || set.contains(7)){
            if(set.contains(2) || set.contains(3) || set.contains(4) || set.contains(5)){
                continue;
            }
            res++;
            continue;
        }
        if(set.contains(2) || set.contains(3) || set.contains(8) || set.contains(9)){
            res+=1;
        }else{
            res+=2;
        }
    }
    res+=(n-row)*2;
    return res;
}

1615. Maximal Network Rank

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
public int maximalNetworkRank(int n, int[][] roads) {
    int res=0;
    Map<Integer, Set<int[]>> map=new HashMap<>();
    for (int[] road : roads) {
        int a=road[0];
        int b=road[1];
        map.putIfAbsent(a,new HashSet<>());
        map.putIfAbsent(b,new HashSet<>());
        map.get(a).add(road);
        map.get(b).add(road);
    }
    for (int i = 0; i < n; i++) {
        if(!map.containsKey(i)){
            continue;
        }
        for (int j = i+1; j < n; j++) {
            if(!map.containsKey(j)){
                continue;
            }
            int count=map.get(i).size();
            for (int[] arr : map.get(j)) {
                if(!map.get(i).contains(arr)){
                    count++;
                }
            }
            res=Math.max(res,count);
        }
    }
    return res;
}

1775. Equal Sum Arrays With Minimum Number of Operations

Greedy，而非DP <= 并不具有optimal substructure

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 minOperations(int[] nums1, int[] nums2) {
    int sum1=Arrays.stream(nums1).sum();
    int sum2=Arrays.stream(nums2).sum();
    if(sum1==sum2){
        return 0;
    }
    if(sum1<sum2){
        return min(nums1,nums2,sum1,sum2);
    }
    return min(nums2,nums1,sum2,sum1);
}

private int min(int[] nums1, int[] nums2, int sum1, int sum2){
    int dif=sum2-sum1;
    int[] cnt=new int[6];
    for (int n : nums1) {
        //increase num1 as far as possible
        cnt[6-n]++;
    }
    for (int n : nums2) {
        //decrease num2 as far as possible
        cnt[n-1]++;
    }
    int res=0;
    for(int i=5; i>0 && dif>0; i--){
        int take=Math.min(cnt[i],dif/i + (dif%i==0 ? 0 : 1));
        dif-=take*i;
        res+=take;
    }
    return dif>0 ? -1 : res;
}