IVN
0%

tag题-3

Posted on Edited on In
Symbols count in article: 9.4k Reading time ≈ 9 mins.

tag题选编3

2038. Remove Colored Pieces if Both Neighbors are the Same 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
public boolean winnerOfGame(String colors) {
    int a=0;
    int b=0;
    char[] chars = colors.toCharArray();
    int n=chars.length;
    int start=0;
    int i = 1;
    for (; i < n; i++) {
        if(chars[start]!=chars[i]){
            //[start,i-1]
            int len=i-start;
            if(len>=3){
                if(chars[start]=='A'){
                    a+=len-2;
                }else{
                    b+=len-2;
                }
            }
            start=i;
        }
    }
    int len=i-start;
    if(len>=3){
        if(chars[start]=='A'){
            a+=len-2;
        }else{
            b+=len-2;
        }
    }
    return a>b;
}

1705. Maximum Number of Eaten Apples

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 eatenApples(int[] apples, int[] days) {
    int res=0;
    PriorityQueue<int[]> pq=new PriorityQueue<>((a,b)->(a[1]-b[1]));
    //quantity, rotDate
    int n=apples.length;
    int i=0;
    for (; i < n; i++) {
        pq.offer(new int[]{apples[i],i+days[i]});
        while(!pq.isEmpty() && pq.peek()[1]<=i){
            pq.poll();
        }
        if(!pq.isEmpty()){
            int[] old=pq.poll();
            res++;
            old[0]--;
            if(old[0]>0){
                pq.offer(old);
            }
        }
    }
    while(!pq.isEmpty()){
        while(!pq.isEmpty() && pq.peek()[1]<=i){
            pq.poll();
        }
        if(!pq.isEmpty()){
            int[] old=pq.poll();
            res++;
            i++;
            old[0]--;
            if(old[0]>0){
                pq.offer(old);
            }
        }
    }
    return res;
}

527. Word Abbreviation

Greedily abbreviate, until all valid

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 List<String> wordsAbbreviation(List<String> words) {
    int n=words.size();
    String[] arr=new String[n];
    int[] ends=new int[n];
    Set<String> set=new HashSet<>();
    Set<String> conflict=new HashSet<>();
    for (int i = 0; i < n; i++) {
        arr[i]=abbr(words.get(i),ends[i]++);
        if(set.contains(arr[i])){
            conflict.add(arr[i]);
        }
        set.add(arr[i]);
    }
    while(!conflict.isEmpty()){
        Set<String> newConflict=new HashSet<>();
        set.clear();
        for (int i = 0; i < n; i++) {
            if(conflict.contains(arr[i])){
                arr[i]=abbr(words.get(i),ends[i]++);
                if(set.contains(arr[i])){
                    newConflict.add(arr[i]);
                }
                set.add(arr[i]);
            }
        }
        conflict=newConflict;
    }
    return Arrays.asList(arr);
}

private String abbr(String word, int end){
    //[0,end] + n-end-2 + [n-1]
    int n=word.length();
    if(n-end-2<=1){
        return word;
    }
    return word.substring(0,end+1)+(n-end-2)+word.charAt(n-1);
}

2542. Maximum Subsequence Score

锚定一个array，greedily变另一个

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 long maxScore(int[] nums1, int[] nums2, int k) {
    int n=nums1.length;
    int[][] pairs=new int[n][2];
    for (int i = 0; i < n; i++) {
        pairs[i][0]=nums1[i];
        pairs[i][1]=nums2[i];
    }
    Arrays.sort(pairs,(a,b)->(b[1]-a[1]));
    PriorityQueue<Integer> pq=new PriorityQueue<>();
    long res=0;
    long sum=0;
    for (int i=0; i < k; i++) {
        sum+=pairs[i][0];
        pq.offer(pairs[i][0]);
    }
    res=sum*pairs[k-1][1];
    for(int i=k; i<n; i++){
        sum-=pq.poll();
        sum+=pairs[i][0];
        pq.offer(pairs[i][0]);
        res=Math.max(res,sum*pairs[i][1]);
    }
    return res;
}

