LeetCode 317 周赛

纪念本狗的第二次AK！

2455. 可被三整除的偶数的平均值

给你一个由正整数组成的整数数组 nums ，返回其中可被 3 整除的所有偶数的平均值。

注意：n 个元素的平均值等于 n 个元素 求和 再除以 n ，结果 向下取整 到最接近的整数。

提示：

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 1000

示例

输入：nums = [1,3,6,10,12,15]
输出：9
解释：6 和 12 是可以被 3 整除的偶数。(6 + 12) / 2 = 9 。
1
2
3

思路

模拟，可被3整除，又是偶数，那么等价于能被6整除

// C++
class Solution {
public:
    int averageValue(vector<int>& nums) {
        int sum = 0, n = 0;
        for (auto& i : nums) {
            if (i % 6 == 0) {
                sum += i;
                n++;
            }
        }
        if (n) return sum / n;
        return 0;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2456. 最流行的视频创作者

给你两个字符串数组 creators 和 ids ，和一个整数数组 views ，所有数组的长度都是 n 。平台上第 i 个视频者是 creator[i] ，视频分配的 id 是 ids[i] ，且播放量为 views[i] 。

视频创作者的 流行度 是该创作者的 所有 视频的播放量的 总和 。请找出流行度 最高 创作者以及该创作者播放量 最大 的视频的 id 。

• 如果存在多个创作者流行度都最高，则需要找出所有符合条件的创作者。
• 如果某个创作者存在多个播放量最高的视频，则只需要找出字典序最小的 id 。

返回一个二维字符串数组 answer ，其中 answer[i] = [creatori, idi] 表示 creatori 的流行度 最高 且其最流行的视频 id 是 idi ，可以按任何顺序返回该结果*。*

提示：

• n == creators.length == ids.length == views.length
• 1 <= n <= 10^5
• 1 <= creators[i].length, ids[i].length <= 5
• creators[i] 和 ids[i] 仅由小写英文字母组成
• 0 <= views[i] <= 10^5

示例

输入：creators = ["alice","bob","alice","chris"], ids = ["one","two","three","four"], views = [5,10,5,4]
输出：[["alice","one"],["bob","two"]]
解释：
alice 的流行度是 5 + 5 = 10 。
bob 的流行度是 10 。
chris 的流行度是 4 。
alice 和 bob 是流行度最高的创作者。
bob 播放量最高的视频 id 为 "two" 。
alice 播放量最高的视频 id 是 "one" 和 "three" 。由于 "one" 的字典序比 "three" 更小，所以结果中返回的 id 是 "one" 。
1
2
3
4
5
6
7
8
9

思路

注意仔细审题，使用哈希表进行分组统计即可。

// C++
typedef pair<long long, string> PIS;
typedef long long LL;
class Solution {
public:
    vector<vector<string>> mostPopularCreator(vector<string>& c, vector<string>& ids, vector<int>& v) {
        unordered_map<string, LL> total; // 创作者和流行度
        unordered_map<string, vector<PIS>> vs; // 存储创作者和对应的作品
        int n = ids.size();
        
        vector<string> ans_c;
        LL max_view = 0;
        
        for (int i = 0; i < n; i++) {
            total[c[i]] += v[i];
            max_view = max(max_view, total[c[i]]);
            vs[c[i]].push_back({v[i], ids[i]});
        }
        
        // 取出流行度最大的创作者
        for (auto& [k, v] : total) {
            if (v == max_view) ans_c.push_back(k);
        }
        
        vector<vector<string>> ans;
        
        for (auto& s : ans_c) {
            vector<PIS> t = vs[s];
            max_view = t[0].first;
            string id = t[0].second;
            for (int j = 1; j < t.size(); j++) {
                PIS i = t[j];
                if (i.first > max_view) {
                    max_view = i.first;
                    id = i.second;
                } else if (i.first == max_view && i.second <= id) {
                    // 播放量相同的, 取id字典序更小的
                    id = i.second;
                }
            }
            vector<string> item;
            item.push_back(s);
            item.push_back(id);
            ans.push_back(item);
        }
        return ans;
    }
};
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
48

2457. 美丽整数的最小增量

给你两个正整数 n 和 target 。

如果某个整数每一位上的数字相加小于或等于 target ，则认为这个整数是一个 美丽整数 。

找出并返回满足 n + x 是 美丽整数 的最小非负整数 x 。生成的输入保证总可以使 n 变成一个美丽整数。

提示：

• 1 <= n <= 10^12
• 1 <= target <= 150
• 生成的输入保证总可以使 n 变成一个美丽整数。

示例

输入：n = 16, target = 6
输出：4
解释：最初，n 是 16 ，且其每一位数字的和是 1 + 6 = 7 。在加 4 之后，n 变为 20 且每一位数字的和变成 2 + 0 = 2 。可以证明无法加上一个小于 4 的非负整数使 n 变成一个美丽整数。
1
2
3

思路

当加上一些数，造成进位时，每一位上的数字之和就有可能变小。进位只会让某一位上的数字增加1，而会使其他位置的数字减少等于或超过1。

比如19，我们只要加上一个1，就能使个位数字减小9，而十位数字只增加1。

并且，对于任意数字，我们总是能通过加上一个数，将其每一位的数字之和变为1，只要让其最高位再向前进位即可。要想使得加上的数尽可能小，而满足条件，很明显，我们应该先考虑让低位的数字变为0。那么，我们可以先将原数字每一位上的数取出来，从最高位开始进行累加，假如累加到某一个位置i时，和恰好大于target，说明对于位置i以及更靠右的位置，都应该变为0；而到第i个位置时才恰好大于target，说明累加到i - 1位置时，和是小于target的，那么小于target，至少就比target小1，而将i及以后的位置全部变为0，会造成进位，恰好使得i - 1位置多1，结果最多也就等于target。

所以，我们的策略就是，从最高位开始，对每一位数字进行累加，找到第一次大于target时的位置i时，停止，将i及以后的位置，全部变为0即可。

注意，有一些特殊情况需要考虑的，比如累加到第i个位置，和恰好等于target了。

比如n = 111001，target = 3，累加到第三个位置时，恰好等于3。此时需要记录一下第一次出现等于target时的位置，并继续累加后面的位，如果后面的位全为0，那么我们不需要加任何数，我们的答案是0；如果后面的某一位不为0，那么加到那一位时，一定会有和大于target，此时我们应当把第一次出现和等于target的位置，以及该位置之后的数，全都变为0。

注：下次求某个数的每一位时，可以将其转化为string。

// C++
typedef long long LL;
class Solution {
public:
    LL makeIntegerBeautiful(LL n, int target) {
        // string s = to_string(n);
        vector<LL> bits; // 存储数字n的每一位, 小端序, 第0个位置存储的是最低位
        LL t = n;
        while (t) {
            bits.push_back(t % 10);
            t /= 10;
        }
        // 找到停止的位置
        int end = -1, sum = 0;
        bool equal = false; // 是否遇到和等于target的情况
        int equal_start = -1;
        // 从最高位开始
        for (int i = bits.size() - 1; i >= 0; i--) {
            sum += bits[i];
            if (sum < target) continue;
            if (sum > target) {
                end = i;
                break;
            } else {
                // sum == target
                if (!equal) equal_start = i; // 第一次遇到相等, 记录下起始位置
                equal = true;
            }
        }
        
        if (end == -1) return 0; // 一直 < target 或者一直 = target
        // 遇到了 > target
        if (equal) end = equal_start; // 若中间有遇到 = target, 则位置应该从第一次遇见 = target 时开始
        LL ans = 0;
        // 从end位置开始计算, 需要补足的数字
        for (int i = end; i >= 0; i--) {
            ans *= 10;
            if (i) ans += 9 - bits[i]; // 其余位相加等于9即可
            else ans += 10 - bits[i]; // 最后一位要保证相加等于10, 产生进位
        }
        return ans;
    }
};
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

此题由于最多只有12位，可以用暴力法来做，先求得所有位的数字和，然后从个位开始，将每一位加为0，然后重新重新计算数字和，直到和小于等于target

// C++
typedef long long LL;
class Solution {
public:
    long long makeIntegerBeautiful(long long n, int target) {
        vector<LL> bits;
        LL t = n;
        int sum = 0;
        while (t) {
            bits.push_back(t % 10);
            sum += t % 10;
            t /= 10;
        }
        if (sum <= target) return 0;

        bits.push_back(0); // 在最高位之后再加个0, 方便处理最高位的进位
        for (int i = 0; i < bits.size() - 1; i++) {
            if (bits[i] == 0) continue; // 该位为0, 不需要加
            // 将该位变成0
            sum = sum - bits[i] + 1; // 会进位, 若该位已经被上一位进位变成了10, 则该位就是变小了9, 没毛病
            bits[i + 1]++;
            bits[i] = 0;
            if (bits[i + 1] == 10) continue; // 下一位也进位了, 则要计算, 不能提前退出
            if (sum <= target) break;
        }
        // 将新得到的bits对应的整数算出来, 再减去n
        LL ans = 0;
        for (int i = bits.size() - 1; i >= 0; i--) ans = ans * 10 + bits[i];
        return ans - n;
    }
};
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

2458. 移除子树后的二叉树高度

给你一棵 二叉树 的根节点 root ，树中有 n 个节点。每个节点都可以被分配一个从 1 到 n 且互不相同的值。另给你一个长度为 m 的数组 queries 。

你必须在树上执行 m 个 独立 的查询，其中第 i 个查询你需要执行以下操作：

• 从树中 移除 以 queries[i] 的值作为根节点的子树。题目所用测试用例保证 queries[i] 不 等于根节点的值。

返回一个长度为 m 的数组 answer ，其中 answer[i] 是执行第 i 个查询后树的高度。

注意：

• 查询之间是独立的，所以在每个查询执行后，树会回到其 初始 状态。
• 树的高度是从根到树中某个节点的 最长简单路径中的边数 。

提示：

• 树中节点的数目是 n
• 2 <= n <= 10^5
• 1 <= Node.val <= n
• 树中的所有值 互不相同
• m == queries.length
• 1 <= m <= min(n, 10^4)
• 1 <= queries[i] <= n
• queries[i] != root.val

示例

输入：root = [5,8,9,2,1,3,7,4,6], queries = [3,2,4,8]
输出：[3,2,3,2]
解释：执行下述查询：
- 移除以 3 为根节点的子树。树的高度变为 3（路径为 5 -> 8 -> 2 -> 4）。
- 移除以 2 为根节点的子树。树的高度变为 2（路径为 5 -> 8 -> 1）。
- 移除以 4 为根节点的子树。树的高度变为 3（路径为 5 -> 8 -> 2 -> 6）。
- 移除以 8 为根节点的子树。树的高度变为 2（路径为 5 -> 9 -> 3）。
1
2
3
4
5
6
7

思路

对于某一颗子树，其根节点为root，左子树为L，右子树为R，删除左子树后剩余部分的高度，要么是右子树R的高度加上根节点所在的层次，要么是根节点root的父节点所在的树的最大高度。

以上图为例，删除节点3，剩余部分的高度，要么等于其兄弟节点7的高度+父节点9所在的层次，要么等于节点9的父节点那一侧的最大高度。

于是我们可以对树进行2次DFS遍历，一次求出以每个节点作为根节点的子树的高度，一次求出删除某个节点剩余部分的高度。经过两次预处理后，后续的每次queries查询，可以在 $O(1)$ 的时间复杂度内求解。

// C++
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    // 以每个节点作为根节点的子树的高度
    unordered_map<int, int> h;
    
    // 删除某个节点, 剩余部分的最大高度
    unordered_map<int, int> ans;
    
    // 返回这棵树的高度
    int dfs(TreeNode* x) {
        if (x == nullptr) return 0;
        int left = dfs(x->left);
        int right = dfs(x->right);
        return h[x->val] = max(left, right) + 1;
    }
    
    // depth 是x所在的层次, other是从x父节点那边传过来的最大高度
    void dfs2(TreeNode* x, int depth, int other) {
        if (x == nullptr) return ;
        ans[x->val] = other; // 删除x节点, 那么得到剩余部分的最大高度就是other
        int h_r = 0, h_l = 0; // 左子树和右子树的高度
        if (x->right != nullptr) h_r = h[x->right->val];
        if (x->left != nullptr) h_l = h[x->left->val];
        // 删除左子树, 剩余部分的高度是other和depth + h_r 取一个max
        dfs2(x->left, depth + 1, max(depth + h_r, other));
        // 删除右子树同理
        dfs2(x->right, depth + 1, max(depth + h_l, other));
    }
    
    vector<int> treeQueries(TreeNode* root, vector<int>& queries) {
        
        // 一次dfs算出每个节点的高度
        dfs(root);
        // 一次dfs求出每个节点删除后剩余的高度
        dfs2(root, 1, 0);
        
        int m = queries.size();
        vector<int> ret(m);
        for (int i = 0; i < m; i++) {
            // 前面求解的高度, 实际是最长路径上的点的个数, 而题目定义的高度是边的个数, 所以要-1
            ret[i] = ans[queries[i]] - 1;
        }
        return ret;
    }
};
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
48
49
50
51
52
53
54
55
56
57

总结

这场比赛一雪昨晚只做出2题的耻辱！但这场比赛总的来说难度感觉不是很大。

T1是模拟；

T2是模拟+哈希表；

T3是贪心；

T4是图论DFS，树的遍历；