第 317 场周赛

比赛链接

Date: 2022-10-30

A 可被三整除的偶数的平均值

遍历即可，注意 0 的特殊处理

C++Python

class Solution {
public:
    int averageValue(vector<int>& nums) {
        int sum = 0, cnt = 0;
        for (auto &x : nums) {
            if (x % 3 == 0 && x % 2 == 0) {
                sum += x;
                cnt++;
            }
        }
        if (cnt == 0) return 0;
        return sum / cnt;
    }
};

class Solution:
    def averageValue(self, nums: List[int]) -> int:
        s = c = 0
        for x in nums:
            if x % 2 == 0 and x % 3 == 0:
                s += x
                c += 1
        return s // c if c != 0 else 0

复杂度分析

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

B 最流行的视频创作者

这个题略微有些麻烦，首先统计每个创作者的和，然后遍历得到最大值。对于和等于最大值的创作者，对他的作品集进行排序，按照流行度从大到小排序，如果流行度一样，就按照 id 的字典序从小到大排序。

C++

class Solution {
public:
    using ll = long long;
    vector<vector<string>> mostPopularCreator(vector<string>& creators, vector<string>& ids, vector<int>& views) {
        unordered_map<string, vector<pair<int, string>>> mp;
        unordered_map<string, ll> sum;
        for (int i = 0; i < creators.size(); i++) {
            auto name = creators[i];
            mp[name].push_back({views[i], ids[i]});
            sum[name] += views[i];
        }

        ll mx = 0;
        for (auto &[k, v] : sum) {
            mx = max(mx, v);
        }
        vector<vector<string>> res;
        for (auto &[k, v] : sum) {
            if (v != mx) continue;
            sort(mp[k].begin(), mp[k].end(), [](const pair<int, string> &lth, const pair<int, string> &rth) {
                if (lth.first != rth.first) return lth.first > rth.first;
                return lth.second < rth.second;
            });
            res.push_back({k, mp[k].front().second});
        }
        return res;
    }
};

复杂度分析

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

另外一种代码方式是直接用一个哈希表记录：

• 每个人的流行度总和
• 最大流行度
• 最大流行度的作品ID

然后遍历哈希表即可得到答案。

C++Python

class Solution {
public:
    using ll = long long;
    vector<vector<string>> mostPopularCreator(vector<string>& creators, vector<string>& ids, vector<int>& views) {
        unordered_map<string, tuple<ll, int, string>> mp;
        ll maxsum = 0;
        for (int i = 0; i < creators.size(); i++) {
            string name = creators[i], id = ids[i];
            int view = views[i];
            if (mp.count(name)) {
                auto [x, y, z] = mp[name];
                x += view;
                if (view > y || (view == y && id < z)) {
                    y = view;
                    z = id;
                }
                mp[name] = make_tuple(x, y, z);
            } else {
                mp[name] = make_tuple(view, view, id);
            }
            maxsum = max(maxsum, get<0>(mp[name]));
        }
        vector<vector<string>> res;
        for (auto &[k, v] : mp) {
            auto [x, y, z] = v;
            if (x == maxsum) {
                res.push_back({k, z});
            }   
        }
        return res;
    }
};

class Solution:
    def mostPopularCreator(self, creators: List[str], ids: List[str], views: List[int]) -> List[List[str]]:
        maxsum = 0
        mp = {}
        for x, y, z in zip(creators, ids, views):
            if x in mp:
                mp[x][0] += z
                if z > mp[x][1] or (z == mp[x][1] and y < mp[x][2]):
                    mp[x][1] = z
                    mp[x][2] = y
            else:
                mp[x] = [z, z, y]
            maxsum = max(maxsum, mp[x][0])
        return [[k, v[2]] for k, v in mp.items() if v[0] == maxsum]

复杂度分析

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

C 美丽整数的最小增量

每次 +1，产生进位后，才会使得总和变小。例如 \(467\)，进到十位是 \(470\)，进到百位是 \(500\)，进到千位是 \(1000\)。

C++Python

