leetcode contest 317

leetcode contest 317

周赛题目不错，大都有一些难度的题目，还算不错的周赛题目。

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

题目

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

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

示例 1：

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

示例 2：

输入：nums = [1,2,4,7,10]
输出：0
解释：不存在满足题目要求的整数，所以返回 0 。

提示：

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

地址

https://leetcode.cn/problems/average-value-of-even-numbers-that-are-divisible-by-three/

题意

直接模拟

思路

1. 直接遍历数组中的元素即可，找到所有能被 $6$ 整除的元素之和即可。
2. 复杂度分析：

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

  代码

  class Solution {
  public:
      int averageValue(vector<int>& nums) {
          int tot = 0, cnt = 0;
          for (auto v : nums) {
              if (v % 6 == 0) {
                  tot += v;
                  cnt++;
              }
          }
          return cnt == 0 ? 0 : tot / cnt;
      }
  };

2456. 最流行的视频创作者

题目

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

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

如果存在多个创作者流行度都最高，则需要找出所有符合条件的创作者。
如果某个创作者存在多个播放量最高的视频，则只需要找出字典序最小的 id 。
返回一个二维字符串数组 answer ，其中 answer[i] = [creatori, idi] 表示 creatori 的流行度 最高 且其最流行的视频 id是 idi ，可以按任何顺序返回该结果。

示例 1：

输入：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" 。

示例 2：

输入：creators = ["alice","alice","alice"], ids = ["a","b","c"], views = [1,2,2]
输出：[["alice","b"]]
解释：
id 为 "b" 和 "c" 的视频都满足播放量最高的条件。
由于 "b" 的字典序比 "c" 更小，所以结果中返回的 id 是 "b" 。

提示：

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

地址

https://leetcode.cn/problems/most-popular-video-creator/

题意

遍历

思路

1. 这个题目也就是遍历即可了，当我们直接统计每个创造者的视频总数，并记录每个创作者观看量最高的视频，最终找到观看量最多的创作者，并返回其观看量最多的视频。
2. 复杂度分析：

• 时间复杂度：时间复杂度为 $O(n)$。
• 空间复杂度：空间复杂度为 $O(n)$。

  代码

  class Solution {
  public:
      vector<vector<string>> mostPopularCreator(vector<string>& creators, vector<string>& ids, vector<int>& views) {
          unordered_map<string, long long> sum;
          unordered_map<string, pair<int, string>> cnt;
          int n = creators.size();
          vector<vector<string>> ans;
          for (int i = 0; i < n; i++) {
              sum[creators[i]] += views[i];
              if (!cnt.count(creators[i]) || 
                   views[i] > cnt[creators[i]].first || 
                   (views[i] == cnt[creators[i]].first && ids[i] < cnt[creators[i]].second)) {
                  cnt[creators[i]] = make_pair(views[i], ids[i]);
              }
          }
          long long maxCnt = 0;
          for (auto [_, x] : sum) {
              maxCnt = max(maxCnt, x);
          }
          for (auto [s, x] : sum) {
              if (x == maxCnt) {
                  ans.push_back({s, cnt[s].second});
              }
          }
          return ans;
      }
  };

2457. 美丽整数的最小增量

题目

给你两个正整数 n 和 target 。

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

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

示例 1：

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

示例 2：

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

示例 3：

输入：n = 1, target = 1
输出：0
解释：最初，n 是 1 ，且其每一位数字的和是 1 ，已经小于等于 target 。

提示：

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

地址

https://leetcode.cn/problems/minimum-addition-to-make-integer-beautiful/

题意

数学问题

思路

1. 简单的数学问题，我们观察一下规律，我们每次尝试将第 $i$ 位上的数字加 $1$，此时我们可以观察到整数的数位之和会减少，如果整数的最高位变为 $1$ 其余的位均为 $0$，则可以将整个数的数字之和最小减少为 $0$。
2. 根据以上尝试我们依次尝试将从右向左将每位上的数字加 $1$，然后计算加 $1$ 后的数字之和为 $tot$，如果满足 $tot < target$，则我们认为达到符合条件的最小值。
3. 复杂度分析

