IVN
0%

Array-3

Posted on Edited on In
Symbols count in article: 23k Reading time ≈ 21 mins.

Array选编（3）

163. Missing Ranges

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 List<String> findMissingRanges(int[] nums, int lower, int upper) {
    List<String> res=new ArrayList<>();
    int n=nums.length;
    int curStart=lower;
    for (int i = 0; i < n; i++) {
        if(curStart==nums[i]){
            curStart=nums[i]+1;
        }else{
            //curStart<nums[i]
            //[curStart,nums[i]-1]
            int end=nums[i]-1;
            if(curStart==end){
                res.add(curStart+"");
            }else{
                res.add(curStart+"->"+end);
            }
            curStart=nums[i]+1;
        }
    }
    if(curStart<upper){
        res.add(curStart+"->"+upper);
    }
    if(curStart==upper){
        res.add(curStart+"");
    }
    return res;
}

238. Product of Array Except Self

You must write an algorithm that runs in O(n) time and without using the division operation.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int[] productExceptSelf(int[] nums) {
    int n=nums.length;
    int[] fromLeft=new int[n];
    int[] fromRight=new int[n];
    fromLeft[0]=nums[0];
    for (int i = 1; i < n; i++) {
        fromLeft[i]=fromLeft[i-1]*nums[i];
    }
    fromRight[n-1]=nums[n-1];
    for (int i = n-2; i >= 0; i--) {
        fromRight[i]=fromRight[i+1]*nums[i];
    }
    int[] res=new int[n];
    res[0]=fromRight[1];
    res[n-1]=fromLeft[n-2];
    for (int i = 1; i < n-1; i++) {
        res[i]=fromLeft[i-1]*fromRight[i+1];
    }
    return res;
}

Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int[] productExceptSelf(int[] nums) {
    int n=nums.length;
    //[0,i-1] [i+1,n-1]
    int[] res=new int[n];
    res[n-1]=1;
    for (int i = n-2; i >= 0; i--) {
        res[i]=nums[i+1]*res[i+1];
    }
    int fromLeft=1;
    for (int i = 0; i < n; i++) {
        res[i]*=fromLeft;
        fromLeft*=nums[i];
    }
    return res;
}

1383. Maximum Performance of a Team

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 maxPerformance(int n, int[] speed, int[] efficiency, int k) {
    int mod=(int)1e9+7;
    int[][] arr=new int[n][2];
    for (int i = 0; i < n; i++) {
        arr[i][0]=efficiency[i];
        arr[i][1]=speed[i];
    }
    Arrays.sort(arr,(a,b)->(b[0]-a[0]));
    PriorityQueue<Integer> pq=new PriorityQueue<>();
    long max=0;
    long sum=0;
    for (int i = 0; i < n; i++) {
        int[] cur=arr[i];
        int curEff=cur[0];
        int curSpeed=cur[1];
        sum+=curSpeed;
        pq.offer(curSpeed);
        if(pq.size()>k){
            sum-=pq.poll();
        }
        max=Math.max(max,sum*curEff);
    }
    return (int)(max%mod);
}

1710. Maximum Units on a Truck

1
2
3
4
5
6
7
8
9
10
11
12
public int maximumUnits(int[][] boxTypes, int truckSize) {
    Arrays.sort(boxTypes,(a,b)->(b[1]-a[1]));
    int res=0;
    for (int[] box : boxTypes) {
        while(truckSize>0 && box[0]>0){
            res+=box[1];
            box[0]--;
            truckSize--;
        }
    }
    return res;
}

2055. Plates Between Candles

