IVN
0%

Weekly_Contest

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

周赛好题

2561. Rearranging Fruits

how should we swap to minimize the cost?

  • swap directly, or

  • swap indirectly

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[] basket1, int[] basket2) {
    Map<Integer,Integer> map=new HashMap<>();
    for (int num : basket1) {
        map.put(num,map.getOrDefault(num,0)+1);
    }
    for (int num : basket2) {
        map.put(num,map.getOrDefault(num,0)-1);
    }
    List<Integer> last=new ArrayList<>();
    for (Integer key : map.keySet()) {
        int val=map.get(key);
        if((val&1)==1){
            return -1;
        }
        for (int i = 0; i < Math.abs(val) / 2; i++) {
            last.add(key);
        }
    }
    int min=Math.min(Arrays.stream(basket1).min().getAsInt()
            , Arrays.stream(basket2).min().getAsInt());
    Collections.sort(last);
    long res=0;
    for (int i = 0; i < last.size()/2; i++) {
        res+=Math.min(last.get(i),2*min);
    }
    return res;
}

2563. Count the Number of Fair Pairs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public long countFairPairs(int[] nums, int lower, int upper) {
    Arrays.sort(nums);
    return count(nums,upper)-count(nums,lower-1);
}

long count(int[] nums, int upper){
    //count pairs <= upper
    long count=0;
    int left=0;
    int right=nums.length-1;
    while(left<right){
        //[left+1,right]
        if(nums[left]+nums[right]<=upper){
            count+=right-left;
            left++;
        }else{
            right--;
        }
    }
    return count;
}

2576. Find the Maximum Number of Marked Indices

ChatGPT?? 不如Contest 2100!

greedy:

  1. 较小数从0开始，较大数从(n+1)/2开始
  2. 原则：
    1. 较小的较小数应该由较小的较大数来满足
    2. 越小的较小数越容易被满足，应该优先满足它
  3. algorithm:
    1. 若当前较小数能被当前较大数满足，则left++,right++（因为该较大数不能再用了）
    2. 否则，right++,换更大的较大数来满足
    3. return 被满足的较小数总数*2
