Leetcode 第126场比赛回顾

一、背景

前面做过 Leetcode 的第 88 场比赛，并写了《 Leecode 第88场比赛回顾 》笔记。

今天简单的做了 Leetcode 第 126 场比赛，也简单的记录一下。

二、查找常用字符

题意很简单，给一些字符串，求字符串的公共子序列。

这里还要求，允许字符串乱序，输出的时候公共子序列从小到大输出。

如果纯粹是公共子序列，那么这道题就需要使用一些高级数据结构才能解决。

但是这里允许字符串乱序，那这个问题就可以简化为计数问题了。

求多个字符串的公共子序列，其实就是循环依次求每个字符串和当前答案的公共子序列，即循环合并即可。

而对于两个字符串的计数合并，则是对每个字母计数统计，然后分别取最小值即可。

至于字符串拆分，就是一个循环而已，这里就不上代码了。

当然，我实际做的时候，没有拆分为三个函数，而是一个循环搞定的，这里拆分为三个函数好方便大家理解。

三、检查替换后的词是否有效

具体题意是： abc 字符串为有效字符串，我们把 abc 插入到一个有效字符串里面形成的字符串也是有效的。

例如 abc 插入到 abc 有四种插入法：

插入到最前面，形成 abcabc 有效字符串。

插入到第一个位置 a 之后，形成 aabcbc 有效字符串。

插入到第二个位置 b 之后，形成 ababcc 有效字符串。

插入到最后面，形成 abcabc 有效字符串。

问题：判断给定的一个字符串是否是有效的。

这道题是一个常见的题型：检查数据是否符合某种递归的模式。

最经典的就是括号匹配问题。

而对应的解决方案就是使用栈来解决。

对于递归模式，之所以能够使用栈来解决，就是因为扫描前面的数据时，暂时不知道是否满足对应的递归模式。

而我们使用栈暂时把前面的数据保存起来，当检查发现满足模式后，逆向的执行这个模式，就可以逆向的递归缩短字符串。

如果给定的字符串满足要求，则扫描完出入字符串后，栈里面也应该刚好为空。

具体到这道题，则是发现第一个字符 c 时，栈顶的两个元素肯定依次是 b 和 a 。 如果不满足，则不是有效字符串，如果满足，则继续下去即可。

四、最大连续1的个数 III

题意：给一个有 0 和 1 组成的数组，我们最多允许对 K 个 0 的值变为 1 ，求仅含 1 的最长连续子数组的长度。

如果你看我上篇文章《 Leecode 第88场比赛回顾 》的话，会发现也有一道类似的题。

那道题是给了一堆 0 和 1 ，求挑一个 0 使得这个 0 距离最近的 1 最远。

我们的方法是累计计算中间的连续 0 的个数，然后算出答案来。

那对于我们这道题，其实可以使用类似的思想，不过这里允许 0 不连续，并且最多只能累计 K 个 0 。

具体来说，就是维护一个队列，这个队列需要满足两个条件。

一、队列里面的数字是连续的。

二、队列里面 0 的个数不超过 K 个。

而我们的答案就是队列的最大长度。

而代码实现，则是扫描输入的数据，一次入队，并更新队列 0 的个数。

如果 0 的个数超过限制，则队首需要不断出队，直到满足不超过 K 个。

具体如下：

这里面有个主意实现就是，当不满足条件时，需要循环出队。因为队首可能不是 0 。

由于我们确定不满足条件时， 0 的个数肯定是 K+1 个。我们也可以直接先把队首的 1 出队，然后再出一个 0 。

当然，两个思想在逻辑上是等价的，不过第一个算法更通用写，而后面这个则更个性化。

五、合并石头的最低成本

题意是给 K 堆石头，每堆知道有多少个。

然后会对这些石头进行合并，每次把连续的 K 堆石头合并为一堆，成本是这 K 堆石头的总个数。

要求不断的合并下去，直到所有石头合并为一堆，求最小成本。

如果不能合并为一堆，则返回 -1 。

面对这道题，我们首先需要判断是否能合并为一堆。

简单观察即可发现，每合并一次，石头的堆数就减少 K-1 。

所以我们可以推导出这样一个等式： N - p * (K - 1) = 1 ，其中 N 是石头的总堆数， p 是合并的次数。

公式转化一下，则可以得到一个判断是否有答案的不等式： (N - 1) % (K - 1) == 0 。

接下来，就是假设有答案，怎么得到最优的答案了。

其实，在看到这个问题时，第一眼想到的是哈夫曼树。

但是哈夫曼树的策略是贪心算法，即不断的挑选最小的 K 个数字，而且很容易证明其正确性。

而我们这道题必须是连续的 K 个数字，贪心的话还无法证明其正确性，所以需要换个思路了。

既然是类似于哈夫曼树的题，就应该先来看看这颗树长什么样子，树的图形画出来后，题就变得比较形象了，一般也可以找到一种可视化的方案来。

比如对于第一个示例，输入是 stones = [7,7,8,6,5,6,6], K = 3 ，我们可以手动画出下面的最优树。

我们观察这个树之后，可以发现这个问题可以划分为一系列子问题来解决，大概如下图。

我们对于给如的数组序列，随意的划分为两部分，使得第一部分合并为 1 堆，第二部分合并为 K - 1 堆。

这样的划分有很多，最优答案肯定是其中一个划分（根据最优答案反推，我们可以划分出这样的图）。

既然这样，我们就可以写出对应的递归代码了。

代码里面有一个出口。

第一个是是否已经计算过，计算过则直接返回。

第二个是这个区间是否不足 K 个，不足则不需要合并，即答案是 0 。

第三个是这个区间是否刚好 K 个，这个时候直接合并为 1 个，答案就是区间和。

第四个就是上面我们提到的划分，在多个划分中找到最小的答案。

在计算划分的时候，有个注意事项就是，只有两个划分可以合并时，我们才需要加上区间和。

而对于输入，我们只需要初始化一下dp数组，然后计算前缀和即可。

六、最后

这次的四道题其实还是比较有点技术含量的，涉及到统计计数、堆、栈、动态规划四个知识点。

另外，上篇文章提到，上次的时候编程环境弄了好久，现在终于差不多稳定了。

测试的时候，差不多是这个样子。

答案对了，直接输出 YES ，答案错了，输出 NO ，并把输入和输出都输出来。

想要我的模板的，可以公众号后台回复 leetcode 获取源代码。

-EOF-