新知识：

  • TreeMap.ceilingKey()
  • TreeMap.floorKey()
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[] platesBetweenCandles(String s, int[][] queries) {
    int n=queries.length;
    int[] res=new int[n];
    TreeMap<Integer,Integer> map=new TreeMap<>();
    int idx=0;
    for (int i = 0; i < s.length(); i++) {
        if(s.charAt(i)=='|'){
            map.put(i,idx++);
        }
    }
    for (int i = 0; i < n; i++) {
        int start=queries[i][0];
        int end=queries[i][1];
        Integer left=map.ceilingKey(start);
        Integer right=map.floorKey(end);
        if(left==null || right==null || left>=right){
            res[i]=0;
        }else{
            res[i]=right-left-(map.get(right)-map.get(left));
        }
    }
    return res;
}

2104. Sum of Subarray Ranges

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public long subArrayRanges(int[] nums) {
    int n=nums.length;
    long res=0;
    for (int i = 0; i < n; i++) {
        int min=nums[i];
        int max=nums[i];
        for (int j = i+1; j < n; j++) {
            min=Math.min(min,nums[j]);
            max=Math.max(max,nums[j]);
            res+=max-min;
        }
    }
    return res;
}

https://leetcode.com/problems/sum-of-subarray-ranges/discuss/1624222/JavaC%2B%2BPython-O(n)-solution-detailed-explanation

https://leetcode.com/problems/sum-of-subarray-minimums/solution/

三步走：

  1. In the given range, find the count of subarrays which contain 2

    [3,4,5,2,3,4]

  2. how to get the range in which each element is the smallest

    1. find the nearest element on the left, which is less than itself

    2. find the closest element on the right, which is less than itself.

      [i+1,j-1]

  3. edge case: duplicate elements

    1. look for elements that are strictly less than the current element on the left.
    2. look for the elements which are less than or equal to the current element

2214. Minimum Health to Beat Game

binary search？杀鸡焉用牛刀！

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
public long minimumHealth(int[] damage, int armor) {
    Arrays.sort(damage);
    long left=0;
    long right=(long)1e10+1;
    int n=damage.length;
    while(left<right){
        long mid=(left+right)/2;
        long hp=mid;
        for (int i = 0; i < n; i++) {
            if(i==n-1){
                hp-=Math.max(damage[i]-armor,0);
            }else{
                hp-=damage[i];
            }
            if(hp<=0){
                break;
            }
        }
        if(hp<=0){
            left=mid+1;
        }else{
            right=mid;
        }
    }
    return left;
}
1
2
3
4
5
6
7
8
9
public long minimumHealth(int[] damage, int armor) {
    long res=0;
    int maxD=0;
    for (int d : damage) {
        res+=d;
        maxD=Math.max(d,maxD);
    }
    return res-Math.min(armor,maxD)+1;
}

2221. Find Triangular Sum of an Array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int triangularSum(int[] nums) {
    int n=nums.length;
    List<Integer> list=new ArrayList<>();
    for (int i = 0; i < n; i++) {
        list.add(nums[i]);
    }
    while(list.size()>1){
        List<Integer> next=new ArrayList<>();
        for (int i = 0; i < list.size()-1; i++) {
            next.add((list.get(i)+list.get(i+1))%10);
        }
        list=next;
    }
    return list.get(0);
}

2272. Substring With Largest Variance

https://leetcode.com/problems/substring-with-largest-variance/discuss/2038222/Kadanes-algorithm-solution-(Java)

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
public int largestVariance(String s) {
    int n=s.length();
    char[] chars = s.toCharArray();
    int[] arr=new int[26];
    for (int i = 0; i < n; i++) {
        arr[chars[i]-'a']++;
    }
    int res=0;
    int curA,curB,resB; //max(A-B),B>0
    for (int i = 0; i < 26; i++) {
        if(arr[i]==0){
            continue;
        }
        for (int j = 0; j < 26; j++) {
            if(j==i || arr[j]==0){
                continue;
            }
            curA=0;
            curB=0;
            resB=arr[j];
            for (int t = 0; t < n; t++) {
                int cur=chars[t]-'a';
                if(cur!=i && cur!=j){
                    continue;
                }
                if(cur==i){
                    curA++;
                }
                if(cur==j){
                    curB++;
                    resB--;
                }
                if(curB>0){
                    res=Math.max(res,curA-curB);
                }
                if(curA-curB<0 && resB>0){
                    curA=0;
                    curB=0;
                }
            }
        }
    }
    return res;
}

