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：

输入：nums1 = [[1,2],[2,3],[4,5]], nums2 = [[1,4],[3,2],[4,1]]
输出：[[1,6],[2,3],[3,2],[4,6]]
解释：结果数组中包含以下元素：
- id = 1 ，对应的值等于 2 + 4 = 6 。
- id = 2 ，对应的值等于 3 。
- id = 3 ，对应的值等于 2 。
- id = 4 ，对应的值等于5 + 1 = 6 。

示例 2：

输入：nums1 = [[2,4],[3,6],[5,5]], nums2 = [[1,3],[4,3]]
输出：[[1,3],[2,4],[3,6],[4,3],[5,5]]
解释：不存在共同 id ，在结果数组中只需要包含每个 id 和其对应的值。

提示：

1 <= nums1.length, nums2.length <= 200
nums1[i].length == nums2[j].length == 2
1 <= idi, vali <= 1000
数组中的 id 互不相同
数据均按 id 以严格递增顺序排列

地址

https://leetcode.cn/contest/weekly-contest-333/problems/merge-two-2d-arrays-by-summing-values/

题意

直接模拟

思路

简单题目，利用哈希表，将相同 $id$ 的元素的和相加，并并入只在一个数组中出现的元素，然后按照 $id$ 大小进行排序即可；
复杂度分析：

时间复杂度：$O((n + m) \log (n + m))$，其中 $m,n$ 为两个数组的长度。
空间复杂度：$O(m + n)$。

代码

class Solution {
public:
    vector<vector<int>> mergeArrays(vector<vector<int>>& nums1, vector<vector<int>>& nums2) {
        unordered_map<int, int> cnt1, cnt2;
        for (auto v : nums1) {
            cnt1[v[0]] = v[1];
        }
        for (auto v : nums2) {
            cnt2[v[0]] = v[1];
        }
        vector<vector<int>> ans;
        for (auto [idx, val] : cnt1) {
            if (cnt2.count(idx)) {
                ans.push_back({idx, val + cnt2[idx]});
            } else {
                ans.push_back({idx, val});
            }
        }
        for (auto [idx, val] : cnt2) {
            if (!cnt1.count(idx)) {
                ans.push_back({idx, val});
            }
        }
        sort(ans.begin(), ans.end());
        return ans;
    }
};

6365. 将整数减少到零需要的最少操作数

给你一个正整数 n ，你可以执行下述操作任意次：

n 加上或减去 2 的某个幂

返回使 n 等于 0 需要执行的最少操作数。

如果 x == 2i 且其中 i >= 0 ，则数字 x 是 2 的幂。

示例 1：

输入：n = 39
输出：3
解释：我们可以执行下述操作：
- n 加上 20 = 1 ，得到 n = 40 。
- n 减去 23 = 8 ，得到 n = 32 。
- n 减去 25 = 32 ，得到 n = 0 。
可以证明使 n 等于 0 需要执行的最少操作数是 3 。

示例 2：

输入：n = 54
输出：3
解释：我们可以执行下述操作：
- n 加上 21 = 2 ，得到 n = 56 。
- n 加上 23 = 8 ，得到 n = 64 。
- n 减去 26 = 64 ，得到 n = 0 。
使 n 等于 0 需要执行的最少操作数是 3 。

提示：

1 <= n <= 105

地址

https://leetcode.cn/contest/weekly-contest-333/problems/minimum-operations-to-reduce-an-integer-to-0/

题意

广度优先搜索

思路

应该有贪心思路的解法的，结果全部都弄成了暴力的广度优先搜索和深度优先搜索，题目就变得非常简单了，直接暴力搜索即可。
复杂度分析：

时间复杂度：$O(n \log n)$，其中 $n$ 为数组的长度。
空间复杂度：$O(n)$，主要为排序需要空间。

代码

class Solution {
public:
    int minOperations(int n) {
        int len = 32 - __builtin_clz(n);
        int lower = 0, upper = 1 << len;
        unordered_set<int> visit;
        visit.emplace(n);
        queue<int> qu;
        qu.emplace(n);
        int step = 0;
        while (!qu.empty()) {
            int sz = qu.size();
            for (int i = 0; i < sz; i++) {
                int curr = qu.front();
                qu.pop();
                if (curr == 0) return step;
                for (int j = 0; j <= len; j++) {
                    /* add one time */
                    int add = curr + (1 << j);
                    if (add <= upper && !visit.count(add)) {
                        visit.emplace(add);
                        qu.emplace(add);
                    }
                    /* sub one time */
                    int sub = curr - (1 << j);
                    if (sub >= lower && !visit.count(sub)) {
                        visit.emplace(sub);
                        qu.emplace(sub);
                    }
                }
            }
            step++;
        }
        return step;
    }
};

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

