leetcode 第 419 场算法比赛

零、背景

这次比赛本来计划参加的，但是由于有点事情，就没参与。
赛后做了下，发现最后一题有两种做法，一种是手动维护区间的合并，很复杂，一种是线段树解决，很简单。

A: 暴力计算。
B: DFS+最小堆。
C: 动态规划。
D: 滑动窗口+模拟 或者 滑动窗口+离散化+二分+线段树。

排名：无
代码地址： https://github.com/tiankonguse/leetcode-solutions/tree/master/contest/4/419

一、计算子数组的 x-sum I

题意：给你一个数组，求子数组sum[i,i+k-1]的 x-sum。
x-sum 定义：选择 x 个频次最多的数字，求这些数字的累计和。
频次相同时，优先选择值大的数字。

思路：数组大小50，暴力枚举所有子数组，统计频次，排序，求和。
复杂度：O(n^2 log(n))

二、第 K 大的完美二叉子树的大小

题意：给一个二叉树，求第K大的完美二叉子树的节点个数。

思路：递归统计所有的完美二叉子树的节点个数，储存在最小堆里，堆大小最大为 K。

怎么判断一个子树是不是完美二叉树呢？
先判断左右子树，当左右子树都是完美二叉树 且 左右的节点个数相等时，当前子树才是完美二叉子树。

三、统计能获胜的出招序列数

题意：给一个字符串代表 A 的出牌顺序，问 B 有多少种出牌顺序，使得最终 B 的得分大于 A 的得分。
牌大小规则：F < W， W < E, E < F。
得分规则：谁大谁得分，等于都不得分。
要求：B 不能连续两次出相同的牌。

思路：动态规划。

状态定义：f[n,p,s]
含义：前 n 张牌，下一张使用 p 牌，得分至少为 s 时的方案数。

状态转移：
含义：当前位置不能选择 p， 选择其他所有牌时的方案数。
选择其他牌时，如果PK相等，则分数 s 不变。
如果输了，就需要多赚一分。
如果赢了，就可以少赚一分。

f(n,p,s) = sum(f(n-1,i, s+PK(i))), i != p;

边界1：分数可能为负，所以需要统一加上 1000。
边界2：最后一个位置有三种选择，为了避免枚举三个位置，f(n,-1,1)

复杂度: O(3^2*n^2)

四、计算子数组的 x-sum II

题意：给你一个数组，求子数组sum[i,i+k-1]的 x-sum。
x-sum 定义：选择 x 个频次最多的数字，求这些数字的累计和。
频次相同时，优先选择值大的数字。

思路：题目与第一题一样，数据范围变大了，不能暴力计算了。

显然，n-k+1个子数组的答案需要使用滑动窗口来维护一些数据结构。
即第一个子数组求出答案后，通过减去一个数字，加上一个数字，就可以快速计算出答案。

第一种方法是自己维护一个平衡树、TOP K 游标，TOP K 累计和。

数据结构1：计数器 H[v]，统计每个值当前出现的次数。
数据结构2：key为 {count, value} 的平衡树 tree，一般使用 set 来储存。
数据结构3：平衡树游标，含义为大于等于游标的节点为出现频次最高的 X 个数字。
数据结构4：sum，代表当前的答案。

滑动窗口右移时，需要删除左边的数字，添加右边的数字。
删除和添加都需要根据 {count, value} 是否在 TOP X 来做更新，相当复杂。
这里就不多介绍了，相当于是一个很大的模拟题。

复杂度：O(n log(n))

第二个方法是使用线段树单点更新区间查询来做。

先预处理滑动窗口，储存下可能遇到的所有{count,value}，排序，分配唯一标号。
线段树的节点的含义为第几个 {count,value}。
线段树里储存2个数据：区间内非0节点的个数 与 节点的区间和。

对于一个数字，根据数字的频率，根据{count,value}找到线段树的节点。
插入数字，只需要将对应的节点增加 count*value, 并标记节点有值。
删除数字，则需要将对应的节点减去 count*value, 并标记节点无值。

查询 TOP X 时，二分找到最大的 [limit, maxCount]，使得这个区间内非0节点恰好 X 个。
之后再查询 [limit, maxCount] 的区间和。
复杂度：O(n log(n) log(n))

五、最后

这次比赛最后一题其实有点难，尤其是想要直接自己维护平衡树的游标和 sum 时，分支情况特别多。
而使用线段树来做，游标通过二分来快速查找，sum直接通过线段树来求和，简单多了。

《完》

-EOF-

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