leetcode contest biweekly 81

虽然是手速题，结果写完了，发现已经掉到 200 名了，真心太菜了。

6104. 统计星号

题目

给你一个字符串 s ，每两个连续竖线 '|' 为一对。换言之，第一个和第二个 '|' 为一对，第三个和第四个 '|' 为一对，以此类推。

请你返回不在竖线对之间，s 中 '*' 的数目。

注意，每个竖线 '|' 都会恰好属于一个对。

示例 1：

输入：s = "l|*e*et|c**o|*de|"
输出：2
解释：不在竖线对之间的字符加粗加斜体后，得到字符串："l|*e*et|c**o|*de|" 。
第一和第二条竖线 '|' 之间的字符不计入答案。
同时，第三条和第四条竖线 '|' 之间的字符也不计入答案。
不在竖线对之间总共有 2 个星号，所以我们返回 2 。

示例 2：

输入：s = "iamprogrammer"
输出：0
解释：在这个例子中，s 中没有星号。所以返回 0 。

示例 3：

输入：s = "yo|uar|e**|b|e***au|tifu|l"
输出：5
解释：需要考虑的字符加粗加斜体后："yo|uar|e**|b|e***au|tifu|l" 。不在竖线对之间总共有 5 个星号。所以我们返回 5 。

提示：

1 <= s.length <= 1000
s 只包含小写英文字母，竖线 '|' 和星号 '*' 。
s 包含偶数个竖线 '|' 。

提示：

1 <= s.length <= 1000
s 由小写和大写英文字母组成

地址

https://leetcode.cn/contest/biweekly-contest-81/problems/count-asterisks/

题意

直接遍历

思路

题目出的比较稀烂，反正暴力即可，先将相邻的 | 之间的 * 全部去掉，然后再统计字符串中的 * 即可。
复杂度分析：

时间复杂度：$O(n)$, 其中 $n$ 为字符串的长度。
空间复杂度：$O(n)$，其中 $n$ 为字符串的长度。

代码

class Solution {
public:
    int countAsterisks(string s) {
        vector<int> arr;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '|'){
                arr.emplace_back(i);
            }
        }
        for (int i = 0; i < arr.size(); i += 2) {
            for (int j = arr[i]; i + 1 < arr.size() && j <= arr[i + 1]; j++) {
                if (s[j] == '*') {
                    s[j] = ' ';
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '*') {
                ans++;
            }
        }
        return ans;
    }
};

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

题目

给你一个整数 n ，表示一张无向图中有 n 个节点，编号为 0 到 n - 1 。同时给你一个二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示节点ai和 bi 之间有一条无向边。

请你返回无法互相到达的不同点对数目。

示例 1：

输入：n = 3, edges = [[0,1],[0,2],[1,2]]
输出：0
解释：所有点都能互相到达，意味着没有点对无法互相到达，所以我们返回 0 。

示例 2：

输入：n = 7, edges = [[0,2],[0,5],[2,4],[1,6],[5,4]]
输出：14
解释：总共有 14 个点对互相无法到达：
[[0,1],[0,3],[0,6],[1,2],[1,3],[1,4],[1,5],[2,3],[2,6],[3,4],[3,5],[3,6],[4,6],[5,6]]
所以我们返回 14 。

提示：

1 <= n <= 105
0 <= edges.length <= 2 * 105
edges[i].length == 2
0 <= ai, bi < n
ai != bi
不会有重复边。

地址

https://leetcode.cn/contest/biweekly-contest-81/problems/count-unreachable-pairs-of-nodes-in-an-undirected-graph/

题意

BFS

思路

典型的图的问题，首先求图中的所有连通区域的数目，我们可以用简单的 BFS 或者 UNION 均可，求出所有的联通区域包含节点的个数的数组为 $arr$，设联通区域的数目为 $n$ 个。则根据组合数组中的抽样定理可以知道，所有可能的点对的数目为:
$$
tot = \sum_{i=0}^{n}(arr[i] \times \sum_{j=0}^{i-1}arr[j])
$$
复杂度分析：