6364. 无平方子集计数

给你一个正整数数组 nums 。

如果数组 nums 的子集中的元素乘积是一个 无平方因子数 ，则认为该子集是一个 无平方 子集。

无平方因子数 是无法被除 1 之外任何平方数整除的数字。

返回数组 nums 中 无平方 且非空的子集数目。因为答案可能很大，返回对 109 + 7 取余的结果。

nums 的 非空子集 是可以由删除 nums 中一些元素（可以不删除，但不能全部删除）得到的一个数组。如果构成两个子集时选择删除的下标不同，则认为这两个子集不同。

示例 1：

输入：nums = [3,4,4,5]
输出：3
解释：示例中有 3 个无平方子集：
- 由第 0 个元素 [3] 组成的子集。其元素的乘积是 3 ，这是一个无平方因子数。
- 由第 3 个元素 [5] 组成的子集。其元素的乘积是 5 ，这是一个无平方因子数。
- 由第 0 个和第 3 个元素 [3,5] 组成的子集。其元素的乘积是 15 ，这是一个无平方因子数。
可以证明给定数组中不存在超过 3 个无平方子集。

示例 2：

输入：nums = [1]
输出：1
解释：示例中有 1 个无平方子集：
- 由第 0 个元素 [1] 组成的子集。其元素的乘积是 1 ，这是一个无平方因子数。
可以证明给定数组中不存在超过 1 个无平方子集。

提示：

1 <= nums.length <= 1000
1 <= 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$ 个质因子已经在子集中出现。
动态规划递推公式如下：
$$dp[i][curr | mask] = dp[i][curr | mask] + dp[i-1][mask] \quad if (curr \And mask = 0)$$
首先我们将当前的元素 $nums[i]$ 分解为质因子的掩码 $curr$，如果某个质因子出现两次，则表示 $nums[i]$ 无法加入到任何子集中，假设当前的子集中已经包含的质因子为 $mask$，此时 $curr$ 与 $mask$ 不能有交集，否则一定会出现某个质因子的次数出现了大于 $1$ 次。因此我们将 $mask$ 尝试与所有可能的子集合并，如果不存在重复的质因子，则可以将 $nums[i]$ 加入到该子集中。
复杂度分析：

时间复杂度：$O(n \times 2^{\alpha (U)})$，其中 $n$ 为数组的长度, $U$ 表示数组中的最大元素。
空间复杂度：$O(2^{\alpha (U)})$。

代码

动态规划

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

输入：lcp = [[4,0,2,0],[0,3,0,1],[2,0,2,0],[0,1,0,1]]
输出："abab"
解释：lcp 对应由两个交替字母组成的任意 4 字母字符串，字典序最小的是 "abab" 。

示例 2：

输入：lcp = [[4,3,2,1],[3,3,2,1],[2,2,2,1],[1,1,1,1]]
输出："aaaa"
解释：lcp 对应只有一个不同字母的任意 4 字母字符串，字典序最小的是 "aaaa" 。

示例 3：

输入：lcp = [[4,3,2,1],[3,3,2,1],[2,2,2,1],[1,1,1,3]]
输出：""
解释：lcp[3][3] 无法等于 3 ，因为 word[3,...,3] 仅由单个字母组成；因此，不存在答案。

提示：

1 <= n == ``lcp.length == ``lcp[i].length <= 1000
0 <= 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]$；

我们根据以上五个合法性质去检测当前的矩阵是否满足上述要求，如果不满足上述要求，则直接返回空字符串；
2. 构造合法的字符串：由于题目要求构造字典序最小的字符串，此时我们从最小的 $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)$。

代码

class Solution {
public:
    string findTheString(vector<vector<int>>& lcp) {
        int n = lcp.size();
        for (int i = 0; i < n; i++) {
            if (lcp[i][i] != n - i) {
                return "";
            }
            for (int j = i + 1; j < n; j++) {
                if (lcp[i][j] > n - j || lcp[i][j] != lcp[j][i]) {
                    return "";
                }
                if (lcp[i][j] > 0 && (i + 1 < n && j + 1 < n && lcp[i][j] != lcp[i + 1][j + 1] + 1)) {
                    return "";
                } 
            }
        }
        string s(n, ' ');
        char c = 'a';
        for (int i = 0; i < n; i++) {
            if (s[i] == ' ') {
                if (c > 'z') {
                    return "";
                }
                s[i] = c;
                for (int j = i + 1; j < n; j++) {
                    if (lcp[i][j] > 0) {
                        s[j] = s[i];
                    }
                }
                c++;
            }
        }
        return s;
    }
};

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

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

Tags: 力扣周赛题解

← leetcode biweekly contest 98 leetcode weekly contest 334 →

扫描二维码，分享此文章