leetcode 第 344 场算法比赛

零、背景

这次比赛题目比较简单，拼手速的时候到了，我 29 分钟全部 1AC 做完，没进前百名。

一、找出不同元素数目差数组

题意：给一个数组，问每个位置前缀和后缀集合大小的差值。

思路：按照题意预处理出每个位置前缀和后缀的集合大小，之后求差值即可。

二、频率跟踪器

题意：交互式题，有三个操作。
1）添加一个元素
2）删除一个元素
3）问是否存在某个元素的出现次数为 freq

思路：维护元素的个数，以及各频率的个数即可。

元素个数：map<v, num>
频率个数: map<num, count>

增加一个元素，旧的频率个数减一，新的频率个数加1，元素个数加一。
删除一个元素，与增加一个元素相反。
询问：直接看频率个数是否大于零。

注意事项：删除元素时，元素不存在需特殊处理。

三、有相同颜色的相邻元素数目

题意：给一个原先没有颜色值的数组，现在不断地对数组进行染色。
问每次染色之后，整个数组中相邻元素颜色相等的数组。

思路：与上一题类似的统计题，统计当前的答案。

每次染色可以转化为取消染色与染色。

取消染色就是相邻元素颜色相同转化为不同，左右最多两个。
染色就是相邻元素颜色不同转化为相同，左右最多两个。

四、使二叉树所有路径值相等的最小代价

题意：给一个完全二叉树，怎么修改才能使得所有根到叶子的路径全部相等，求最小修改代价。
修改代价：一次可以选择一个节点值加一。

思路：可以推断出，答案最优时，根到叶子的路径和也是最小的。

起初我想的是二分路径和，结果发现可以直接计算出路径和。
即原始二叉树中的最大路径。

对于其他路径，把差值都加到叶子上，即可构造出一个答案，但是不是最优值。
分析不是最优值的原因，是因为有些相邻父节点的叶子都进行了修改。
如果把修改上移到父节点，则可以降低修改的次数。

所以可以从叶子节点向上倒推，合并两个儿子的公共修改次数。
这样就可以计算出最优答案了。

五、最后

这次比赛虽然简单，但是最后一题有点贪心的味道，想到就很简单，想不到就难了吧。

最后一题你是怎么做的呢？

《完》

-EOF-

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