2281. Sum of Total Strength of Wizards

brute force (still TLE)

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[] nums;

   public int totalStrength(int[] strength) {
       this.nums=strength;

       int n=strength.length;
       long res=0;
       for (int i = 0; i < n; i++) {
           for (int j = 0; j <= i; j++) {
               res+=strength(j,i);
           }
       }
       int r=(int)(res%((int)Math.pow(10,9)+7));
       return r;
   }

   long strength(int start,int end){

       int min=Integer.MAX_VALUE;
       int sum=0;
       for (int i = start; i <= end; i++) {
           min=Math.min(min,nums[i]);
           sum+=nums[i];
       }
       long res=min*sum;

       return res;
   }

prefix sum (still TLE)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int totalStrength(int[] strength) {
    int n=strength.length;
    long[] prefix=new long[n];
    prefix[0]=strength[0];  //[0,i]
    for (int i = 1; i < n; i++) {
        prefix[i]=prefix[i-1]+strength[i];
    }
    int min;
    long sum;
    long res=0;
    for (int i = 0; i < n; i++) {
        min=strength[i];
        for (int j = i; j >= 0; j--) {
            min=Math.min(min,strength[j]);
            //[j,i] = [0,i] -[0,j-1]
            sum=j==0 ? prefix[i] : prefix[i]-prefix[j-1];
            res+=sum*min;
        }
    }
    res%=(int)1e9+7;
    return (int)res;
}

monotonic stack

https://leetcode.com/problems/sum-of-total-strength-of-wizards/discuss/2061985/JavaC%2B%2BPython-One-Pass-Solution

1074. Number of Submatrices That Sum to Target

法一：

暴力，很慢

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
int row;
int col;
long[][] sum;
public int numSubmatrixSumTarget(int[][] matrix, int target) {
    //sum(x1,y1,x2,y2)=rect(x2,y2)-rect(x2,y1-1)
    // -rect(x1-1,y2)+rect(x1-1,y1-1)
    row=matrix.length;
    col=matrix[0].length;
    sum=new long[row][col];
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            sum[i][j]=sum(i-1,j)+sum(i,j-1)+matrix[i][j]-sum(i-1,j-1);
        }
    }
    int res=0;
    for (int x2 = 0; x2 < row; x2++) {
        for (int y2 = 0; y2 < col; y2++) {
            for (int x1 = 0; x1 <= x2; x1++) {
                for (int y1 = 0; y1 <= y2; y1++) {
                    long s=sum(x2,y2)-sum(x2,y1-1)-sum(x1-1,y2)+sum(x1-1,y1-1);
                    if(s==target){
                        res++;
                    }
                }
            }
        }
    }
    return res;
}

private long sum(int x, int y){
    if(x<0 || y<0){
        return 0;
    }
    return sum[x][y];
}

法二：

转换，快多了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int numSubmatrixSumTarget(int[][] A, int target) {
            int res = 0, m = A.length, n = A[0].length;
    for (int i = 0; i < m; i++)
        for (int j = 1; j < n; j++)
            A[i][j] += A[i][j - 1];
    Map<Integer, Integer> counter = new HashMap<>();
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            counter.clear();
            counter.put(0, 1);
            int cur = 0;
            for (int k = 0; k < m; k++) {
                cur += A[k][j] - (i > 0 ? A[k][i - 1] : 0);
                res += counter.getOrDefault(cur - target, 0);
                counter.put(cur, counter.getOrDefault(cur, 0) + 1);
            }
        }
    }
    return res;
}

