leetcode 第190算法比赛

零、背景

这次正常参加了 leetcode 的第 190 场比赛。

这次又是喜欢这次比赛，又不喜欢这次比赛。

不喜欢这次比赛是因为题目太简单的，都是基础题，比的是手速。而我敲键盘的速度大家都知道，很慢的，这方面我不占优势。

喜欢这次比赛是因为最后一题虽说是基础题，但是是动态规划的基础题，不少人面对动态规划会毫无思路，而我则是看一眼题目就直接开始敲代码的。

综合来看，这次比赛用了 25 分钟做完了，排名 25 ，好巧。

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

一、句子中单词的前缀

题意：一个句子由一组单词构成，单词间用空格分隔。
给一个字符串，问是否有单词是这个字符串的前缀，如果有，输出最小的单词下标。

思路：分割字符串得到单词列表，然后一个个比较即可。

二、子串中元音最大数目

题意：给一个字符串，问定长子串中，最多能有多少个元音。

思路：滑动窗口即可。

三、二叉树中的伪回文路径

题意：给一个二叉树，根到叶子节点组成的路径经过重排列，如果能够组成回文序列，则称为回文路径。
求回文路径个数。

思路：假设已经找到一个路径，对节点值进行统计，判断能否重排列为会问序列。

什么时候可以组成回文序列呢？
值出现奇数次的个数为一个或者零个的时候。

所以我们只需要递归二叉树求出所有的路径，顺便统计出现奇数次的个数即可。

四、两个子序列的最大点积

题意：给两个数组，两个数组中分别选出一个子序列，使得两个子序列的点积最大。

假设两个子序列分别为 [a1, a2,…, an] 和 ` [b1, b2,…, bn]。 则点积为 a1b1 + a2b2 + … + an*bn`。

思路：典型的动态规划题。

假设两个数组 A 和 B 的长度分别为 x 和 y。
则答案可以定义为 f(x, y)。
含义为子数组 A[1,x] 与 B[1,y]的最优值。

那这个最优值可能分五种情况。

-）A[x] * A[y]
-）A[x] * A[y] + f(x-1, y-1)
-) f(x-1, y)
-) f(x, y-1)
-) f(x-1,y-1)

这五种情况取 max 就是最优值了。

注意事项：由于最优值可能为负，不存在答案时，可以返回一个负无穷。

当然，比赛的时候是使用的递归实现方式，由于解题报告写完了，比赛还没结束，就又改成递推的模式了。

递归的可能清晰一些。

不过递归的时候，有个地方需要注意，不能使用-1来标记dp[x][y]是否计算过。
因为可以构造出一种 case 使 -1 这个标记的复杂度退化为指数级。

五、最后

这次比赛题目比较简单，你都做出来了吗？

思考题：最后一题那种输入会使-1标记超时？为什么？

《完》

-EOF-

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