1
2
3
4
5
6
7
8
9
10
11
public int maxNumOfMarkedIndices(int[] nums) {
    int n=nums.length;
    Arrays.sort(nums);
    int f=0,s=(n+1)/2;
    while(s<n){
        if(nums[f]*2<=nums[s])
            f++;
        s++;
    }
    return f*2;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
public int maxNumOfMarkedIndices(int[] nums) {
    int n=nums.length;
    Arrays.sort(nums);
    int s=0;
    int b=(n+1)/2;
    while(b<n){
        if(nums[s]*2<=nums[b]){
            s++;
        }
        b++;
    }
    return s*2;
}

2577. Minimum Time to Visit a Cell In a Grid

注意：

  • 只要第一步能走出去，路就能走通！
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 minimumTime(int[][] grid) {
    int row=grid.length;
    int col=grid[0].length;
    if(grid[0][1]>1 && grid[1][0]>1){
        return -1;
    }
    int[] dx=new int[]{0,0,1,-1};
    int[] dy=new int[]{1,-1,0,0};
    PriorityQueue<int[]> pq=new PriorityQueue<>((a,b)->(a[2]-b[2]));
    boolean[][] visited=new boolean[row][col];
    pq.offer(new int[]{0,0,0});
    visited[0][0]=true;
    while(!pq.isEmpty()){
        int[] cur=pq.poll();
        int i=cur[0];
        int j=cur[1];
        int t=cur[2];
        if(i==row-1 && j==col-1){
            return t;
        }
        int x,y;
        for (int k = 0; k < 4; k++) {
            x=i+dx[k];
            y=j+dy[k];
            if(x<0 || x>=row || y<0 || y>=col || visited[x][y]){
                continue;
            }
            //for every point, only consider first/fastest arrival
            visited[x][y]=true;
            if(t+1>=grid[x][y]){
                pq.offer(new int[]{x,y,t+1});
            }else{
                //can always move back and forth to wait
                int diff=grid[x][y]-t;
                if(diff%2==0){
                    //need to add 1 more time, since (back and forth)s
                    //take 2n time, n>=1
                    pq.offer(new int[]{x,y,grid[x][y]+1});
                }else{
                    pq.offer(new int[]{x,y,grid[x][y]});
                }
            }
        }
    }
    return -1;
}

2589. Minimum Time to Complete All Tasks

注意：

  1. It is always beneficial to run the task as late as possible so that later tasks can run simultaneously.
  2. Since there are only up to 2000 time points to consider, you can check them one by one
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 findMinimumTime(int[][] tasks) {
    Set<Integer> set=new HashSet<>();
    Arrays.sort(tasks,(a,b)->(a[1]-b[1]));
    for (int[] task : tasks) {
        int start=task[0];
        int end=task[1];
        int i=task[1];
        int d=task[2];
        for(int j=start; j<=end; j++){
            if(set.contains(j)){
                d--;
                if(d==0){
                    break;
                }
            }
        }
        while(d>0){
            if(!set.contains(i)){
                set.add(i--);
                d--;
            }else{
                i--;
            }
        }
    }
    return set.size();
}

2597. The Number of Beautiful Subsets

注意：

  • 此思路有bug
  • 若nums为 [1,1,1]，则remove后，unchoose开始时set为空，存在漏算情况！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//wrong!
Set<Integer> set=new HashSet<>();
int res=0;
public int beautifulSubsets(int[] nums, int k) {
    backtracking(nums,0,k);
    return res;
}

void backtracking(int[] nums ,int cur, int k){
    if(cur==nums.length){
        if(set.size()>0){
            res++;
        }
        return;
    }
    //choose
    if(!set.contains(nums[cur]-k) && !set.contains(nums[cur]+k)){
        set.add(nums[cur]);
        backtracking(nums,cur+1,k);
        set.remove(nums[cur]);
    }
    //unchoose
    backtracking(nums,cur+1,k);
}

  • 不sort不行！反例：

  • **[18, 12, 10, 5, 6, 2, 18, 3] **

  • 8

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Set<Integer> set=new HashSet<>();
public int beautifulSubsets(int[] nums, int k) {
    Arrays.sort(nums);
    return backtracking(nums,0,k);
}

int backtracking(int[] nums, int cur, int k){
    if(cur==nums.length){
        return set.size()>0 ? 1 : 0;
    }
    int unchoose=backtracking(nums,cur+1,k);
    int choose=0;
    if(!set.contains(nums[cur]-k)){
        set.add(nums[cur]);
        choose=backtracking(nums,cur+1,k);
        set.remove(nums[cur]);
    }
    return choose+unchoose;
}

还有dp解法：

2602. Minimum Operations to Make All Array Elements Equal

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 List<Long> minOperations(int[] nums, int[] queries) {
    List<Long> res=new ArrayList<>();
    int n=nums.length;
    Arrays.sort(nums);
    long[] prefix=new long[n+1]; //sum of [0,i-1]
    for (int i = 1; i <= n; i++) {
        prefix[i]=prefix[i-1]+nums[i-1];
    }
    for (int query : queries) {
        int i=leftSearch(nums,query);
        //[0,i-1]   i   prefix[i]
        //[i,n-1]   n-i     prefix[n] - prefix[i]
        long sum=(long)query*i-prefix[i];
        sum+=prefix[n]-prefix[i]-(long)query*(n-i);
        res.add(sum);
    }
    return res;
}

int leftSearch(int[] nums, int query){
    //find the smallest i where nums[i] >=query
    //if to insert query, it will be placed at i
    int left=0;
    int right=nums.length;
    while(left<right){
        //[left,right)
        int mid=(left+right)/2;
        if(nums[mid]<query){
            left=mid+1;
        }else{
            right=mid;
        }
    }
    return left;
}

2614. Prime In Diagonal

送分题也会翻车啊！！

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 diagonalPrime(int[][] nums) {
    int n=nums.length;
    //(i,i), (i,n-i-1)
    int res=0;
    for (int i = 0; i < n; i++) {
        if(isPrime(nums[i][i])){
            res=Math.max(res,nums[i][i]);
        }
        if(isPrime(nums[i][n-i-1])){
            res=Math.max(res,nums[i][n-i-1]);
        }

    }
    return res;
}

boolean isPrime(int num){
   	//再简单的edge case也不能忘记考虑
    if(num==1){
        return false;
    }
    if(num==2){
        return true;
    }
    for(int i=2; i<=Math.sqrt(num); i++){
        if(num%i==0){
            return false;
        }
    }
    return true;
}

2615. Sum of Distances

压哨绝杀失败！！

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 long[] distance(int[] nums) {
    int n=nums.length;
    long[] res=new long[n];
    Map<Integer,List<Integer>> map=new HashMap<>();

    for (int i = 0; i < nums.length; i++) {
        map.putIfAbsent(nums[i],new ArrayList<>());
        map.get(nums[i]).add(i);
    }
    //[0,2,3,5]
    for (Integer num : map.keySet()) {
        List<Integer> list=map.get(num);
        int len=list.size();
        long[] arr=new long[len+1];//sum of [0,i-1]
        for (int i = 1; i <= len; i++) {
            arr[i]=arr[i-1]+list.get(i-1);
        }
        //[0,0,2,5,8]
        for (int i = 0; i < len; i++) {
            int idx=list.get(i);
            //[0,i-1]
            //[i+1,len-1]
            long a=i==0 ? 0 : (long)i*idx-arr[i];
            long b=i==len-1 ? 0 : arr[len]-arr[i+1]-(long)(len-i-1)*idx;
            res[idx]=a+b;
        }
    }
    return res;
}

2645. Minimum Additions to Make Valid String

在2个string上玩two pointer，好题！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int addMinimum(String word) {
    int n=word.length();
    String s="abc";
    int res=0;
    int idx=0;
    for (int i = 0; i < n; i++) {
        char c=word.charAt(i);
        while(c!=s.charAt(idx)){
            res++;
            idx=(idx+1)%3;
        }
        idx=(idx+1)%3;
    }
    //0 : ok
    //1 : +2
    //2 : +1
    if(idx!=0){
        res+=3-idx;
    }
    return res;
}

2653. Sliding Subarray Beauty

当直接法不好处理时，考虑换个角度

注意：-50 <= nums[i] <= 50

法一：Simple Counting

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[] getSubarrayBeauty(int[] nums, int k, int x) {
    int[] count=new int[50]; //0: -50, 1:-49, .., 49:-1
    int n=nums.length;
    int[] res=new int[n-k+1];
    for (int i = 0; i < n; i++) {
        if(nums[i]<0){
            count[nums[i]+50]++;
        }
        //k-1,n-1
        if(i<k-1){
            continue;
        }
        if(i-k>=0 && nums[i-k]<0){
            count[nums[i-k]+50]--;
        }
        //[i-k+1,i]
        int t=0;
        int j=0;
        for (; j < 50; j++) {
            t+=count[j];
            if(t>=x){
                break;
            }
        }
        if(t>=x){
            res[i-k+1]=j-50;
        }
    }
    return res;
}

法二：TreeMap

思路同上，但慢得多

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 int[] getSubarrayBeauty(int[] nums, int k, int x) {
    int n=nums.length;
    int[] res=new int[n-k+1];
    TreeMap<Integer,Integer> min=new TreeMap<>();
    for (int i = 0; i < n; i++) {
        if(nums[i]<0){
            min.put(nums[i],min.getOrDefault(nums[i],0)+1);
        }
        //[i-k+1,i]
        if(i-k>=0 && nums[i-k]<0){
            min.put(nums[i-k],min.get(nums[i-k])-1);
            if(min.get(nums[i-k])==0){
                min.remove(nums[i-k]);
            }
        }
        if(i-k+1>=0){
            int t=0;
            int v=0;
            for (Integer val : min.keySet()) {
                t+=min.get(val);
                v=val;
                if(t>=x){
                    break;
                }
            }
            if(t>=x){
                res[i-k+1]=v;
            }
        }
    }
    return res;
}

2654. Minimum Number of Operations to Make All Array Elements Equal to 1

codeforce经典题库

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
public int minOperations(int[] nums) {
    int n=nums.length;
    int res=Integer.MAX_VALUE;
    int ones=0;
    for (int i = 0; i < n; i++) {
        int g=nums[i];
        if(g==1){
            ones++;
        }
        for (int j = i+1; j < n; j++) {
            g=gcd(g,nums[j]);
            if(g==1){
                //j-i steps to get a 1
                //n-1 steps to make all others 1
                res=Math.min(res,j-i+n-1);
            }
        }
    }
    if(ones>0){
        res=n-ones;
    }
    return res==Integer.MAX_VALUE ? -1 : res;
}

private int gcd(int a, int b){
    //4 3
    //3 1
    //1 0
    if(a<b){
        return gcd(b,a);
    }
    while(b!=0){
        int temp=b;
        b=a%b;
        a=temp;
    }
    return a;
}

2662. Minimum Cost of a Path With Special Roads

dijkstra

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 minimumCost(int[] start, int[] target, int[][] specialRoads) {
    //Memory Limit Exceeded
           int[][] dist=new int[target[0]+1][target[1]+1];

    PriorityQueue<int[]> q=new PriorityQueue<>((a,b)->(a[2]-b[2]));

    q.offer(new int[]{start[0],start[1],0});

    while(!q.isEmpty()){
        int[] cur=q.poll();
        int i=cur[0];
        int j=cur[1];
        if(i==target[0] && j==target[1]){
            return cur[2];
        }
        q.offer(new int[]{target[0],target[1],cur[2]+target[0]+target[1]-i-j});
        for (int[] arr : specialRoads) {
            int x1=arr[0];
            int y1=arr[1];
            int x2=arr[2];
            int y2=arr[3];
            int cost=cur[2]+Math.abs(x1-i)+Math.abs(y1-j)+arr[4];
            if(dist[x2][y2]==0 || dist[x2][y2]>cost){
                dist[x2][y2]=cost;
                q.offer(new int[]{x2,y2,cost});
            }
        }
    }
    return dist[target[0]][target[1]]; 
}

其实priority可以保证第一次到达某一点既是最短路径，无需额外的dist数组

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 minimumCost(int[] start, int[] target, int[][] specialRoads) {
    Map<Integer, HashSet<Integer>> map=new HashMap<>();
    PriorityQueue<int[]> pq=new PriorityQueue<>((a,b)->(a[2]-b[2]));
    pq.offer(new int[]{start[0],start[1],0});
    int tx=target[0];
    int ty=target[1];
    while(!pq.isEmpty()){
        int[] cur=pq.poll();
        int i=cur[0];
        int j=cur[1];
        if(i==tx && j==ty){
            return cur[2];
        }
        //already reach this point before (by shorter dist)
        if(map.containsKey(i) && map.get(i).contains(j)){
            continue;
        }
        map.putIfAbsent(i,new HashSet<>());
        map.get(i).add(j);
        //reach target directly
        pq.offer(new int[]{tx,ty,cur[2]+tx+ty-i-j});
        for (int[] arr : specialRoads) {
            int x1=arr[0];
            int y1=arr[1];
            int x2=arr[2];
            int y2=arr[3];
            //try to use this specialRoad
            //if the end of this specialRoad has already been reached,
            //then a shorter path to the end has been found,
            //no need to consider
            if(map.containsKey(x2) && map.get(x2).contains(y2)){
                continue;
            }
            int cost=cur[2]+Math.abs(x1-i)+Math.abs(y1-j)+arr[4];
            pq.offer(new int[]{x2,y2,cost});
        }
    }
    return -1;
}

2712. Minimum Cost to Make All Characters Equal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public long minimumCost(String s) {
    long res=0;
    int n=s.length();
    for (int i = 1; i < n; i++) {
        if(s.charAt(i)!=s.charAt(i-1)){
            //i-1,i is different
            //either flip [0,i-1] or flip [i,n-1]
            // to make i-1, i the same
            //after flipping, won't affect following or previous status
            res+=Math.min(i,n-i);
        }
    }
    return res;
}

2713. Maximum Strictly Increasing Cells in a Matrix

https://leetcode.com/problems/maximum-strictly-increasing-cells-in-a-matrix/discuss/3570203/Longest-Path-in-C%2B%2B-Java-and-Python

新题型：longest path

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 int maxIncreasingCells(int[][] mat) {
    int row=mat.length;
    int col=mat[0].length;
    //val -> coordinates
    TreeMap<Integer, List<int[]>> map=new TreeMap<>();
    int[] rows=new int[row];//maximum existing path length ending with this row's point
    int[] cols=new int[col];//maximum existing path length ending with this col's point
    int[][] temp=new int[row][col];//maximum existing path ending with this point
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            map.putIfAbsent(mat[i][j],new ArrayList<>());
            map.get(mat[i][j]).add(new int[]{i,j});
        }
    }
    for (Integer val : map.keySet()) {
        for (int[] arr : map.get(val)) {
            temp[arr[0]][arr[1]]=Math.max(rows[arr[0]],cols[arr[1]])+1;
        }
        for (int[] arr : map.get(val)) {
            rows[arr[0]]=Math.max(rows[arr[0]],temp[arr[0]][arr[1]]);
            cols[arr[1]]=Math.max(cols[arr[1]],temp[arr[0]][arr[1]]);
        }
    }
    int res=0;
    for (int i : rows) {
        res=Math.max(res,i);
    }
    for (int i : cols) {
        res=Math.max(res,i);
    }
    return res;
}