• 时间复杂度：时间复杂度为 $O(\log n)$，$n$ 为给定的数字。
• 空间复杂度：空间复杂度为 $O(\log n)$。

  代码

  class Solution {
  public:
      long long makeIntegerBeautiful(long long n, int target) {
          long long x = n;
          int tot = 0;
          while (x != 0) {
              tot += (x % 10);
              x /= 10;
          }
          if (tot <= target) {
              return 0;
          }
          string s = to_string(n);
          s = "0" + s;
          reverse(s.begin(), s.end());
          for (int i = 1; i < s.size(); i++) {
              string t = s;
              int curr = 0;
              for (int j = 0; j < i; j++) {
                  t[j] = '0';
              }
              int carry = (t[i] - '0' + 1) / 10;
              t[i] = (t[i] - '0' + 1) % 10 + '0';
              curr += t[i] - '0';
              for (int j = i + 1; j < s.size(); j++) {
                  int next = (t[j] - '0' + carry) / 10;
                  t[j] = (t[j] - '0' + carry) % 10 + '0';
                  carry = next;
                  curr += t[j] - '0';
              }
              if (curr <= target) {
                  reverse(t.begin(), t.end());
                  return stol(t) - n;
              }
          }
          return 0;        
      }
  };

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

题目

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

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

从树中 移除 以 queries[i] 的值作为根节点的子树。题目所用测试用例保证 queries[i] 不 等于根节点的值。
返回一个长度为 m 的数组 answer ，其中 answer[i] 是执行第 i 个查询后树的高度。

注意：

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

示例 1：

输入：root = [1,3,4,2,null,6,5,null,null,null,null,null,7], queries = [4]
输出：[2]
解释：上图展示了从树中移除以 4 为根节点的子树。
树的高度是 2（路径为 1 -> 3 -> 2）。

示例 2：

输入：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）。

提示：

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

地址

https://leetcode.cn/problems/height-of-binary-tree-after-subtree-removal-queries/

题意

深度优先搜索

思路

1. 确实是个不错的题目，也是个非常有意思的题目，每次记录遍历当前节点 $node$ 子树以外得到的节点所能遍历得到的高度 $h$，此时删除节点 $node$ 后的高度即为 $h$，我们可以分别采用先左遍历后右遍历和先右遍历后左遍历的方法来得到所有的可能：

• 假设当前节点 $node$ 为其父节点的左节点，且 $node$ 节点为根节点的左子树，则可以知道我们可以采用先遍历右节点，再遍历左节点的方法即可得到 $node$ 子树以外的节点构成的最大高度；
• 假设当前节点 $node$ 为其父节点的右节点，且 $node$ 节点为根节点的左子树，$node$ 子树以外的节点构成的最大高度：
  • 要么我们先右后左，可以得到一个高度 $h1$，此时 $node$ 的左兄弟的最大高度没有计算出来；
  • 要么我们先左后后，可以得到一个高度 $h2$，此时我们可以计算出 $node$ 的左兄弟的最大高度；
  • 当前去除 $node$ 后的节点子树的高度一定包含在 $\max(h1,h2)$ 中；
• 假设当前节点 $node$ 为其父节点的左节点，且 $node$ 节点为根节点的右子树，$node$ 子树以外的节点构成的最大高度；
  • 要么我们先左后有，可以得到一个高度 $h1$，此时我们可以计算出 $node$ 的右兄弟的高度没有计算出来；
  • 要么我们先右后左，可以得到一个高度 $h2$，此时可以计算出 $node$ 的右兄弟的高度；
  • 当前去除 $node$ 后的节点子树的高度一定包含在 $\max(h1,h2)$ 中；
• 假设当前节点 $node$ 为其父节点的右节点，且 $node$ 节点为根节点的右子树，则可以知道我们可以采用先遍历左节点，再遍历右节点的方法即可得到 $node$ 子树以外的节点构成的最大高度；

1. 复杂度分析：

• 时间复杂度：$O(n)$，其中 $n$ 表示给定的节点的数目。
• 空间复杂度：$O(n)$，其中 $n$ 表示给定的节点的数目。

代码

class Solution {
public:
    void dfs1(TreeNode* root, vector<int> &depth1, int &maxHeight, int height) {
        if (!root) {
            return;
        }
        depth1[root->val] = maxHeight;
        maxHeight = max(maxHeight, height);
        dfs1(root->left,  depth1, maxHeight, height + 1);
        dfs1(root->right, depth1, maxHeight, height + 1);
    }

    void dfs2(TreeNode* root, vector<int> &depth2, int &maxHeight, int height) {
        if (!root) {
            return;
        }
        depth2[root->val] = maxHeight;
        maxHeight = max(maxHeight, height);
        dfs2(root->right,  depth2, maxHeight, height + 1);
        dfs2(root->left, depth2, maxHeight, height + 1);
    }

    vector<int> treeQueries(TreeNode* root, vector<int>& queries) {
        int n = 1e5 + 1;
        vector<int> depth1(n), depth2(n);
        int maxHeight = 0;
        dfs1(root, depth1, maxHeight, 0);
        maxHeight = 0;
        dfs2(root, depth2, maxHeight, 0);
        vector<int> res;
        for (auto &v : queries) {
            res.emplace_back(max(depth1[v], depth2[v]));
        }
        return res;
    }
};

#

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

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