0%

leetcode-第211场周赛

Posted on In ,

第211场周赛

##两个相同字符之间的最长子字符串

image1

遍历一遍字符串，统计字符最早出现的位置和最晚出现的位置，两者之差就是子字符串的长度。之后再进行比较得到最长的子字符串。

1
class Solution {
2
    public int maxLengthBetweenEqualCharacters(String s) {
3
        int[][] index = new int[26][2];
4
        for(int i=0; i<26; i++){
5
            Arrays.fill(index[i], -1);
6
        }
7
        for(int i=0; i<s.length(); i++){
8
            char c = s.charAt(i);
9
            if(index[c-'a'][0] == -1){
10
                index[c-'a'][0] = i;
11
            }else{
12
                if(i > index[c-'a'][1]){
13
                    index[c-'a'][1] = i;
14
                }
15
            }
16
        }
17
        int ans = -1;
18
        for(int i=0; i<26; i++){
19
            if(index[i][0]!=-1 && index[i][1]!=-1){
20
                ans = Math.max(ans, index[i][1]-index[i][0]-1);
21
            }
22
        }
23
        return ans;
24
    }
25
}

执行操作后字典序最小的字符串

image2

由于数据规模不大，所以可以枚举出所有可能的情况并得到最小的字符串。

对于累加操作来说，一个字符串经过若干次操作后，一定还会回到初始的样子。举例分析可以得到，对于步长a来说，一个字符串最多经过十次累加操作，就会变成最开始的字符串。

对于轮转操作来说，如果b是奇数位轮转，那么字符串原来偶数位置上的数就会在奇数位置上，奇数位置上的数就会在偶数位置上，那么对于偶数位置上的数来说，也会有累加操作。如果b是偶数位轮转，那么奇数位置上的数仍然会在奇数位置上，偶数位置上的数也仍然会在偶数位置上，所以不需要讨论偶数位置上进行累加操作的情况。

1
class Solution {
2
    public String findLexSmallestString(String s, int a, int b) {
3
        String ans = s;
4
        int len = s.length();
5
        for(int i=0; i<len; i++){
6
            // 轮转
7
            s = s.substring(b, len) + s.substring(0,b);
8
            for(int j=0; j<=9; j++){
9
                char[] chars = s.toCharArray();
10
                // 修改奇数位置
11
                for(int k=1; k<len; k+=2){
12
                    chars[k] += a;
13
                    if(chars[k] > '9'){
14
                        chars[k] = (char)('0' + (chars[k]-'9'-1));
15
                    }
16
                }
17
                if(b % 2 == 1){
18
                    // b为奇数，此时通过轮转，也能修改偶数位置
19
                    for (int m=0; m<=9; m++){
20
                        for(int k=0; k<len; k+=2){
21
                            chars[k] += a;
22
                            if(chars[k] > '9'){
23
                                chars[k] = (char)('0' + (chars[k]-'9'-1));
24
                            }
25
                        }
26
                        s = new String(chars);
27
                        if(s.compareTo(ans)<0){
28
                            ans = s;
29
                        }
30
                    }
31
                }else{
32
                    s = new String(chars);
33
                    if(s.compareTo(ans)<0){
34
                        ans = s;
35
                    }
36
                }
37
            }
38
        }
39
        return ans;
40
    }
41
}

无矛盾的最佳球队

image3

首先进行排序，按年龄从小到大排，如果年龄相同，就按照分数从小到大排序。

记$dp[i]$是以第$i$位球员结束的最大分数。考虑第$i$个球员，如果前$i-1$个球员里存在分数比他小的球员$j$，那么$dp[i]=dp[j]+scores[i]$，这是因为球员已经按照年龄排序，所以第$j$个球员年龄一定比第$i$个球员小，那么此时将第$i$个球员加入球队，一定不会产生矛盾。

答案就是$dp[i]$中的最大值。

1
class Solution {
2
    public int bestTeamScore(int[] scores, int[] ages) {
3
        int ans = 0;
4
        if(scores.length == 1){
5
            return scores[0];
6
        }
7
        int[][] arr = new int[scores.length][2];
8
        for(int i=0; i<scores.length; i++){
9
            arr[i][0] = ages[i];
10
            arr[i][1] = scores[i];
11
        }
12
        Arrays.sort(arr, new Comparator<int[]>() {
13
            @Override
14
            public int compare(int[] o1, int[] o2) {
15
                if(o1[0] == o2[0]){
16
                    return o1[1]-o2[1];
17
                }else {
18
                    return o1[0]-o2[0];
19
                }
20
            }
21
        });
22
        int[] dp = new int[scores.length];
23
        for(int i=0; i<scores.length; i++){
24
            dp[i] = arr[i][1];
25
        }
26
        for(int i=0; i<scores.length; i++){
27
            for(int j=0; j<i; j++){
28
                if(arr[j][1] <= arr[i][1]){
29
                    dp[i] = Math.max(dp[i], dp[j]+arr[i][1]);
30
                }
31
            }
32
            ans = Math.max(ans, dp[i]);
33
        }
34
        return ans;
35
    }
36
}

带阈值的图连通性

image4

一般思路就是先建图，然后逐个计算每两个图之间是否有连接，且是否超过阈值。但因为$N=10^4$，所以会超时。可以反向思考，由连通性可以想到并查集这一数据结构。然后再考虑阈值，我们可以从$threshold+1$开始枚举因子加入并查集，例如$threshold+1,(threshold+1)2,(threshold+1)3$。并查集的连边和查询操作都近似$O(1)$。

1
class Solution {
2
    public List<Boolean> areConnected(int n, int threshold, int[][] queries) {
3
        DSU dsu = new DSU(n+1);
4
        for(int i=threshold+1; i<=n; i++){
5
            for(int j=i*2; j<=n; j+=i){
6
                dsu.merge(i,j);
7
            }
8
        }
9
        List<Boolean> ans = new ArrayList<>();
10
        for(int[] query : queries){
11
            int u = query[0], v = query[1];
12
            ans.add(dsu.find(u)==dsu.find(v));
13
        }
14
        return ans;
15
16
    }
17
}
18
19
class DSU {
20
    int[] p;
21
    int[] rank;
22
23
    public DSU(int n){
24
        p = new int[n];
25
        rank = new int[n];
26
        reset();
27
    }
28
29
    public void reset(){
30
        for(int i=0; i<p.length; i++){
31
            p[i] = i;
32
            rank[i] = 0;
33
        }
34
    }
35
36
    public int find(int a){
37
        if(p[a] == p[p[a]]){
38
            return p[a];
39
        }
40
        return p[a] = find(p[a]);
41
    }
42
43
    public void merge(int a, int b){
44
        a = find(a);
45
        b = find(b);
46
        if(a == b){
47
            return;
48
        }
49
        if (rank[a] == rank[b]){
50
            rank[a]++;
51
        }
52
        if(rank[a] < rank[b]){
53
            int tmp = b;
54
            b = a;
55
            a = tmp;
56
        }
57
        p[b] = a;
58
    }
59
}