2718. Sum of Matrix After Queries

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public long matrixSumQueries(int n, int[][] queries) {
    long res=0;
    boolean[] rows=new boolean[n];
    boolean[] cols=new boolean[n];
    int rowRemaining=n;
    int colRemaining=n;
    for (int i = queries.length - 1; i >= 0; i--) {
        if(queries[i][0]==0 && !rows[queries[i][1]]){
            rows[queries[i][1]]=true;
            res+=colRemaining*queries[i][2];
            rowRemaining--;
        }
        if(queries[i][0]==1 && !cols[queries[i][1]]){
            cols[queries[i][1]]=true;
            res+=rowRemaining*queries[i][2];
            colRemaining--;
        }
    }
    return res;
}

2749. Minimum Operations to Make the Integer Zero

太难！

https://leetcode.com/problems/minimum-operations-to-make-the-integer-zero/discuss/3679281/JavaC%2B%2BPython-Bit-count-4-lines

1
2
3
4
5
6
7
8
9
10
// num1 = ([] + num2) *k
//target(k) = num1 - k*num2, target be made of k powers of 2
public int makeTheIntegerZero(long num1, long num2) {
    for(int k=1; k<=60; k++){
        if(Long.bitCount(num1-k*num2)<=k && k<=num1-k*num2){
            return k;
        }
    }
    return -1;
}

