leetcode 第 204 算法比赛

零、背景

今天继续做比赛，第二题看着很简单，本想随便写写就行了，结果被卡主了。
最后只好认认真真的分析怎样才最简单，然后才通过。

以后做比赛还是要正确的对待每一道题，马虎不得。

下面来看看比赛的四道题吧。

一、重复至少 K 次且长度为 M 的模式

题意：给一个数组，问是否存在一个子数组，使得连续 M 个一组，重复 K 次。

思路：经典的字符串题。

不过作为比赛的第一题，枚举暴力判断即可。

具体实现是枚举每个起始位置，判断是否满足条件。
复杂度：O(N*M*K)

优化：由于是重复 K 个，相邻的其实位置可以复用之前的判断结果。
这样只需要扫描一遍就可以了。
复杂度：O(N)

二、乘积为正数的最长子数组长度

题意：给一个数字数组，求出乘积为正数的最长子数组的长度。

思路：一开始我的做法是标记第一个正数和负数的起始位置，然后统计两种情况负数的个数。
结果发现有各种特殊 case 负负得正使得统计错误。

后来认真思考了下，发现可以通过动态规划解决。 即每个位置有两个最优值：乘积为负数的最大长度 和 乘积为正数的最大长度。

如果下个位置是正数，两个最优值都加一。
如果下个位置是负数，两个最优值进行反转。
即正数的最大长度加一变成当前负数的最大长度，负数也一样。

注意事项：乘积遇到 0 后永远是 0，所以 0 将数组拆分若干子问题，独立计算 。

三、使陆地分离的最少天数

题意：给一个二维网格，0代表水，1代表陆地。
陆地通过上下左右连成岛屿。

每天可以将一个陆地转变为水域。
如果 恰好只有一座岛屿，则认为陆地是连通的；否则，陆地就是分离的 。 问最少需要多少天可以使陆地分离。

思路：

有两种情况陆地是非连通的，即分离的。
一种是所有陆地全部变成水域，一种是至少存在两个岛屿。

这里的关键是，消除多少个陆地才能产生至少两个岛屿。

可以分几种情况分析。

1、已经全部是水域
2、已经是非连通的，即至少两个岛屿
3、消除若干陆地，变成两个岛屿
4、消除若干陆地，全部变成水域

这四种情况中，情况三是最难得，因为我们不知道删除几个陆地才能创造出一个岛屿来。

于是我想，不管输入数据，在岛屿里随便找一个角落，至少需要消除几个陆地才能形成一个单点岛屿呢？
一画图不要紧，嘴都只需要两天即可形成岛屿。

所以情况三转化为了两种子问题。

1、消除一个岛屿是否可以满足答案。
2、否则消除两个岛屿就是答案。

分析到这里，问题就转化为了枚举题。
即枚举删除每个陆地，判断是否是分离的。

四、生成相同二叉树的数组方案数

题意：给一个数组，可以生成一个二叉查找树。
问还存在多少中不同的数组，可以生成相同的二叉查找树。

思路：大水题。

例如下图，输入是[3,4,5,1,2]。

针对一个根节点来说，左子树的数字和右子树的数字都确定了。
随意保持左子树数字相对顺序，同时保持右子树数字的相对顺序，左子树与右子树的数字是可以交叉排列的。

所以这个是一个组合问题，共有C(l+r, l)中情况。
即左子树先任意选择自己在数组中的位置，剩下的就是右子树的。

而子树内部的顺序递归处理即可。

五、最后

总结下，这次比赛的题型如下。

1、字符串题，可暴力枚举通过。
2、统计题，可动态规划通过。
3、搜索图，可贪心通过。
4、二叉树题，递归二叉树可通过。

这些题都挺不错的，没啥说的了。

思考题：这些题你都是怎么做的呢？

《完》

-EOF-

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