2422. Merge Operations to Turn Array Into a Palindrome

Two Pointers + Greedy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int minimumOperations(int[] nums) {
    int res=0;
    int n=nums.length;
    int left=0;
    int right=n-1;
    int leftSum=nums[0]; //[0,left]
    int rightSum=nums[n-1]; //[right,n-1]
    while(left<right){
        if(leftSum==rightSum){
            leftSum=nums[++left];
            rightSum=nums[++right];
        }else if(leftSum>rightSum){
            res++;
            rightSum+=nums[--right];
        }else{
            res++;
            leftSum+=nums[++left];
        }
    }
    return res;
}

2330. Valid Palindrome IV

1
2
3
4
5
6
7
8
9
10
public boolean makePalindrome(String s) {
    int n=s.length();
    int count=0;
    for(int i=0, j=n-1; i<j; i++,j--){
        if(s.charAt(i)!=s.charAt(j)){
            count++;
        }
    }
    return count<=2;
}

1079. Letter Tile Possibilities

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 numTilePossibilities(String tiles) {
    int[] arr=new int[26];
    for (int i = 0; i < tiles.length(); i++) {
        char c=tiles.charAt(i);
        arr[c-'A']++;
    }
    return dp(arr);
}

    //AAB
    //A
    //AA, AB
    //AAB, ABA
    //B
    //BA
    //BAA
private int dp(int[] arr){
    int sum=0;
    for (int i = 0; i < 26; i++) {
        if(arr[i]!=0){
            sum++;
            arr[i]--;
            sum+=dp(arr);
            arr[i]++;
        }
    }
    return sum;
}

1042. Flower Planting With No Adjacent

Greedily paint every vertice one by one, not DFS or BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int[] gardenNoAdj(int N, int[][] paths) {
    Map<Integer, Set<Integer>> G = new HashMap<>();
    for (int i = 0; i < N; i++) G.put(i, new HashSet<>());
    for (int[] p : paths) {
        G.get(p[0] - 1).add(p[1] - 1);
        G.get(p[1] - 1).add(p[0] - 1);
    }
    int[] res = new int[N];
    for (int i = 0; i < N; i++) {
        int[] colors = new int[5];
        for (int j : G.get(i))
            colors[res[j]] = 1;
        for (int c = 1; c <=4 ; ++c)
            if (colors[c] == 0)
                res[i] = c;
    }
    return res;
}

2323. Find Minimum Time to Finish All Jobs II

1
2
3
4
5
6
7
8
9
10
11
12
13
public int minimumTime(int[] jobs, int[] workers) {
    //more complicated task assigned to more able worker
    Arrays.sort(jobs);
    Arrays.sort(workers);
    int res=0;
    int n=jobs.length;
    for (int i = 0; i < n; i++) {
        int t=jobs[i]%workers[i]==0 ? jobs[i]/workers[i]
                : jobs[i]/workers[i]+1;
        res=Math.max(res,t);
    }
    return res;
}

2638. Count the Number of K-Free Subsets

simple backtracking: TLE

610/1235

the limit of backtracking is 20, 50 is too big

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;
int[] nums;
int k;
long res=0;
Set<Integer> set=new HashSet<>();
public long countTheNumOfKFreeSubsets(int[] nums, int k) {
    Arrays.sort(nums);
    this.nums=nums;
    this.k=k;
    n=nums.length;
    backtracking(0);
    return res;
}

private void backtracking(int start){
    //subset问题，见一个加一个，所见皆为subset
    res++;
    if(start==n){
        return;
    }
    for (int i = start; i < n; i++) {
        if(!set.contains(nums[i]-k)){
            set.add(nums[i]);
            backtracking(i+1);
            set.remove(nums[i]);
        }
    }
}

UnionFind + DP (Fib)

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
public long countTheNumOfKFreeSubsets(int[] nums, int k) {
    int n=nums.length;
    UnionFind u=new UnionFind(n);
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            if(Math.abs(nums[i]-nums[j])==k){
                u.union(i,j);
            }
        }
    }
    long res=1;
    for (int i = 0; i < n; i++) {
        if(u.find(i)==i){
            res*=cal(u.size[i]);
        }
    }
    return res;
}

