Skip to content

第 333 场周赛

比赛链接

Date: 2023-02-19

A 合并两个二维数组 - 求和法

用一个 map 去记录每一个 kv 对即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<vector<int>> mergeArrays(vector<vector<int>>& nums1, vector<vector<int>>& nums2) {
        map<int, int> mp;
        for (auto &v : nums1) {
            mp[v[0]] += v[1];
        }
        for (auto &v : nums2) {
            mp[v[0]] += v[1];
        }
        vector<vector<int>> res;
        for (auto &[k, v] : mp) {
            res.push_back({k, v});
        }
        return res;
    }
};

1
2
3
4
5
6
class Solution:
    def mergeArrays(self, nums1: List[List[int]], nums2: List[List[int]]) -> List[List[int]]:
        d = Counter()
        for x, y in nums1: d[x] += y
        for x, y in nums2: d[x] += y
        return list(sorted(d.items()))

复杂度分析

  • 时间复杂度：\(O(n\log n)\)
  • 空间复杂度：\(O(n)\)

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

首先容易想到的是将数字转换为二进制表示后，对于值为 \(1\) 的位置我们用一次减去。

但又会有一个反例：\(111\)，我们只需要 \(2\) 次操作即可把它变为 \(0\)。

那进一步的想法是记录连续 \(1\) 的个数，如果连续超过 \(2\) 个 \(1\)，那么我们可以用 \(2\) 操作即可把它变为 \(0\)。

但是又会有一个反例是 \(1110111\)，我们可以通过 \(+2\), \(+8\), \(-128\) 把它变为 \(0\)。

综上我们可以发现，后面的一段连续的 \(1\)，可能会把前面的一个 \(0\) 破除掉，因此我们应该尽量让连续的 \(1\) 通过加法进位。即便这一段连续的 \(1\) 只有两个。

进位后，可以发现没有两个连续的 \(1\) 存在，所以返回 \(1\) 的个数即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int minOperations(int n) {
        int res = 0;
        for (int i = 0; i <= 25; i++) {
            if ((n >> i & 1) && (n >> (i + 1) & 1)) {
                n += (1 << i);
                res++;
            }
        }
        for (int i = 0; i <= 25; i++) {
            if (n >> i & 1) {
                res++;
            }
        }
        return res;
    }
};

复杂度分析

  • 时间复杂度：\(O(\log n)\)
  • 空间复杂度：\(O(1)\)

C 无平方子集计数

首先有一个结论，无平方子集表示该子集内的所有数字的乘积不存在相同的质因子。因此，我们在选数字时，不能选择相同的质因子。

然后发现 \(\textit{nums}[i]\) 的范围只有 \(30\)，而 \(30\) 以内的质因子只有 \(10\) 个，因此我们最多只能选 \(10\) 个数字出来。

用二进制数字来表示集合是比较常规的做法，\(d[i][j]\) 表示从前 \(i\) 个数字里面选出集合 \(j\) 的方法数，其中 \(j\) 是 \(0 \sim 2^{10}\) 之间的数字。

 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
class Solution {
public:
    static constexpr int mod = (1e9 + 7);
    int primes[10] = {
        2, 3, 5, 7, 11, 13, 17, 19, 23, 29
    };
    int squareFreeSubsets(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> d(n, vector<int>(1 << 10, 0));
        for (int i = 0; i < n; i++) {
            if (i > 0) {
                d[i] = d[i - 1];
            }
            int x = nums[i], mask = 0, fg = 1;
            for (int j = 0; j < 10; j++) {
                int cnt = 0;
                while (x % primes[j] == 0) {
                    mask |= 1 << j;
                    cnt++;
                    x /= primes[j];
                }
                if (cnt > 1) {
                    fg = 0;
                    break;
                }
            }
            if (fg == 0) {
                continue;
            }
            if (i == 0) {
                d[i][mask] = 1;
                continue;
            }
            d[i][mask] = (d[i][mask] + 1) % mod;
            for (int j = 0; j < (1 << 10); j++) {
                if ((mask & j) == 0) {
                    d[i][mask | j] = (d[i][mask | j] + d[i - 1][j]) % mod;
                }
            }
        }
        int res = 0;
        for (int i = 0; i < (1 << 10); i++) {
            res = (d[n - 1][i] + res) % mod;
        }
        return res;
    }
};

复杂度分析

  • 时间复杂度：\(O(2^{10}n)\)。
  • 空间复杂度：\(O(2^{10}n)\)。

D 找出对应 LCP 矩阵的字符串

如果 \(lcp[i][j] != 0\)，则表示 \(i\) 和 \(j\) 的字符相同，我们依据这一条就可以构造出 \(s\)。

由于相同的性质是必须满足的，所以我们从前到后依次确定每个字符应该是谁。构造出来以后，进行判定：

  1. 如果 \(s[i] = s[j]\)，那么必须满足 \(lcp[i][j] = lcp[i + 1][j + 1] + 1\)，否则无解。
  2. 如果 \(s[i] != s[j]\)，那么必须满足 \(lcp[i][j] = 0\)，否则无解。
 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
class Solution {
public:
    string findTheString(vector<vector<int>>& lcp) {
        int n = lcp.size();
        string s = string(n, ' ');
        int ord = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] != ' ') {
                continue;
            }
            s[i] = char('a' + ord);
            for (int j = i + 1; j < n; j++) {
                if (lcp[i][j] != 0) {
                    s[j] = char('a' + ord);
                }
            }
            ord++;
        }
        if (ord > 26) {
            return "";
        }
        // 构造出 s，然后验证
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int right_down = i + 1 < n && j + 1 < n ? lcp[i + 1][j + 1] : 0;
                if (s[i] == s[j]) {
                    if (lcp[i][j] == right_down + 1) {
                        continue;
                    } else {
                        return "";
                    }
                } else if (lcp[i][j] != 0) {
                    return "";
                }
            }
        }
        return s;
    }
};

复杂度分析

  • 时间复杂度：\(O(n^2)\)
  • 空间复杂度：\(O(n^2)\)
本文访问 次