853. Car Fleet

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int carFleet(int target, int[] position, int[] speed) {
    TreeMap<Integer,Double> map=new TreeMap<>(Collections.reverseOrder());
    int n=position.length;
    for (int i = 0; i < n; i++) {
        map.put(position[i],(double)(target-position[i])/speed[i]);
    }
    int res=0;
    double cur=0;
    for (Integer pos : map.keySet()) {
        double curTime=map.get(pos);
        if(curTime>cur){
            cur=curTime;
            res++;
        }
    }
    return res;
}

2340. Minimum Adjacent Swaps to Make a Valid Array

注意：

  1. 找leftmost min 和 rightmost max, 只需要one pass即可
  2. 若left most min 比 rightmost max 还靠右，则有一次swap可以两用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int minimumSwaps(int[] nums) {
            int n=nums.length;
    int min=0;
    int max=n-1;
    for (int i = 1; i < n; i++) {
        if(nums[i]<nums[min]){
            min=i;
        }
        if(nums[n-1-i]>nums[max]){
            max=n-1-i;
        }
    }
    return min-0+n-1-max-(min>max ? 1 : 0);
}

2357. Make Array Zero by Subtracting Equal Amounts

1
2
3
4
5
6
7
8
9
10
11
12
13
public int minimumOperations(int[] nums) {
    int[] arr=new int[101];
    for (int num : nums) {
        arr[num]++;
    }
    int res=0;
    for (int i = 1; i <= 100; i++) {
        if(arr[i]>0){
            res++;
        }
    }
    return res;
}

531. Lonely Pixel I

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 findLonelyPixel(char[][] picture) {
    int row=picture.length;
    int col=picture[0].length;
    int[] rows=new int[row];
    int[] cols=new int[col];
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            if(picture[i][j]=='B'){
                rows[i]++;
                cols[j]++;
            }
        }
    }
    int res=0;
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            if(picture[i][j]=='B' && rows[i]==1 && cols[j]==1){
                res++;
            }
        }
    }
    return res;
}

562. Longest Line of Consecutive One in 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
public int longestLine(int[][] mat) {
    int row=mat.length;
    int col=mat[0].length;
    int[][][] dp=new int[row+1][col+2][4];
    int max0=0;
    int max1=0;
    int max2=0;
    int max3=0;
    //horizontal, vertical, diagonal, anti-diagonal
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            if(mat[i][j]==1){
                dp[i+1][j+1][0]=dp[i+1][j][0]+1;
                max0=Math.max(max0,dp[i+1][j+1][0]);
                dp[i+1][j+1][1]=dp[i][j+1][1]+1;
                max1=Math.max(max1,dp[i+1][j+1][1]);
                dp[i+1][j+1][2]=dp[i][j][2]+1;
                max2=Math.max(max2,dp[i+1][j+1][2]);
                dp[i+1][j+1][3]=dp[i][j+2][3]+1;
                max3=Math.max(max3,dp[i+1][j+1][3]);
            }
        }
    }
    max0=Math.max(max0,max1);
    max0=Math.max(max0,max2);
    max0=Math.max(max0,max3);
    return max0;
}

624. Maximum Distance in Arrays

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int maxDistance(List<List<Integer>> arrays) {
    int res=0;
    int min=arrays.get(0).get(0);
    int max=arrays.get(0).get(arrays.get(0).size()-1);
    int n=arrays.size();
    for (int i = 1; i < n; i++) {
        List<Integer> arr=arrays.get(i);
        res=Math.max(res,Math.abs(arr.get(arr.size()-1)-min));
        res=Math.max(res,Math.abs(arr.get(0)-max));
        min=Math.min(min,arr.get(0));
        max=Math.max(max,arr.get(arr.size()-1));
    }
    return res;
}