private long cal(int n){
    //0: 1
    //1: 2
    //2: 3
    //3: 5
    if(n==1){
        return 2;
    }
    long a=1;
    long b=2;
    long c=0;
    for(int i=2; i<=n; i++){
        c=a+b;
        a=b;
        b=c;
    }
    return c;
}


class UnionFind{
    int[] parent;
    int[] size;
    
    UnionFind(int n){
        parent=new int[n];
        size=new int[n];
        for (int i = 0; i < n; i++) {
            parent[i]=i;
            size[i]=1;
        }
    }
    
    int find(int i){
        while(parent[i]!=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;
        }
    }
}

1218. Longest Arithmetic Subsequence of Given Difference

1
2
3
4
5
6
7
8
9
public int longestSubsequence(int[] arr, int difference) {
    int max=1;
    Map<Integer,Integer> map=new HashMap<>();
    for (int num : arr) {
        map.put(num,map.getOrDefault(num-difference,0)+1);
        max=Math.max(max,map.get(num));
    }
    return max;
}

799. Champagne Tower

杨辉三角形模拟，大基本功

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public double champagneTower(int poured, int query_row, int query_glass) {
    if(poured==0){
        return 0;
    }
    List<Double> list=new ArrayList<>();
    list.add((double)poured);
    int n=0;
    while(n++<query_row){
        List<Double> next=new ArrayList<>();
        //[0,n-1]
        //[0,1,..,n]
        next.add(Math.max(list.get(0)-1,0)/2);
        int size=list.size();
        for (int i = 0; i < size-1; i++) {
            next.add((Math.max(list.get(i)-1,0)+Math.max(list.get(i+1)-1,0))/2);
        }
        next.add(Math.max(list.get(size-1)-1,0)/2);
        list=next;
    }
    return Math.min(1.0,list.get(query_glass));
}

880. Decoded String at Index

注意：

  • “stack”的妙用，simulation without actual copying the whole string
  • 只需keep track of len和经调整后的target index k：
    • if k==len, exactly current char
    • if k==0, also exactly current char
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 String decodeAtIndex(String s, int k) {
    long len=0;
    int n=s.length();
    for(int i=0; i<n; i++){
        char c=s.charAt(i);
        if(c>='0' && c<='9'){
            len*=c-'0';
        }else{
            len++;
        }
    }
    for(int i=n-1; i>=0; i--){
        char c=s.charAt(i);
        
        if(c>='0' && c<='9'){
            len/=c-'0';
            k%=len;
        }else{
            //len=15, k=15, exactly current char
            //len=15, k=0 is equivalent to k=15, still exactly current char
            if(k==len || k==0){
                return ""+c;
            }
            len--;
        }
    }
    return "";
}

1060. Missing Element in Sorted Array

Follow up: Can you find a logarithmic time complexity (i.e., O(log(n))) solution?

思路：

  1. First define a function f(x) that counts the number of missing elements until x.

    • [0,i] should span [nums[0], nums[0]+i]
    • in reality, span [nums[0], nums[i]]
    • missing number between [0,i] = nums[i]-nums[0]-i

  2. Then use binary search with the given function f(x) to find the kth missing element.

  3. be careful of edge case

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 missingElement(int[] nums, int k) {
    int n=nums.length;
    //find smallest idx with totalMissing(i) >= k
    int l=0;
    int r=n-1;
    while(l<r){
        int mid=(l+r)>>1;
        if(totalMissing(nums,mid)<k){
            l=mid+1;
        }else{
            r=mid;
        }
    }
    //if not beyond nums[n-1]
    int t=totalMissing(nums,l);
    if(t>=k){
        return nums[l]-(t-k+1);
    }
    return nums[l]+(k-t);
}

private int totalMissing(int[] nums, int i){
    //[0,i] should span [nums[0], nums[0]+i]
    //in reality, span [nums[0], nums[i]]
    //missing number between [0,i] = nums[i]-nums[0]-i
    return nums[i]-nums[0]-i;
}