2763. Sum of Imbalance Numbers of All Subarrays

神之一手：

  • Increment the imbalance value whenever a new number is not adjacent (+/- 1) to other old numbers.
    • For example, when you add 3 to [1, 5], or when you add 5 to [1, 3].
    • new value is
      • (i) largest,
      • (ii) smallest,
      • (iii) between two old numbers.
  • Decrement the imbalance value whenever a new number is adjacent (+/- 1) to two old numbers.
    • The imbalance value does not change in the case of one adjacent old number.
    • For example, when you add 3 to [2, 4].
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int sumImbalanceNumbers(int[] nums) {
    int res=0;
    int n=nums.length;
    int cur=0;
    Set<Integer> set=new HashSet<>();
    for (int i = 0; i < n; i++) {
        set.clear();
        set.add(nums[i]);
        cur=0;
        for (int j = i+1; j < n; j++) {
            if(!set.contains(nums[j]) && !set.contains(nums[j]-1) && !set.contains(nums[j]+1)){
                cur++;
            }
            if(!set.contains(nums[j]) && set.contains(nums[j]-1) && set.contains(nums[j]+1)){
                cur--;
            }
            res+=cur;
            set.add(nums[j]);
        }
    }
    return res;
}

2781. Length of the Longest Valid Substring

Amazon最新OA