643. Maximum Average Subarray I

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public double findMaxAverage(int[] nums, int k) {
    double sum=0;
    int n=nums.length;
    for (int i = 0; i < k; i++) {
        sum+=nums[i];
    }
    double res=sum/k;
    for (int i = k; i < n; i++) {
        //[i-k+1,i]
        sum+=nums[i];
        sum-=nums[i-k];
        res=Math.max(res,sum/k);
    }
    return res;
}

644. Maximum Average Subarray II

法一：TLE

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 double findMaxAverage(int[] nums, int k) {
    int n=nums.length;
    double res=find(nums,k);
    for (int i = k+1; i <= n; i++) {
        res=Math.max(res,find(nums,i));
    }
    return res;
}

public double find(int[] nums, int k) {
    double sum=0;
    int n=nums.length;
    for (int i = 0; i < k; i++) {
        sum+=nums[i];
    }
    double res=sum/k;
    for (int i = k; i < n; i++) {
        //[i-k+1,i]
        sum+=nums[i];
        sum-=nums[i-k];
        res=Math.max(res,sum/k);
    }
    return res;
}

法二：强行TLE

活久见：77 / 77 test cases passed, but took too long.

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 double findMaxAverage(int[] nums, int k) {
    int n=nums.length;
    double[] prefix=new double[n];//[0,i]
    prefix[0]=nums[0];
    for (int i = 1; i < n; i++) {
        prefix[i]=prefix[i-1]+nums[i];
    }
    double res=find(prefix,k);
    for (int i = k+1; i <= n; i++) {
        res=Math.max(res,find(prefix,i));
    }
    return res;
}

public double find(double[] prefix, int k) {
    double sum=prefix[k-1];   //[0,k-1]
    int n=prefix.length;
    double res=sum/k;
    for (int i = k; i < n; i++) {
        //[i-k+1,i]
        sum=prefix[i]-prefix[i-k];
        res=Math.max(res,sum/k);
    }
    return res;
}

https://leetcode.com/problems/maximum-average-subarray-ii/discuss/132164/Java-Clear-Code-using-Binary-Search-with-Detailed-Explanations

可谓妙极

public double findMaxAverage(int[] nums, int k) {
    double l = -10001, r = 100001;
    while(l + 0.00001 < r) {
        double m = l + (r - l) / 2;
        if (canFindLargerAverage(nums, k, m)) {
            l = m;
        }
        else {
            r = m;
        }
    }
    return l;
}   

private boolean canFindLargerAverage(int[] nums, int k, double x) {
    int n = nums.length;
    double[] a = new double[n];
    for (int i = 0; i < n; i++) {
        a[i] = nums[i] - x;
    }
    double cur = 0, prev = 0;
    for (int i = 0; i < k; i++) {
        cur += a[i];
    }
    if (cur >= 0) {
        return true;
    }
    for (int i = k; i < n; i++) {
        cur += a[i];
        prev += a[i - k];
        if (prev < 0) {
            cur -= prev;
            prev = 0;
        }
        if (cur >= 0) {
            return true;
        }
    }
    return false;
}

723. Candy Crush

simulation好题

注意：

  1. negative标记将被removed的元素
  2. 将被removed的元素也能remove其他元素，需要以abs来判断是否为同一type
  3. 只需考虑down和right
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
public int[][] candyCrush(int[][] board) {
    int row=board.length;
    int col=board[0].length;
    boolean found=true;
    while(found){
        found=false;
        //crash (mark as negative)
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                int val=Math.abs(board[i][j]);
                if(val==0){
                    continue;
                }
                //down
                if(i+2<row && val==Math.abs(board[i+1][j]) && val==Math.abs(board[i+2][j])){
                    found=true;
                    int idx=i;
                    while(idx<row && Math.abs(board[idx][j])==val){
                        board[idx][j]=-val;
                        idx++;
                    }
                }
                //right
                if(j+2<col && val==Math.abs(board[i][j+1]) && val==Math.abs(board[i][j+2])){
                    found=true;
                    int idx=j;
                    while(idx<col && Math.abs(board[i][idx])==val){
                        board[i][idx]=-val;
                        idx++;
                    }
                }
            }
        }
        //gravity
        if(found){
            for (int j = 0; j < col; j++) {
                int idx=row-1;
                for (int i = row-1; i >= 0; i--) {
                    if(board[i][j]>0){
                        board[idx--][j]=board[i][j];
                    }
                }
                for (int i = idx; i >= 0; i--) {
                    board[i][j]=0;
                }
            }
        }
    }
    return board;
}