时间复杂度：$O(n)$，其中 $n$ 为节点的数目。
空间复杂度：$O(n)$，其中 $n$ 为节点的数目。

代码

class Solution {
public:
    long long countPairs(int n, vector<vector<int>>& edges) {
        vector<int> dp;
        vector<int> visit(n, false);
        vector<vector<int>> graph(n);
        for (auto v : edges) {
            graph[v[0]].emplace_back(v[1]);
            graph[v[1]].emplace_back(v[0]);
        }
        for (int i = 0; i < n; i++) {
            if (visit[i]) continue;
            queue<int> qu;
            qu.emplace(i);
            visit[i] = true;
            int total = 0;
            while(!qu.empty()) {
                int curr = qu.front();
                qu.pop();
                total++;
                for (auto next : graph[curr]) {
                    if (visit[next]) continue;
                    qu.emplace(next);
                    visit[next] = true;
                }
            }
            dp.emplace_back(total);
        }
        long long ans = 0;
        long long sum = dp[0];
        for (int i = 1; i < dp.size(); i++) {
            ans += sum * dp[i];
            sum += dp[i];
        }
        return ans;
    }
};

6105. 操作后的最大异或和

题目

给你一个下标从 0 开始的整数数组 nums 。一次操作中，选择任意非负整数 x 和一个下标 i ，更新 nums[i] 为 nums[i] AND (nums[i] XOR x) 。

注意，AND 是逐位与运算，XOR 是逐位异或运算。

请你执行任意次更新操作，并返回 nums 中所有元素最大逐位异或和。

示例 1：

输入：nums = [3,2,4,6]
输出：7
解释：选择 x = 4 和 i = 3 进行操作，num[3] = 6 AND (6 XOR 4) = 6 AND 2 = 2 。
现在，nums = [3, 2, 4, 2] 且所有元素逐位异或得到 3 XOR 2 XOR 4 XOR 2 = 7 。
可知 7 是能得到的最大逐位异或和。
注意，其他操作可能也能得到逐位异或和 7 。

示例 2：

输入：nums = [1,2,3,9,2]
输出：11
解释：执行 0 次操作。
所有元素的逐位异或和为 1 XOR 2 XOR 3 XOR 9 XOR 2 = 11 。
可知 11 是能得到的最大逐位异或和。

提示：

1 <= nums.length <= 105
0 <= nums[i] <= 108

地址

https://leetcode.cn/contest/biweekly-contest-81/problems/maximum-xor-after-operations/

题意

数学问题，贪心算法

思路

简单的数学问题，由于题目中明确说了 x 可以为任意值，这就很好办，nums[i] XOR x 可以变为任何值，nums[i] AND (nums[i] XOR x) 则表明我们可以保留 nums[i] 中数位为 1 的任何一位，因此我们统计数组中所有的数中数位出为 1 出现的个数，只要是某个数位上存在某个元素该数位为 1 则我们一定可以将其保留，问题最终转变为统计所有的数位即可，然后将所有出现过的数位全部置为 1 即可得到最大值。
复杂度分析：

时间复杂度：$O(C \times n)$, $n$ 表示数组的数目。
空间复杂度：$O(C)$，$C$ 表示数位的数目。

代码

