0%

leetcode-第205场周赛

Posted on In ,

第205场周赛

替换所有的问号

image1

直接模拟即可，如果是’?’，记录前后字符。

1
class Solution {
2
    public String modifyString(String s) {
3
        char[] str = s.toCharArray();
4
        int n = s.length();
5
        for(int i=0; i<n; i++){
6
            if(str[i] == '?'){
7
                int[] used = new int['z'-'a'+1];
8
                if(i-1>=0 && str[i-1]!='?'){
9
                    used[str[i-1]-'a'] = 1;
10
                }
11
                if(i+1<n && str[i+1]!='?'){
12
                    used[str[i+1]-'a'] = 1;
13
                }
14
                for(int j=0; j<'z'-'a'+1; j++){
15
                    if(used[j] == 0){
16
                        str[i] = (char)('a'+j);
17
                        break;
18
                    }
19
                }
20
            }
21
        }
22
        return new String(str);
23
    }
24
}

复杂度分析：

  • 时间复杂度：$O(n)$。
  • 空间复杂度：$O(n*26)$。

2.数的平方等于两数乘积的方法数

image2

也是直接模拟，可以先做预处理，即求出某一数组的平方，用map存储，这里需要注意要使用long，因为int为溢出。

1
class Solution {
2
    public int numTriplets(int[] nums1, int[] nums2) {
3
        return get(nums1, nums2) + get(nums2, nums1);
4
    }
5
6
    public int get(int[] a, int[] b){
7
        int ans = 0;
8
        Map<Long, Integer> map = new HashMap<Long, Integer>();
9
        for(int i=0; i<b.length; i++){
10
            long res = (long)b[i] * b[i];
11
            int count = map.getOrDefault(res, 0);
12
            map.put(res, count+1);
13
        }
14
        for(int i=0; i<a.length; i++){
15
            for(int j=i+1; j<a.length; j++){
16
                long target = (long) a[i] * a[j];
17
                if(map.containsKey(target)){
18
                    ans += map.get(target);
19
                }
20
            }
21
        }
22
        return ans;
23
    }
24
}

复杂度分析：

  • 时间复杂度：$O(n^2)$。
  • 空间复杂度：$O(n)$。

3.避免重复字母的最小删除成本

image3

采用贪心策略，每次删除成本最小的，如果遇到一连串重复的字母，例如aaaa，那么最后必定只剩下一个a，那么只需留下成本最高的那么字母a即可。

1
class Solution {
2
    public int minCost(String s, int[] cost) {
3
        int ans = 0;
4
        char[] str = s.toCharArray();
5
        for(int i=0; i<s.length(); i++){
6
            int sum = cost[i];
7
            int max = cost[i];
8
            char c = str[i];
9
            while(i+1<s.length() && str[i+1]==c){
10
                i++;
11
                sum += cost[i];
12
                max = Math.max(max, cost[i]);
13
            }
14
            ans += sum-max;
15
        }
16
        return ans;
17
    }
18
}

复杂度分析：

  • 时间复杂度：$O(n)$。
  • 空间复杂度：$O(n)$。

4.保证图可完全遍历

image4

对于Alice来说，如果图可完全遍历，那么类型1和类型3的边的数目必定为n-1（n为图中节点数）。对于Bob来说也一样，那么我们可以使用并查集来计算边数，如果不为n-1，那么就返回-1。之后再计算多余的边数，对于Alice来说，如果图可完全遍历，那么除去公共边（类型3的边），只需要n-1-commonEdge的边数，对于Bob来说也是这样。那么总的来说对于Alice和Bob，如果两人都想要图可完全遍历，那么只需要2*(n-1-commonEdge)+commonEdge=2*(n-1)-commonEdge即可，其余的边就是多余的边。其中commonEdge的数目可以用并查集来确定。在并查集算法中，对于每一条边对应的两个顶点，我们检查这两个顶点是否已经在一个连通分量中，若是，则这条边为冗余边，可以直接去掉。这也是寻找最小生成树的过程。

1
class Solution {
2
    public int maxNumEdgesToRemove(int n, int[][] edges) {
3
        DSU dsu = new DSU(n+1);
4
        dsu.reset();
5
        int t1 = 0;
6
        for(int[] e : edges){
7
            if(e[0]!=2 && dsu.find(e[1])!=dsu.find(e[2])){
8
                t1++;
9
                dsu.merge(e[1], e[2]);
10
            }
11
        }
12
        dsu.reset();
13
        int t2 = 0;
14
        for(int[] e : edges){
15
            if(e[0]!=1 && dsu.find(e[1])!=dsu.find(e[2])){
16
                t2++;
17
                dsu.merge(e[1], e[2]);
18
            }
19
        }
20
        if(t1!=n-1 || t2!=n-1){
21
            return -1;
22
        }
23
        int cnt = 0;
24
        dsu.reset();
25
        for(int[] e : edges){
26
            if(e[0]==3 && dsu.find(e[1])!=dsu.find(e[2])){
27
                cnt++;
28
                dsu.merge(e[1], e[2]);
29
            }
30
        }
31
        int retain = 2*(n-1)-cnt;
32
        return edges.length-retain;
33
    }
34
}
35
36
public class DSU{
37
    int[] p;
38
    int[] rank;
39
40
    public DSU(int n){
41
        p = new int[n];
42
        rank = new int[n];
43
        reset();
44
    }
45
46
    public void reset(){
47
        for(int i=0; i<p.length; i++){
48
            p[i] = i;
49
            rank[i] = 0;
50
        }
51
    }
52
53
    public int find(int a){
54
        if(p[a] == p[p[a]]){
55
            return p[a];
56
        }
57
        return p[a] = find(p[a]);
58
    }
59
60
    public void merge(int a, int b){
61
        a = find(a);
62
        b = find(b);
63
        if(a == b){
64
            return;
65
        }
66
        if(rank[a] == rank[b]){
67
            rank[a]++;
68
        }
69
        if(rank[a] < rank[b]){
70
            int tmp = b;
71
            b = a;
72
            a = tmp;
73
        }
74
        p[b] = a;
75
    }
76
}

复杂度分析：

  • 时间复杂度：$O(n)$。
  • 空间复杂度：$O(n)$。