1198. Find Smallest Common Element in All Rows

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int smallestCommonElement(int[][] mat) {
    Map<Integer,Integer> map=new HashMap<>();
    int n=mat.length;
    for (int i = 0; i < n-1; i++) {
        int[] arr=mat[i];
        for (int num : arr) {
            map.put(num,map.getOrDefault(num,0)+1);
        }
    }
    for (int num : mat[n - 1]) {
        if(map.containsKey(num) && map.get(num)==n-1){
            return num;
        }
    }
    return -1;
}

还有多种解法

1182. Shortest Distance to Target Color

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 List<Integer> shortestDistanceColor(int[] colors, int[][] queries) {
    List<Integer> res=new LinkedList<>();
    int n=colors.length;
    Map<String,Integer> map=new HashMap<>();
    for (int[] query : queries) {
        int i=query[0];
        int c=query[1];
        if(colors[i]==c){
            res.add(0);
            continue;
        }
        String key=i+","+c;
        if(map.containsKey(key)){
            res.add(map.get(key));
            continue;
        }
        int left=i-1;
        int right=i+1;
        int len=Integer.MAX_VALUE;
        while(left>=0 && colors[left]!=c){
            left--;
        }
        if(left>=0 && colors[left]==c){
            len=i-left;
        }
        while(right<n && colors[right]!=c){
            right++;
        }
        if(right<n && colors[right]==c){
            len=Math.min(len,right-i);
        }
        if(len==Integer.MAX_VALUE){
            len=-1;
        }
        map.put(key,len);
        res.add(len);
    }
    return res;
}

1196. How Many Apples Can You Put into the Basket

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int maxNumberOfApples(int[] weight) {
    Arrays.sort(weight);
    int capacity=5000;
    int res=0;
    for (int num : weight) {
        if(capacity>=num){
            res++;
            capacity-=num;
        }else{
            break;
        }
    }
    return res;
}

1167. Minimum Cost to Connect Sticks

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int connectSticks(int[] sticks) {
    int n=sticks.length;
    if(n<2){
        return 0;
    }
    if(n==2){
        return sticks[0]+sticks[1];
    }
    PriorityQueue<Integer> pq=new PriorityQueue<>();
    for (int i = 0; i < n; i++) {
        pq.offer(sticks[i]);
    }
    int res=0;
    while(pq.size()>1){
        int c=pq.poll()+pq.poll();
        res+=c;
        pq.offer(c);
    }
    return res;
}

1207. Unique Number of Occurrences

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public boolean uniqueOccurrences(int[] arr) {
    Arrays.sort(arr);
    int cur=1;
    Set<Integer> set=new HashSet<>();
    for (int i = 1; i < arr.length; i++) {
        if(arr[i]==arr[i-1]){
            cur++;
        }else{
            if(set.contains(cur)){
                return false;
            }
            set.add(cur);
            cur=1;
        }
    }
    if(set.contains(cur)){
        return false;
    }
    return true;
}

1402. Reducing Dishes

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 maxSatisfaction(int[] satisfaction) {
    PriorityQueue<Integer> pos=new PriorityQueue<>();
    PriorityQueue<Integer> npos=new PriorityQueue<>((a,b)->(b-a));
    for (int i : satisfaction) {
        if(i>0){
            pos.offer(i);
        }else{
            npos.offer(i);
        }
    }
    int sum=0;
    int res=0;
    int t=1;
    while(!pos.isEmpty()){
        int p=pos.poll();
        sum+=p;
        res+=p*(t++);
    }
    while(!npos.isEmpty() && npos.peek()+sum+res>res){
        int p=npos.poll();
        res=res+sum+p;
        sum+=p;
    }
    return res;
}