https://leetcode.com/problems/length-of-the-longest-valid-substring/discuss/3771333/Picture-Short-and-Concise-Approach-Easy-to-Understand-In-depth-Explanation

思路：

  • 依然是sliding window
  • 从后向前slide，确定从当前index开始的longest valid substring
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int longestValidSubstring(String word, List<String> forbidden) {
    Set<String> set=new HashSet<>(forbidden);
    int res=0;
    int n=word.length();
    int right=n-1;
    //[left,right]
    //the previous farthest right point cannot be
    // surpassed by current valid substring
    for (int left = n-1; left >= 0; left--) {
        //sb + append + toString 表现不如 直接substring
        StringBuilder sb=new StringBuilder();
        for(int i=left; i<Math.min(left+10,n) && i<=right; i++){               
            sb.append(word.charAt(i));
            if(set.contains(sb.toString())){
                right=i-1;
                break;
            }
        }
        res=Math.max(res,right-left+1);
    }
    return res;
}

2791. Count Paths That Can Form a Palindrome in a Tree

https://leetcode.com/problems/count-paths-that-can-form-a-palindrome-in-a-tree/discuss/3803579/Java-Solution-using-Bitmask-with-Detailed-Explanation

可以用bitmask来判断if two paths can form a palindrome path:

  • the same or differ by 1
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
List<int[]>[] graph;
Map<Integer,Integer> count;
int[] mask;
public long countPalindromePaths(List<Integer> parent, String s) {
    int n=parent.size();
    graph=new List[n];
    for (int i = 0; i < n; i++) {
        graph[i]=new ArrayList<>();
    }
    for (int i = 1; i < n; i++) {
        graph[parent.get(i)].add(new int[]{i,s.charAt(i)-'a'});
    }
    mask=new int[n];
    count=new HashMap<>();
    dfs(0,0);
    long res=0;
    for (int i = 0; i < n; i++) {
        //must have at least one edge, should not consider (cur,cur)
        long freq=count.get(mask[i])-1;
        for (int j = 0; j < 26; j++) {
            int newMask=mask[i]^(1<<j);
            freq+=count.getOrDefault(newMask,0);
        }
        res+=freq;
    }
    //considered (u,v) and (v,u), should halve
    res/=2;
    return res;
}