class Solution {
public:
    using ll = long long;
    long long makeIntegerBeautiful(long long n, int target) {
        ll mask = 1;
        while (true) {
            // 注意取出末尾元素可以用 n % mask，但是由于末尾可能都是 0，所以 mask 减去之后还需要取模
            ll buf = (mask - (n % mask)) % mask; 
            ll m = n + buf;
            int cnt = 0;
            while (m) {
                cnt += m % 10;
                m /= 10;
            }
            if (cnt <= target) return buf;
            mask *= 10;
        }
        return -1;
    }
};

class Solution:
    def makeIntegerBeautiful(self, n: int, target: int) -> int:
        mask = 1
        while True:
            buf = (mask - n % mask) % mask
            m = n + buf
            cnt = 0
            while m > 0:
                cnt += m % 10
                m /= 10
            if cnt <= target:
                return buf
            mask *= 10
        return -1

复杂度分析

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

D 移除子树后的二叉树高度

方法一 DFS 序

DFS 后，可以将树转换为一个序列即 DFS 序，记 \(x\) 为子树根的编号，那么 \(in[x]\sim out[x]\) 标记序列中以 \(x\) 为根的子树区间。

我们求出每个点距离 root 的深度，如果删除 \(x\)，那么不会影响除去 \(x\) 的子树之外其他点到 root 的距离。

所以，对应到 DFS 中删除一个子树相当于去除了一个区间。因此，提前预处理这个 DFS 序列每个点的深度，构成一个新序列，求出它的前缀和后缀即可 \(O(1)\) 回答每个询问。

C++

class Solution {
public:
    void getCnt(TreeNode* root, int &n) {
        if (root == nullptr) {
            return;
        }
        n++;
        getCnt(root->left, n);
        getCnt(root->right, n);
    }
    vector<int> treeQueries(TreeNode* root, vector<int>& queries) {
        int n = 0;
        getCnt(root, n);
        vector<int> dep(n + 1), pre(n + 1), suf(n + 2), in(n + 1), out(n + 1);
        int cnt = 0;
        function<void(TreeNode*, int)> dfs = [&](TreeNode* root, int d) {
            if (root == nullptr) return;
            in[root->val] = ++cnt;
            dep[cnt] = d;
            dfs(root->left, d + 1);
            dfs(root->right, d + 1);
            out[root->val] = cnt;
        };
        dfs(root, 0);
        for (int i = 1; i <= n; i++) pre[i] = max(pre[i - 1], dep[i]);
        for (int i = n; i >= 1; i--) suf[i] = max(suf[i + 1], dep[i]);
        vector<int> res;
        for (auto q : queries) {
            res.push_back(max(pre[in[q] - 1], suf[out[q] + 1]));
        }
        return res;
    }
};

复杂度分析

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

方法二 DP

假设提前处理出每个子树被删除之后的答案，即可 \(O(1)\) 回答每个询问。

假设已经求出去除 \(x\) 后的最大深度 \(cur\)，并且已知 \(up\) 是 \(x\) 到根的边数，那么：

1. 去掉 \(x\) 的 \(left\) 的最大深度是：\(max(cur, up + dep[right])\)
2. 去掉 \(x\) 的 \(right\) 的最大深度是：\(max(cur, up + dep[left])\)

C++

class Solution {
public:
    vector<int> treeQueries(TreeNode* root, vector<int>& queries) {
        unordered_map<int, int> dep, ret;
        function<int(TreeNode*)> dfs = [&](TreeNode* rt) {
            if (rt == nullptr) return 0;
            dep[rt->val] = max(dfs(rt->left), dfs(rt->right)) + 1;
            return dep[rt->val];
        };
        dfs(root);
        function<void(TreeNode*, int, int)> get = [&](TreeNode* rt, int up, int cur) {
            if (rt == nullptr) return;
            ret[rt->val] = cur;
            int rdep = rt->right ? dep[rt->right->val] : 0;
            int ldep = rt->left ? dep[rt->left->val] : 0;
            get(rt->left, up + 1, max(cur, up + rdep));
            get(rt->right, up + 1, max(cur, up + ldep));
        };
        get(root, 0, 0);
        vector<int> res;
        for (auto q : queries) {
            res.push_back(ret[q]);
        }
        return res;
    }
};

本文访问 次