leetcode-第81场双周赛

本文最后更新于：2022年6月26日 晚上

6104. 统计星号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int countAsterisks(string s) {
        
        int cnt = 0;
        int t = 0;
        for (int i = 0; i < s.size(); i++)
        {
            if (s[i] == '|') t++;
            if (t % 2 == 0)
            {
                if (s[i] == '*') cnt ++;
            }
        }
        return cnt;
    }
};

6106. 统计无向图中无法互相到达点对数
无向图，1w个点

考虑补集
不能到达的点对数b = Cn2-可以到达的点对数a

求 有多少个连通块 和 连通块的点数

每个连通块求下组合数，因为同一个连通块中的任意2个点都可以到达。
假设k个连通块中点的数量分别为x1,x2,…xk
则k个连通块可以相互到达的点对数量 a = C x1 2 + C x2 2 + .. + C xk 2;

求每个连通块的点数：2类做法
图的遍历：
DFS
BFS
并查集：使用并查集维护连通块大小

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
typedef long long LL;

class Solution {
public:
    vector<int> p; // p[x] 是x 的父节点
    vector<int> cnt; // 某个集合中点的数量

    // 找 x 的根节点
    int find(int x)
    {   // 判断 x 的父节点 p[x] 是否等于自己, 如果是，则 x=p[x]为根节点，直接返回p[x]
        // 如果不是，则继续找p[x]的根节点并返回，即 p[x] = find(p[x])
        if (p[x] != x) 
            p[x] = find(p[x]);
        return p[x];
    }

    long long countPairs(int n, vector<vector<int>>& edges) {
        // 不连通的数量 = 全集-连通的数量:
        // 不能到达的点对数 = C n 2 - 所有连通块中连通的点对数量(所有连通块中 连通块节点数取2个)

        // 求连通块中节点的数量：并查集
        for (int i = 0; i < n; i++) 
        {
            p.push_back(i); // n个节点，每个节点最初是独立的，自己就是根节点
            cnt.push_back(1); // cnt表示连通块(集合)中的节点个数
        }

        for (auto& e : edges)
        {
            int a = e[0], b = e[1];
            a = find(a), b = find(b);
            if (a != b)
            {
                // 若 a 和 b 不在一个集合中，就计算2个集合中的节点数量之和，并 合并
                cnt[b] += cnt[a]; // 集合的节点个数，只会看集合的根节点x对应的 cnt[find(x)]的数量
                p[a] = b;// a的根节点的父节点是 b的根节点，b的根节点是新的集合的根节点
            }
        }

        LL res = (LL)n * (n - 1) / 2; // *处会爆int
        
        // 遍历所有节点，找到每个集合的根节点
        for (int i = 0; i < n; i++)
        {
            // 这里 p[i]已经是i的根节点了
            // if (p[i] == i) // 节点i的根节点 == i, 即 i 为根节点
            if (find(i) == i) // 也可以继续使用find(i)找i的根节点
                res -= cnt[i] * (LL)(cnt[i] - 1) / 2; // * 处会爆int
        }
        return res;
    }
};

6105. 操作后的最大异或和

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

leetcode周赛

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！