private void dfs(int cur, int val){
    mask[cur]=val;
    count.put(val,count.getOrDefault(val,0)+1);
    for (int[] arr : graph[cur]) {
        int nextIdx=arr[0];
        int nextBit=arr[1];
        dfs(nextIdx,val^(1<<nextBit));
    }
}

2800. Shortest String That Contains Three Strings

不必给自己增加难度，既然n=3，只考虑n=3的特殊情况就好

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
class Solution {
public:
    string getMinString(string a, string b) {    //compare two string with min size or if equal then return lexicographically smaller string 
        return (a.size() < b.size() || (a.size() == b.size() && a < b) )?a : b;
    }
    
    string addTwoStrings(string &a, string &b){    //try to add b at the end of a with optimal way
        if(b.find(a) != string::npos) return b; 
        for(int i = 0; i < a.size(); ++i){
            string t1 = a.substr(i), t2 = b.substr(0,  t1.size());
            if(t1 == t2) return a + b.substr(t1.size());
        }
        return a+b;
    }
    
    string solve(string& a, string& b, string& c) {    //merge a,b first and then merge with c in sequence
        string t1 = addTwoStrings(a, b), t2 = addTwoStrings(b, a);
        string res1 = getMinString(addTwoStrings(t1, c), addTwoStrings(c, t1));
        string res2 = getMinString( addTwoStrings(t2, c), addTwoStrings(c, t2));
        return getMinString(res1, res2);
    }
    
    string minimumString(string a, string b, string c) { 
        string res = getMinString( solve(a, b, c), solve(b, c, a));
        return getMinString( res , solve(c,a,b));
    }
};

2813. Maximum Elegance of a K-Length Subsequence

https://leetcode.com/problems/maximum-elegance-of-a-k-length-subsequence/discuss/3869920/JavaC%2B%2BPython-Sort-by-Profit

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 long findMaximumElegance(int[][] items, int k) {
    int n=items.length;
    Arrays.sort(items,(a,b)->(b[0]-a[0]));
    long sum=0;
    Set<Integer> set=new HashSet<>();
    LinkedList<Integer> dup=new LinkedList<>();
    long res=0;
    for (int i = 0; i < n; i++) {
        if(i<k){
            sum+=items[i][0];
            if(set.contains(items[i][1])){
                dup.add(items[i][0]);
            }
        }else if(!set.contains(items[i][1])){
            if(dup.isEmpty()){
                break;
            }
            //always update sum when seeing a unique item
            sum+=items[i][0]-dup.removeLast();
        }
        set.add(items[i][1]);
        res=Math.max(res,sum+1L*set.size()*set.size());
    }
    return res;
}