945. Minimum Increment to Make Array Unique

1
2
3
4
5
6
7
8
9
10
11
12
public int minIncrementForUnique(int[] nums) {
    Arrays.sort(nums);
    int res=0;
    int n=nums.length;
    for (int i = 1; i < n; i++) {
        if(nums[i]<=nums[i-1]){
            res+=nums[i-1]+1-nums[i];
            nums[i]=nums[i-1]+1;
        }
    }
    return res;
}

1918. Kth Smallest Subarray Sum

binary_search + 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
public int kthSmallestSubarraySum(int[] nums, int k) {
    //return the kth smallest subarray sum
    //=> return the smallest num satisfying that
    // k subarray sum <= num
    int lo=0;
    int hi= Arrays.stream(nums).sum();
    while(lo<hi){
        int mid=(lo+hi)>>1;
        if(countLessThan(nums,mid)<k){
            //if not valid
            lo=mid+1;
        }else{
            //if valid
            hi=mid;
        }
    }
    return lo;
}

private int countLessThan(int[] nums, int target){
    int l=0;
    int sum=0;
    int count=0;
    for (int r = 0; r < nums.length; r++) {
        sum+=nums[r];
        //[l,r]
        while(sum>target){
            sum-=nums[l++];
        }
        count+=r-l+1;
    }
    return count;
}

2100. Find Good Days to Rob the Bank

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public List<Integer> goodDaysToRobBank(int[] security, int time) {
    int n=security.length;
    int[] l=new int[n];//longest non-increasing subarray end with i
    int[] r=new int[n];//longest non-decreasing subarray start with i
    l[0]=1;
    for (int i = 1; i < n; i++) {
        l[i]=security[i]<=security[i-1] ? l[i-1]+1 : 1;
    }
    r[n-1]=1;
    for (int i = n-2; i >= 0; i--) {
        r[i]=security[i]<=security[i+1] ? r[i+1]+1 : 1;
    }
    List<Integer> res=new ArrayList<>();
    for (int i = 0; i < n; i++) {
        if(l[i]>time && r[i]>time){
            res.add(i);
        }
    }
    return res;
}

2294. Partition Array Such That Maximum Difference Is K

1
2
3
4
5
6
7
8
9
10
11
12
13
public int partitionArray(int[] nums, int k) {
    Arrays.sort(nums);
    int res=1;
    int n=nums.length;
    int start=0;
    for (int i = 0; i < n; i++) {
        if(nums[i]-nums[start]>k){
            res++;
            start=i;
        }
    }
    return res;
}

2524. Maximum Frequency Score of a Subarray

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
public int maxFrequencyScore(int[] nums, int k) {
    int mod=(int)1e9+7;
    Map<Integer, List<Long>> map=new HashMap<>();
    Map<Integer,Integer> cnt=new HashMap<>();
    for (int num : nums) {
        cnt.put(num,cnt.getOrDefault(num,0)+1);
    }
    for (Integer num : cnt.keySet()) {
        int val=cnt.get(num);
        long pw=1;
        List<Long> list=new ArrayList<>();
        for (int i = 0; i < val; i++) {
            pw=pw*num%mod;
            list.add(pw);
        }
        map.put(num,list);
    }
    int max=0;
    int left=0;
    int right=0;
    int n=nums.length;
    long sum=0;
    cnt.clear();
    while(right<n){
        //[left,right)
        int num=nums[right++];
        if(cnt.containsKey(num)){
            int val=cnt.get(num);
            //注意：减法时可能产生负数，需要加上mod来避免
            sum=(sum-map.get(num).get(val-1)%mod+
                    map.get(num).get(val)%mod+mod)%mod;
            cnt.put(num,val+1);
        }else{
            sum=(sum+map.get(num).get(0)%mod)%mod;
            cnt.put(num,1);
        }
        if(right-left>k){
            int l=nums[left++];
            int val=cnt.get(l);
            if(val==1){
                sum=(sum-map.get(l).get(0)%mod)%mod;
                cnt.remove(l);
            }else{
                //注意：减法时可能产生负数，需要加上mod来避免
                sum=(sum-map.get(l).get(val-1)%mod+
                        map.get(l).get(val-2)%mod+mod)%mod;
                cnt.put(l,val-1);
            }
        }
        if(right-left==k){
            max=Math.max(max,(int)sum);
        }
    }
    return max;
}

