leetcode 第 317 场算法比赛

零、背景

这次比赛最后两题有意思。

倒数第三题需要一番逻辑推导，可以发现扫描一遍就可以求出答案。
倒数第四题树的询问问题，可以转化为区间询问问题。

一、可被三整除的偶数的平均值

题意：问可以被 3 整除的偶数的数字的平均值。

思路：被 3 整除的偶数就是被 6 整除，求和与计数相除即可。

二、最流行的视频创作者

题意：给三个数组，分别是创作者名字，创作者上传的视频ID，以及该视频的播放量。
求创作者所有视频播放量最大的那个创作者，以及创作者对应的播放量最大的视频ID。
视频ID有多个时，输出字典序最小的那个。

思路：

-）扫描累计计算每个创作者的总播放量，顺便记录视频播放量最大的视频ID。
-）扫描得到最大的创作者总播放量。
-）扫描得到所有满足最大总播放量的创作者以及答案要求的数据。

三、美丽整数的最小增量

题意：给一个正整数 n 个和目标值 target。
求最小的 x ，使得 n+x 十进制所有位数字之和不大于 target。

思路：

可以证明，肯定存在答案，因为可以转化为最高位为 1 后面都为 0 的数字，此时各位数字之和为 1。

但是题目不是求最小的十进制和，只需要满足不大于 target 即可。

这道题的关键突破口是枚举有变化的最高位数。

假设前面的高位不存在变化，然后第 i 位才开始变化。
则分两种情况。
第一种是加上小于第 i 位的数字，第 i 位进一位。
第二种是加上一个 i 位数字。

显然可以证明，如果存在答案，第一种情况显然更优。

那怎样才能让第 i 位进一位了？
例如数字 123，最高位进一位后是 200，显然需要加上 77。
故需要加的最小值是 10^i - n % (10^i)。

由此，通过枚举变化的最高位，取最优值即可。

当然，进一步分析，可以发现，如果在更低位存在答案，最高位的答案显然不会更优。
所以直接从最低位到最高位枚举计算，找到答案结束即可。

四、移除子树后的二叉树高度

题意：给一个值互不相同的二叉树，有 k 个询问，问删除一个子树后，二叉树的高度是多少。

思路：

如果每次删除都暴力计算，计算一次的复杂度就是 O(n)，询问 k 次复杂度就是 O(kn)。

观察二叉树删除后的特征，可以发现，删除一个子树，其他节点的树高是不变的。
所以只需要求出剩余节点的最大树高即可。

如果将树转化为值为树高的序列，删除一个子树就是删除一个连续区间。
问题就转化为了求前缀和后缀的最大值。

具体实现：树按先序序列记录每个节点的树高，并记录每个子树根在序列里的左右区间。
然后预处理序列，计算出每个位置前缀和后缀的最大值。
删除一个子树时，先得到子树在序列里对应的左右区间边界，然后前缀和后缀的最大值取最大值即可。

递归直接计算答案思路：

删除一个子树，假设这个子树是父节点的某个儿子。
则最高的树高节点可能是父节点的另外一个儿子，或者是父节点外的最大树高。
递归的时候，维护父节点之外的最大高度，即可计算出删除当前节点时，剩余树的高度。

五、最后

这次比赛题目有点意思。
尤其是第三题思考一下还是可以想出来。
第四题则可以直接递归算，也可以转化为区间来做。

加油，算法人。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code