leetcode weekly contest 333
leetcode weekly contest 333
周赛的题目质量很高，确实上了一个档次。
6362.合并两个二维数组 - 求和法
给你两个 二维 整数数组 nums1 和 nums2.
nums1[i] = [idi, vali]表示编号为idi的数字对应的值等于vali。nums2[i] = [idi, vali]表示编号为idi的数字对应的值等于vali。
每个数组都包含 互不相同 的 id ，并按 id 以 递增 顺序排列。
请你将两个数组合并为一个按 id 以递增顺序排列的数组，并符合下述条件：
- 只有在两个数组中至少出现过一次的 id 才能包含在结果数组内。
- 每个 id 在结果数组中 只能出现一次 ，并且其对应的值等于两个数组中该 id 所对应的值求和。如果某个数组中不存在该 id ，则认为其对应的值等于
0。
返回结果数组。返回的数组需要按 id 以递增顺序排列。
示例 1：
1 | |
示例 2：
1 | |
提示：
1 <= nums1.length, nums2.length <= 200nums1[i].length == nums2[j].length == 21 <= idi, vali <= 1000- 数组中的 id 互不相同
- 数据均按 id 以严格递增顺序排列
地址
https://leetcode.cn/contest/weekly-contest-333/problems/merge-two-2d-arrays-by-summing-values/
题意
直接模拟
思路
- 简单题目，利用哈希表，将相同 $id$ 的元素的和相加，并并入只在一个数组中出现的元素，然后按照 $id$ 大小进行排序即可；
- 复杂度分析：
1 | |
6365. 将整数减少到零需要的最少操作数
给你一个正整数 n ，你可以执行下述操作 任意 次：
n加上或减去2的某个 幂
返回使 n 等于 0 需要执行的 最少 操作数。
如果 x == 2i 且其中 i >= 0 ，则数字 x 是 2 的幂。
示例 1：
1 | |
示例 2：
1 | |
提示：
1 <= n <= 105
地址
题意
广度优先搜索
思路
- 应该有贪心思路的解法的，结果全部都弄成了暴力的广度优先搜索和深度优先搜索，题目就变得非常简单了，直接暴力搜索即可。
- 复杂度分析：
- 时间复杂度：$O(n \log n)$，其中 $n$ 为数组的长度。
- 空间复杂度：$O(n)$，主要为排序需要空间。
代码
1 | |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
int minOperations(int n) {
unordered_map<int, int> memo;
function<int(int)> dfs = [&](int x)->int {
if (memo.count(x)) {
return memo[x];
}
if (__builtin_popcount(x) == 1) {
return 1;
}
int y = x - (x & (x - 1));
int ret = min(dfs(x + y), dfs(x - y)) + 1;
memo[x] = ret;
return ret;
};
return dfs(n);
}
};
1 | |
6364. 无平方子集计数
给你一个正整数数组 nums 。
如果数组 nums 的子集中的元素乘积是一个 无平方因子数 ，则认为该子集是一个 无平方 子集。
无平方因子数 是无法被除 1 之外任何平方数整除的数字。
返回数组 nums 中 无平方 且 非空 的子集数目。因为答案可能很大，返回对 109 + 7 取余的结果。
nums 的 非空子集 是可以由删除 nums 中一些元素（可以不删除，但不能全部删除）得到的一个数组。如果构成两个子集时选择删除的下标不同，则认为这两个子集不同。
示例 1：
1 | |
示例 2：
1 | |
提示：
1 <= nums.length <= 10001 <= nums[i] <= 30
地址
https://leetcode.cn/contest/weekly-contest-333/problems/count-the-number-of-square-free-subsets/
题意
状态压缩动态规划
思路
- 题目给定的提示点在于 $1 \le nums[i] \le 30$，我们知道一个子集中含有平方子集，即该子集中质因子的次数出现超过两次即会被平方数相除，我们仔细观察的点在于 $[1,30$ 之间只有 $10$ 个质数，因此我们可以用状态压缩。设 $dp[i][state]$ 表示前 $i$ 个元素中构成的子集中的出现的质因数为 $mask$，在此 $mask$ 用二进制掩码表示，第 $i$ 为 $1$ 则表示从 $i$ 个质因子已经在子集中出现。
- 动态规划递推公式如下：首先我们将当前的元素 $nums[i]$ 分解为质因子的掩码 $curr$，如果某个质因子出现两次，则表示 $nums[i]$ 无法加入到任何子集中，假设当前的子集中已经包含的质因子为 $mask$，此时 $curr$ 与 $mask$ 不能有交集，否则一定会出现某个质因子的次数出现了大于 $1$ 次。因此我们将 $mask$ 尝试与所有可能的子集合并，如果不存在重复的质因子，则可以将 $nums[i]$ 加入到该子集中。
- 复杂度分析：
- 时间复杂度：$O(n \times 2^{\alpha (U)})$，其中 $n$ 为数组的长度, $U$ 表示数组中的最大元素。
- 空间复杂度：$O(2^{\alpha (U)})$。
代码
动态规划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
46class Solution {
public:
int squareFreeSubsets(vector<int>& nums) {
int n = nums.size();
vector<int> primer;
vector<int> visit(31, 0);
for (int i = 2; i <= 30; i++) {
if (!visit[i]) {
primer.emplace_back(i);
for (int j = i; j <= 30; j += i) {
visit[j] = 1;
}
}
}
long long mod = 1e9 + 7;
vector<long long> dp(1024);
dp[0] = 1;
for (int i = 1; i <= n; i++) {
vector<long long> ndp = dp;
bool issquare = false;
int mask = 0;
for (int j = 0; j < primer.size(); j++) {
if (nums[i - 1] % primer[j] == 0) {
mask |= (1 << j);
}
if (nums[i - 1] % (primer[j] * primer[j]) == 0) {
issquare = true;
break;
}
}
if (issquare) {
continue;
}
for (int j = 0; j < 1024; j++) {
if (j & mask) continue;
ndp[j | mask] = (dp[j] + ndp[j | mask]) % mod;
}
dp = move(ndp);
}
long long res = 0;
for (int i = 0; i < 1024; i++) {
res = (res + dp[i]) % mod;
}
return (res - 1 + mod) % mod;
}
};
6363. 找出对应 LCP 矩阵的字符串
对任一由 n 个小写英文字母组成的字符串 word ，我们可以定义一个 n x n 的矩阵，并满足：
lcp[i][j]等于子字符串word[i,...,n-1]和word[j,...,n-1]之间的最长公共前缀的长度。
给你一个 n x n 的矩阵 lcp 。返回与 lcp 对应的、按字典序最小的字符串 word 。如果不存在这样的字符串，则返回空字符串。
对于长度相同的两个字符串 a 和 b ，如果在 a 和 b 不同的第一个位置，字符串 a 的字母在字母表中出现的顺序先于 b 中的对应字母，则认为字符串 a 按字典序比字符串 b 小。例如，"aabd" 在字典上小于 "aaca" ，因为二者不同的第一位置是第三个字母，而 'b' 先于 'c' 出现。
示例 1：
1 | |
示例 2：
1 | |
示例 3：
1 | |
提示：
1 <= n == ``lcp.length == ``lcp[i].length<= 10000 <= lcp[i][j] <= n
地址
https://leetcode.cn/contest/weekly-contest-333/problems/find-the-string-with-lcp/
题意
思维题目
思路
- 检测矩阵的合法性：首先我们需要检测一下 $lcp$ 矩阵是否合法，设目标字符串为 $s$，长度为 $n$，我们可以观察矩阵得到以下性质:
- $lcp[i][i] = n - i$，起点相同的两个后缀一定相等；
- $lcp[i][j] > 0$ 时，此时一定满足 $s[i] = s[j]$；
- $lcp[i][j]$ 的最大值一定不能超过 $n - \min(i,j)$；
- $lcp[i][j] = lcp[i + 1][j + 1] + 1$；
- 矩阵一定是一个对称矩阵，$lcp[i][j] = lcp[j][i]$；
我们根据以上五个合法性质去检测当前的矩阵是否满足上述要求，如果不满足上述要求，则直接返回空字符串；
- 构造合法的字符串：由于题目要求构造字典序最小的字符串，此时我们从最小的 $c = \text{`a’}$ 开始从左到右填充每个字符：
- 如果当前字符 $s[i]$ 未填充，则我们将 $c$ 填充到当前位置，并将所有与 $s[i]$ 相等的位置 $s[j]$ 也全部填上 $c$，此时 $s[i] \neq s[k] \quad if \quad k < s$，因此我们选择填充当前可以填充的字典序最小的字符；
- 每次填充完后，我们将 $c$ 加 $1$，如果全部 $26$ 个字符无法完成填充，则直接返回空字符；
- 题目感觉本身不需要特别复杂的算法，但是思考过程还是蛮有意思，值得好好思考的一个题目；
- 复杂度分析：
- 时间复杂度：$O(n^2)$，其中 $n$ 为字符串的长度。
- 空间复杂度：$O(1)$。
代码
1 | |
欢迎关注和打赏，感谢支持！
- 关注我的博客: http://whistle-wind.com/
- 关注我的知乎：https://www.zhihu.com/people/da-hua-niu
- 关注我的微信公众号: 公务程序猿