class Solution {
public:
    int maximumXOR(vector<int>& nums) {
        vector<int> cnt(32);
        for (auto v : nums) {
            for (int i = 0; i < 32; i++) {
                if (v & (1 << i)) {
                    cnt[i] = 1;
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < 32; i++) {
            if (cnt[i]) {
                ans |= (1 << i);
            }
        }
        return ans;
    }
};

6107. 不同骰子序列的数目

题目

给你一个整数 n 。你需要掷一个 6 面的骰子 n 次。请你在满足以下要求的前提下，求出不同骰子序列的数目：

序列中任意相邻数字的最大公约数为 1 。
序列中相等的值之间，至少有 2 个其他值的数字。正式地，如果第 i 次掷骰子的值等于第 j 次的值，那么 abs(i - j) > 2 。
请你返回不同序列的总数目。由于答案可能很大，请你将答案对 109 + 7 取余后返回。

如果两个序列中至少有一个元素不同，那么它们被视为不同的序列。

示例 1：

输入：n = 4
输出：184
解释：一些可行的序列为 (1, 2, 3, 4) ，(6, 1, 2, 3) ，(1, 2, 3, 1) 等等。
一些不可行的序列为 (1, 2, 1, 3) ，(1, 2, 3, 6) 。
(1, 2, 1, 3) 是不可行的，因为第一个和第三个骰子值相等且 abs(1 - 3) = 2 （下标从 1 开始表示）。
(1, 2, 3, 6) i是不可行的，因为 3 和 6 的最大公约数是 3 。
总共有 184 个不同的可行序列，所以我们返回 184 。

示例 2：

输入：n = 2
输出：22
解释：一些可行的序列为 (1, 2) ，(2, 1) ，(3, 2) 。
一些不可行的序列为 (3, 6) ，(2, 4) ，因为最大公约数不为 1 。
总共有 22 个不同的可行序列，所以我们返回 22 。

提示：

1 <= n <= 104

地址

https://leetcode.cn/contest/biweekly-contest-81/problems/number-of-distinct-roll-sequences/

题意

动态规划

思路

典型的动态规划，我们设 $dp[i][j][k]$ 表示抛掷骰子 $i$ 次且倒数第一次和第二次的数字为 $j,k$ 的序列数目，则可以知道如下递推公式:
$$
dp[i][j][k] = \sum_{p=1}^{6}dp[i-1][k][p] \qquad(j \neq k, k \neq p, j \neq p, \gcd(j,k) = 1, \gcd(k,p) = 1)
$$
按照上述的递推公式即可得到所有可能的组合,需要对过程变量和最终结果取模即可。
复杂度分析：

时间复杂度：$n \times C^3 $， $n$ 表示抛掷次数, $C = 6$ 为骰子的取值范围。
空间复杂度：$n \times C^2$, $n$ 表示抛掷次数，$C = 6$ 为骰子的取值范围。

代码

class Solution {
public:
    int distinctSequences(int n) {
        long long mod = 1e9 + 7;
        if (n == 1) {
            return 6;
        }
        vector<vector<vector<long long>>> dp(n + 1, vector<vector<long long>>(7, vector<long long>(7)));
        for(int i = 1; i <= 6; i++) {
            for (int j = 1; j <= 6; j++) {
                if (__gcd(i,j) == 1 && i != j) {
                    dp[2][i][j] = 1;
                }
            }
        }
        for (int i = 3; i <= n; i++) {
            for (int j = 1; j <= 6; j++) {
                for (int k = 1; k <= 6; k++) {
                    if (__gcd(j, k) > 1 || j == k) continue;
                    for (int m = 1; m <= 6; m++) {
                        if (j == m) continue;
                        if (__gcd(k, m) > 1 || k == m) continue;
                        dp[i][j][k] = (dp[i][j][k] + dp[i-1][k][m]) % mod;
                    }
                }
            }
        }
        long long tot = 0;
        for (int i = 1; i <= 6; i++) {
            for (int j = 1; j <= 6; j++) {
                if (__gcd(i,j) == 1 && i != j) {
                    tot = (tot + dp[n][i][j]) % mod;
                }
            }
        }
        return tot;
    }
};

欢迎关注和打赏，感谢支持！

关注我的博客: http://mikemeng.org/
关注我的知乎：https://www.zhihu.com/people/da-hua-niu
关注我的微信公众号: 公务程序猿

Tags: 力扣周赛

← leetcode biweekly contest 78 leetcode biweekly contest 294 →

扫描二维码，分享此文章