2817. Minimum Absolute Difference Between Elements With Constraint

reflection：

  • in paring problems, should always try to use symmetry to avoid duplication
    • if every i is considered with [0,i-x], then no need to consider i with [i+x,n-1]
  • find the one key idea of a problem, stay in control of the coding
    • if already try one way for 20 minutes and no AC, quit and try another one
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int minAbsoluteDifference(List<Integer> nums, int x) {
    TreeSet<Integer> set=new TreeSet<>();
    int n=nums.size();
    int res=Integer.MAX_VALUE;
    //check [0,i-x] for i
    for (int i = x; i < n; i++) {
        set.add(nums.get(i-x));
        int num=nums.get(i);
        Integer floor=set.floor(num);
        if(floor!=null){
            res=Math.min(res,num-floor);
        }
        Integer ceil=set.ceiling(num);
        if(ceil!=null){
            res=Math.min(res,ceil-num);
        }
    }
    return res;
}

2850. Minimum Moves to Spread Stones Over Grid

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
//直接暴力backtracking就行，不必要为了dp而dp
public int minimumMoves(int[][] grid) {
    //if no 0, finished
    //can always find a solution in finite time, no stack overflow
    return dfs(grid);
}

private int dfs(int[][] grid){
    int tx=0;
    int ty=0;
    boolean finished=true;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if(grid[i][j]==0){
                tx=i;
                ty=j;
                finished=false;
                break;
            }
        }
    }
    if(finished){
        return 0;
    }
    int res=Integer.MAX_VALUE;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if(grid[i][j]>1){
                grid[tx][ty]++;
                grid[i][j]--;
                res=Math.min(res,dfs(grid)+Math.abs(i-tx)+Math.abs(j-ty));
                grid[tx][ty]--;
                grid[i][j]++;
            }
        }
    }
    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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
//wrong answer!!! 609 / 611 test cases passed.
//[0,1,3]
//[3,1,0]
//[0,1,0]
Map<String,Integer> dp=new HashMap<>();
Map<Integer,List<Integer>> map=new HashMap<>();
Set<String> seen=new HashSet<>();
//0 1 2
//3 4 5
//6 7 8
public int minimumMoves(int[][] grid) {

    for(int i=0; i<9; i++){
        map.put(i,new ArrayList<>());
    }
    map.get(0).add(1);
    map.get(0).add(3);
    map.get(1).add(0);
    map.get(1).add(2);
    map.get(1).add(4);
    map.get(2).add(1);
    map.get(2).add(5);
    map.get(3).add(0);
    map.get(3).add(4);
    map.get(3).add(6);
    map.get(4).add(1);
    map.get(4).add(3);
    map.get(4).add(5);
    map.get(4).add(7);
    map.get(5).add(2);
    map.get(5).add(4);
    map.get(5).add(8);
    map.get(6).add(3);
    map.get(6).add(7);
    map.get(7).add(4);
    map.get(7).add(6);
    map.get(7).add(8);
    map.get(8).add(5);
    map.get(8).add(7);
    dp.put("111111111",0);
    StringBuilder sb=new StringBuilder();
    for(int i=0; i<3; i++){
        for(int j=0; j<3; j++){
            sb.append(grid[i][j]);
        }
    }
    return dp(sb.toString());
}

private int dp(String cur){
    if(dp.containsKey(cur)){
        return dp.get(cur);
    }
    if(seen.contains(cur)){
        return -1;
    }
    seen.add(cur);
    char[] chars=cur.toCharArray();
    int res=Integer.MAX_VALUE;
    for(int i=0; i<9; i++){
        if(chars[i]!='0'){
            //try to move while possible
            //should not redo
            for (Integer j : map.get(i)) {

                chars[i]--;
                chars[j]++;
                String sub=new String(chars);
                int dfs=dp(sub);
                    if(dfs!=-1){
                        res=Math.min(res,1+dfs);
                    }
                chars[i]++;
                chars[j]--;

            }
        }
    }
    if(res==Integer.MAX_VALUE){
        res=-1;
    }
    seen.remove(cur);
    dp.put(cur,res);
    return res;
}