leetcode 第 355 场算法比赛

零、背景

这次比赛第三题蛮难得。

一、按分隔符拆分字符串

题意：给一个字符串数组，给一个分隔符对每个字符串进行拆分，求最终得到的所有字符串。

思路：分隔符只有一个，可以使用临时字符串来储存不等于分隔符的前缀。
一旦遇到分隔符，临时字符串不为空就是其中一个答案。

二、合并后数组中的最大元素

题意：给一个数组，可以执行下面的操作。
操作：相邻元素后面的大于前面时，后面元素的值替换为两个元素求和，删除前面的元素。
问执行无数次操作后，可以得到的数组的最大值是多少。

思路：显然，需要从后到前来判断，因为如果后面的大于前面的，则后面的可以比前面的得到更大的值。
从后到前循环，判断当前后面累计的值是否大于前面，大于了则吸收前面的。

思考题：如果不是相邻元素做合并，而是任意两个元素满足后面大于前面时，做合并，又该如何做呢？

三、长度递增组的最大数目

题意：给一个数组，代表每个下标对应数字的个数。
现在需要创建不同大小的集合，且集合的大小都不同。
问可以创建多少个集合。

思路：要求集合大小不同，显然集合大从 1 开始连续递增答案是最优的。
总结下，就是创建 k 个集合，大小分别为 1、2、3、…、k，求最大 K。

很容易想到一种思路来构建这样的集合。
集合的构建顺序是从小到大。
对于每个集合，假设大小为 x，判断剩余的下标中，个数是否大于 x。
如果大于，则说明可以构造出这个集合，选择剩余次数最多的 x 个下标。

对于这种思路，需要维护一个数据结构，需要满足以下几个性质。

1）储存n个数字的次数。
2）判断次数大于0的数字个数。
3）对次数最多的 TOP X 个数字，次数分别建议。

对于这个数据结构，我首先想到的是树状数组或者线段树。
复杂度是 O(n log(n) log(n))，超时了。

赛后发现可以贪心，一层循环就解决。
大概在心中模拟了这种算法，发现确实是正确的，但是目前还无法严格证明（如果我想出来了，或者有人评论证明方法了，我会置顶评论）。

题解中还看到一些高级数据结构算法，即支持拆分与合并的平衡树，如无旋 Treap 和 Splay。

四、树中可以形成回文的路径数

题意：给一个简单树，边上有个字符。
问存在多少条路径，边上字符重排序后，可以得到回文串。

思路1：树形DP。

我首先想到的是树形DP。

我这边一开始没想到 LCA，直接使用子树集合合并，超时了。

看题解可以利用 LCA 的性质，这样就可以采用轻边往重边合并来防止超时。

思路2：点集合。

有了 LCA 的性质，没必要统计子树了，每个路径和已处理路径做运算即可。

思路3：点分治。

与第三题一样，又是高级复杂数据结构。

点分治的关键在于每一轮递归都要重新选择当前子树的重心作为根节点，根据重心的性质，每一轮递归后，树的大小至少减半，因此递归深度不超过 log⁡n。

感兴趣的可以看资料：https://oi-wiki.org/graph/tree-divide/

五、最后

这次比赛后第三题蛮难的，比赛不到 50 人做出来，你是怎么做的？

《完》

-EOF-

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