力扣-子序列问题

1.524. 通过删除字母匹配到字典里最长单词,隐含的子序列问题,不过这个判断的函数比较简单,判断一个字串是否是另一个的子序列。

2.392. 判断子序列,其实这个是双指针解决的问题,在有大量s的情况下就简历下标dp数组,减少在t中查找下一个字符的时间。

3.674. 最长连续递增序列,比较简单,可以说是贪心,其实我认为是dp,比较简单。

4.300. 最长递增子序列,dp可以解决O(n^2),第二种方法利用到了贪心+二分法,d[i]记录最长递增长度i时的数值,贪心是指使上升子序列尽可能的长,则我们需要让序列上升得尽可能慢,因此我们希望每次在上升子序列最后加上的那个数尽可能的小

5.673. 最长递增子序列的个数,挺难的,需要cnt记录序列个数,len记录序列最长大小,O(n^2)的解法。

6.334. 递增的三元子序列,可以用dp解法,但是复杂度太高,O(n)的解法用了双指针,small和mid分别指向最小值和中间,很绝,也把这道题放在双指针博客里。

7.583. 两个字符串的删除操作,两种解法:一种是LCS,m+n-2*lcs,分为字符相等时,字符不等就删除,dp[i][j]表示字串1的前i个字符和字串2的前j个字符的LSC;一种是编辑距离计算方法,认为只有删除操作。都可以使用一维滚动数组来减小空间复杂度。

8.712. 两个字符串的最小ASCII删除和,两种解法:一种是dp就保存最小删除的字符ASCII值,每次删除时加上;一种是LCS,dp保存LCS中的最大ASCII值,每次能够匹配上时+值。

9.354. 俄罗斯套娃信封问题,是个二维的最长递增子序列问题,和300很相似,第一维升序排列,第二维降序排列,即固定了第一维只考虑第二维度上的最长递增子序列问题。法一使用dp,是O(n^2)的复杂度;法二,是贪心+二分的解法,这个非常快,参考300.

原文地址:https://www.cnblogs.com/BlueBlueSea/p/14180818.html