讨论/题目交流/🏆 第 190 场力扣周赛/
🏆 第 190 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 检查单词是否为句中其他单词的前缀
4 分 - 定长子串中元音的最大数目
5 分 - 二叉树中的伪回文路径
6 分 - 两个子序列的最大点积

展开讨论
力扣 (LeetCode)发起于 2020-05-24

(10:45)T4 我怎么老是T, 是不是想复杂了 O(nm(n + m))就炸了.

(11:40)已经A了, 感觉自己是个zz

这次题目真的想通了很简单。

T1. 检查单词是否为句中其他单词的前缀
签到题。直接拆分每个单词, 然后从前往后找searchWord是不是该单词的前缀。注意一找到立刻退出即可。

T2. 定长子串中元音的最大数目
签到题。直接用前缀和算一下就可以了。当然滑动窗口更容易想。
时间复杂度O(n)O(n).

T3. 二叉树中的伪回文路径
中档题。直接暴力DFS即可。 只需要每次记录路径中的数字出现的个数。当进入该点时 + 1, 退出该点时 - 1即可。 注意不可直接直接暴力提取所有路径,会爆内存。
然后判断回文串, 最多只有1个数字出现奇数次就可以组成回文串。 否则不行。

时间复杂度O(nk)O(nk). kk为数字种类数量, 这道题里面为10.

T4. 两个子序列的最大点积
中档题。 如果大家做过那种最长公共子序列的话就非常容易想了。
我最初是考虑转移状态的时候必须遍历之前所有状态, 所以超了。 但是根据dp顺序, 之前的状态都遍历过,所以和那个最长公共子序列是一样的。

f(i,j)f(i, j) 代表第一个序列前i个元素, 第二个序列前j个元素所组成的乘积最大值)。
因此, 有三种情况。

不取A[i], 不取B[j], 两个都取。

f(i,j)=max(f(i1,j),f(i,j1),f(i1,j1)+A[i]B[j])f(i, j) = max(f(i-1, j), f(i, j-1), f(i-1, j-1) + A[i] * B[j])

这样时间复杂度就是O(nm)O(nm)了。

展开全部 31 讨论