2448. Minimum Cost to Make Array Equal

prefix sum of cost

still confusing: why Changing the elements into one of the numbers already existing in the array nums is optimal. 

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 long minCost(int[] nums, int[] cost) {
    int n=nums.length;
    int[][] arr=new int[n][2];
    for (int i = 0; i < n; i++) {
        arr[i][0]=nums[i];
        arr[i][1]=cost[i];
    }
    Arrays.sort(arr,(a,b)->(a[0]-b[0]));
    long[] prefix=new long[n+1]; //cost sum of first i items
    for (int i = 0; i < n; i++) {
        prefix[i+1]=prefix[i]+arr[i][1];
    }
    long c=0;
    for (int i = 1; i < n; i++) {
        c+=1L*(arr[i][0]-arr[0][0])*arr[i][1];
    }
    long res=c;
    for (int i = 1; i < n; i++) {
        long diff=arr[i][0]-arr[i-1][0];
        //[0,i-1]
        c+=diff*prefix[i];
        //[i,n-1]
        c-=diff*(prefix[n]-prefix[i]);
        res=Math.min(res,c);
    }
    return res;
}

2462. Total Cost to Hire K Workers

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 long totalCost(int[] costs, int k, int candidates) {
    long res=0;
    int n=costs.length;
    PriorityQueue<Integer> front=new PriorityQueue<>();
    PriorityQueue<Integer> rear=new PriorityQueue<>();
    int l=0;
    int r=n-1;
    for (int i = 0; i < candidates && l<=r; i++) {
        front.offer(costs[l++]);
        if(l>r){
            break;
        }
        rear.offer(costs[r--]);
    }
    for (int i = 0; i < k; i++) {
        if(front.isEmpty()){
            res+=rear.poll();
            if(l<=r){
                rear.offer(costs[r--]);
            }
            continue;
        }
        if(rear.isEmpty()){
            res+=front.poll();
            if(l<=r){
                rear.offer(costs[l++]);
            }
            continue;
        }
        if(front.peek()<=rear.peek()){
            res+=front.poll();
            if(l<=r){
                front.offer(costs[l++]);
            }
        }else{
            res+=rear.poll();
            if(l<=r){
                rear.offer(costs[r--]);
            }
        }
    }
    return res;
}

918. Maximum Sum Circular Subarray

Kadane’s algorithm

how to handle special case?

法一：kadane + prefix & suffix sum

法二：kadane*2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int maxSubarraySumCircular(int[] nums) {
    int n=nums.length;
    int pre1=0;  //greatest subarray ending in i
    int res=Integer.MIN_VALUE;
    int sum=0;
    int pre2=0; //smallest subarray ending in i
    int min=0;

    for (int i = 0; i < n; i++) {
        sum+=nums[i];
        pre1= pre1>=0 ? pre1+nums[i] : nums[i];
        pre2= pre2>=0 ? nums[i] : pre2+nums[i];
        res=Math.max(res,pre1);
        min=Math.min(min,pre2);
    }
    //however, min cannot be [0,n-1]
    if(sum!=min){
        res=Math.max(res,sum-min);
    }
    return res;
}