leetcode contest biweekly 81

leetcode contest biweekly 81

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

6104. 统计星号

题目

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

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

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

示例 1：

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

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

示例 3：
1
2
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/

题意

直接遍历

思路

  1. 题目出的比较稀烂，反正暴力即可，先将相邻的 | 之间的 * 全部去掉，然后再统计字符串中的 * 即可。
  2. 复杂度分析：
  • 时间复杂度：$O(n)$, 其中 $n$ 为字符串的长度。
  • 空间复杂度：$O(n)$，其中 $n$ 为字符串的长度。

    代码

    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
    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：

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

示例 2：
1
2
3
4
5
输入：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

思路

  1. 典型的图的问题，首先求图中的所有连通区域的数目，我们可以用简单的 BFS 或者 UNION 均可，求出所有的联通区域包含节点的个数的数组为 $arr$，设联通区域的数目为 $n$ 个。则根据组合数组中的抽样定理可以知道，所有可能的点对的数目为:
  2. 复杂度分析：
  • 时间复杂度：$O(n)$，其中 $n$ 为节点的数目。
  • 空间复杂度：$O(n)$，其中 $n$ 为节点的数目。

    代码

    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
    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：

1
2
3
4
5
6
输入：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：
1
2
3
4
5
输入：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/

题意

数学问题，贪心算法

思路

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

    代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    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：

1
2
3
4
5
6
7
输入：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：
1
2
3
4
5
输入：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/

题意

动态规划

思路

  1. 典型的动态规划，我们设 $dp[i][j][k]$ 表示抛掷骰子 $i$ 次且倒数第一次和第二次的数字为 $j,k$ 的序列数目，则可以知道如下递推公式:按照上述的递推公式即可得到所有可能的组合,需要对过程变量和最终结果取模即可。
  2. 复杂度分析：
  • 时间复杂度：$n \times C^3 $， $n$ 表示抛掷次数, $C = 6$ 为骰子的取值范围。
  • 空间复杂度：$n \times C^2$, $n$ 表示抛掷次数，$C = 6$ 为骰子的取值范围。

代码

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
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;
    }
};

#

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

力扣周赛
#力扣周赛
leetcode contest biweekly 81
http://example.com/2022/01/01/力扣周赛题解/11/
Author
Mike Meng
Posted on
January 1, 2022
Updated on
September 8, 2026
Licensed under