LeetCode第81场双周赛

LeetCode第81场双周赛

链接跳转

    6104. 统计星号
1

思路:
先遍历查看一共多少个"*“号记ans, 再找出来所有两个”|“之间的所有”**"号记cnt，最后返回ans - cnt

代码:

class Solution {
public:
    int countAsterisks(string s) {
        int cnt = 0;
        int n = s.size();
        int pre = -1;
        for(int i = 0; i < n; ++ i){
            if(s[i] == '|'){
                if(pre == -1)
                    pre = i;
                else{
                    for(int j = pre; j < i; ++ j) if(s[j] == '*') cnt ++;
                    pre = -1;
                }
            }
        }
        int ans = 0;
        for(int i = 0; i < n; ++ i) if(s[i] == '*') ans ++;
        return ans - cnt;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

    6105. 统计无向图中无法互相到达点对数
1

思路:
其实就是求不连通图的个数以及每个图中的点数，dfs就行啦，先链式向前星存储图,最后跑dfs，最后再用乘法原则，算出所有方案

代码:

const int N = 1e5 + 10;
class Solution {
public:
    
    int h[N], e[N << 2], ne[N << 2], idx;
    int st[N];
    int g[N];
    int a[N];
    
    void add(int a, int b){
        e[idx] = b, ne[idx] = h[a], h[a] = idx++;
    }
    
    int dfs(int x){
        if(st[x]) return 0;
        st[x] = true;
        int res = 1;
        for(int i = h[x]; ~i; i = ne[i]){
            int j = e[i];
            res += dfs(j);
        }
        return res;
    }
    
    long long countPairs(int n, vector<vector<int>>& edges) {
            memset(h, -1, sizeof h);
            int m = edges.size();
            for(int i = 0; i < m; ++ i)
                add(edges[i][0], edges[i][1]), add(edges[i][1], edges[i][0]);
            memset(st, 0, sizeof st);
            int cnt = 0;
            for(int i = 0; i < n; ++ i){
                if(!st[i]){
                    int x = dfs(i);
                    a[++cnt] = x;
                }
            }
            long long res = 0;
            a[0] = 0;
            for(int i = 1; i <= cnt; ++ i) a[i] += a[i - 1];
            for(int i = 1; i <= cnt; ++ i) res += (long long)(a[i] - a[i - 1]) * (a[cnt] - a[i]);
            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

    6106. 操作后的最大异或和
1

思路:
考虑: ans = nums[i] AND (nums[i] XOR x)
其实本质就是二进制中 nums[i] 对于第i位而言为1， 而x对于第i为而言为0的结果
因为x任意， 所以这个 ans 可以让第i位为1也可以让第i位为0
最后求 ans 异或和 就是贪心思路：从大大小枚举每一位 对nums[i]说只要存在一个1，那么就为1，这样可以达到最大值

代码:

class Solution {
public:
    int maximumXOR(vector<int>& nums) {
        int ans = 0;
        for(int i = 30; i >= 0; -- i)
            for(int j = 0; j < nums.size(); ++ j)
                if((nums[j] >> i & 1) == 1){
                    //cout << i << " ";
                    ans += 1 << i;
                    break;
                }
        cout << endl;
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

    6107. 不同骰子序列的数目
1

思路:
一眼看出来是dp， 有两个条件 1.最大公约数为1 2.相同数字下标距离至少大于2
最大公约数: 可以 预处理一下 因为 考虑来考虑去都是 1-6之间的考虑
而下标距离大于2: 如果考虑当前第i次掷色子,只需要考虑 i-1, i-2次掷色子的数就行了 ，只要满足最大公约数为1，且任意两个不相同就行
在预处理的时候就把相同的情况删去

f[i][j][k]: 第i次掷色子为j, 且i - 1次掷色子为k的情况之和
属性:数量
状态转移方程: f[i][j][k] += f[i - 1][k][z](注意此时z要满足gcd(k,z) == 1 and z不为j)
最后记得mod
代码:

const int mod = 1e9 + 7, N = 1e4 + 10;
class Solution {
public:
    
    int f[N][7][7];
    vector<int> p[7];
    
    int gcd(int a, int b){
        return b ? gcd(b, a % b): a;
    }
    
    int distinctSequences(int n) {
        if(n == 1) return 6;
        memset(f, 0, sizeof f);
        
        for(int i = 1; i <= 6; ++ i)
            for(int j = 1; j <= 6; ++ j)
                if(i != j && gcd(i, j) == 1) p[i].push_back(j);
        
        for(int i = 1; i <= 6; ++ i) f[1][i][0] = 1;
        
        for(int i = 1; i <= 6; ++ i)
            for(int j = 0; j < p[i].size(); ++ j) f[2][i][p[i][j]] += f[1][p[i][j]][0];
        
        for(int i = 3; i <= n; ++ i)
            for(int j = 1; j <= 6; ++ j)
                for(int k = 0; k < p[j].size(); ++ k)
                    for(int a = 0; a < p[p[j][k]].size(); ++ a)
                        if(p[p[j][k]][a] != j)
                            f[i][j][p[j][k]] = (f[i - 1][p[j][k]][p[p[j][k]][a]] + f[i][j][p[j][k]]) % mod;
                
        int sum = 0;
        
        for(int i = 1; i <= 6; ++ i)
            for(int j = 0; j < p[i].size(); ++ j) sum = (sum + f[n][i][p[i][j]]) % mod;
        
        return sum;
        
    }
};
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

那么就AC啦, 加油加油