第 335 场周赛

Date: 2023-03-05

A 递枕头

设置一个指针，指向当前拿枕头的人。再设置一个方向，表示当前是向左还是向右传递。

class Solution {
public:
    int passThePillow(int n, int time) {
        int cur = 1, dir = 1;
        for (int i = 0; i < time; i++) {
            if (cur == 1) {
                cur = 2;
                dir = 1;
            } else if (cur == n) {
                cur = n - 1;
                dir = -1;
            } else {
                cur = cur + dir;
            }
        }
        return cur;
    }
};

复杂度分析

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

B 二叉树中的第 K 大层和

递归时携带一个深度信息，然后用哈希表记录每一层的和。最后排序即可。

class Solution {
public:
    using ll = long long;
    long long kthLargestLevelSum(TreeNode* root, int k) {
        unordered_map<int, ll> mp;
        function<void(TreeNode*, int)> dfs = [&](TreeNode* rt, int dep) {
            if (rt == nullptr) return;
            mp[dep] += rt->val;
            dfs(rt->left, dep + 1);
            dfs(rt->right, dep + 1);
        };
        dfs(root, 0);
        vector<ll> res;
        for (auto &[k, v] : mp) res.push_back(v);
        sort(res.begin(), res.end(), greater<ll>());
        if (res.size() < k) return -1;
        return res[k - 1];
    }
};

复杂度分析

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

C 分割数组使乘积互质

本题应该是本次周赛中最难的一题（但也不会很难）。

首先两组数的乘积互质，等同于这两组数分别求出质因数集合后不存在交集。

所以，我们先求出整体的质因数集合，然后再从左向右扫描的过程中从中删除质因数。用一个变量 \(\textit{cnt}\) 来记录已删除过的质因数中，有多少还没有删除完（删除完的意思是说这类质因数在右边不再出现，即个数为 0）。

具体的，\(tot\) 表示质因数集合，\(cur\) 表示当前右部的质因数集合，如果要删除一个 \(x\)，发现 \(cur\) 中的 \(x\) 和 \(tot\) 中的 \(x\) 个数相同，则 \(cnt + 1\)，删除之后如果 \(cur\) 中的 \(x\) 个数为 \(0\)，表示删完了，\(cnt - 1\)。

当过程中出现 \(cnt = 0\) 的情况，则表示左部和右部的质因数集合之间不存在交集，也就符合了题意。

class Solution {
public:
    int findValidSplit(vector<int>& nums) {
        int n = nums.size(), cnt = 0;
        vector<vector<int>> fac(n);
        unordered_map<int, int> tot, cur;
        // 求解质因数
        auto getFac = [&](int x, vector<int>& fac) {
            for (int i = 2; i * i <= x; i++) {
                while (x % i == 0) {
                    fac.push_back(i);
                    x /= i;
                }
            }
            if (x > 1) {
                fac.push_back(x);
            }
        };

        auto des = [&](int x) {
            if (cur[x] == tot[x]) {
                cnt++;
            }
            cur[x]--;
            if (cur[x] == 0) {
                cnt--;
            }
        };

        for (int i = 0; i < n; i++) {
            getFac(nums[i], fac[i]);
            for (auto x : fac[i]) {
                tot[x]++;
                cur[x]++;
            }
        }

        for (int i = 0; i < n - 1; i++) {
            for (auto x : fac[i]) {
                des(x);
            }
            if (cnt == 0) {
                return i;
            }
        }
        return -1;
    }
};

复杂度分析

时间复杂度：\(O(n\sqrt C)\)，其中 \(n\) 是元素个数，\(C\) 是值域范围，本题中等于 \(10^6\)。
空间复杂度：\(O(n\log n)\)。每个数字的质因子个数是 \(log\) 级别的，我们为了节省多次求解质因数，选择了将质因数存储下来，因此会多一点空间占用。当然，如果前后两次都选择直接求解的话，空间复杂度将会降低至 \(O(n)\)。

D 获得分数的方法数

比较裸的动态规划题，类似 01 背包的思路。

\(d[i][j]\) 表示考虑了前 \(i\) 个物品后，组成 \(j\) 分的方法数。转移方程见代码。

C++

class Solution {
public:
    static constexpr int mod = 1e9 + 7;
    int waysToReachTarget(int target, vector<vector<int>>& types) {
        vector<vector<int>> d(2, vector<int>(target + 1));
        d[1][0] = 1;
        int n = types.size();
        for (int i = 0; i < n; i++) {
            int t = i & 1;
            fill(d[t].begin(), d[t].end(), 0);
            for (int k = 0; k <= target; k++) {
                for (int j = 0; j <= types[i][0] && j * types[i][1] <= k; j++) {
                    d[t][k] = (d[t][k] + d[t^1][k - j * types[i][1]]) % mod;
                }
            }
        }
        return d[(n - 1) & 1][target];
    }
};

复杂度分析

时间复杂度：\(O(nmk)\)，其中 \(n\) 是题目种类数，\(m\) 是 \(target\)，\(k\) 是每种题目的数量。
空间复杂度：\(O(m)\)。

本文访问次