网站建设费无形资产,seo外包公司哪家专业,哪里有网站建设企业,如何免费申请自己的网站目录
31. LeetCode674. 最长连续递增序列
32. LeetCode18. 最长重复子数组
33. LeetCode1143. 最长公共子序列
34. LeetCode1035. 不相交的线
35. LeetCode53. 最大子数组和
36. LeetCode392.判断子序列
37. LeetCode115. 不同的子序列
38. LeetCode583. 两个字符串的删…目录
31. LeetCode674. 最长连续递增序列
32. LeetCode18. 最长重复子数组
33. LeetCode1143. 最长公共子序列
34. LeetCode1035. 不相交的线
35. LeetCode53. 最大子数组和
36. LeetCode392.判断子序列
37. LeetCode115. 不同的子序列
38. LeetCode583. 两个字符串的删除操作
39. LeetCode72. 编辑距离 思路
1.dp含义
dp[i]集合nums从下标0到下标i并且以nums[i]结尾的最长递增子序列长度
(1)为什么能够以nums[i]结尾因为每个递增子序列必定是以集合nums中的其中一个元素结尾。
(2)为什么一定要以nums[i]结尾因为在递推时我们需要与前一个递增子序列作比较而只有知道尾元素大小才能有效地比较。
2.转移方程
if(nums[j]nums[i])dp[i]max(dp[i],dp[j]1);//j0~(i-1)
3.初始化dp
dp[0]1;方法一动态规划
class Solution {
public:int lengthOfLIS(vectorint nums) {if(nums.size()1)return nums.size();//dp[i]集合nums从下标0到下标i并且以nums[i]结尾的最长递增子序列长度vectorintdp(nums.size(),1);//基础长度是1int res0;//完善dpfor(int i1;inums.size();i){for(int j0;ji;j){if(nums[j]nums[i])dp[i]max(dp[i],dp[j]1);//保留以nums[i]结尾最大长度}resmax(dp[i],res);//保留整体集合最长递增子序列长度}return res;}
};
时间复杂度O(n^2)
空间复杂度O(n)方法二贪心动态规划
ends[i]所有长度为i1的递增子序列的尾元素最小值且ends[i]必定小于ends[i1]
为什么ends[i]ends[i1]设以ends[i]、ends[i1]结尾的递增子序列分别为subSequence1长度为i1subSequence2长度为i2
假设ends[i]ends[i1]即subSequence1[i]subSequence2[i1]由于递增
所以subSequence1[i]subSequence2[i1]subSequence2[i] subSequence1[i]subSequence2[i]
则 ends[i]subSequence2[i]有矛盾所以假设不成立。class Solution {
public:int lengthOfLIS(vectorint nums) {if(nums.size()1)return nums.size();//ends[i]所有长度为i1的递增子序列的尾元素最小值且ends[i]必定小于ends[i1]vectorintends(nums.size());ends[0]nums[0];int right0;for(int i1;inums.size();i){//长度最长的递增子序列尾元素小于nums[i]有效区域右移并记录最小尾元素if(ends[right]nums[i]){ends[right]nums[i];}else{int l0;while(lrightends[l]nums[i]){//找到ends最左边比nums[i]大的尾元素l;}//退出循环有两种情况只有第二种情况才能赋值if(ends[l]nums[i])ends[l]nums[i];}}//ends[right]是长度为right1的递增子序列的最小尾元素return right1;}
};
时间复杂度O(n*logn)
空间复杂度O(n)
31. LeetCode674. 最长连续递增序列
1.dp[i]以nums[i]结尾的连续递增序列长度
2.if(nums[i]nums[i-1])dp[i]dp[i-1]1因为是连续的所以只需要考虑nums[i]是否比nums[i-1]大就行了贪心
3.初始化dp全都初始化成1因为至少包含nums[i]动态规划
class Solution {
public:int findLengthOfLCIS(vectorint nums) {if(nums.size()1)return nums.size();//dp[i]以nums[i]结尾的连续递增序列长度vectorintdp(nums.size(),1);int resINT_MIN;//完善dpfor(int i1;inums.size();i){if(nums[i]nums[i-1])dp[i]dp[i-1]1;resmax(res,dp[i]);//记录最长连续递增序列长度}return res;}
};贪心
class Solution {
public:int findLengthOfLCIS(vectorint nums) {if(nums.size()1)return nums.size();int count1;//记录过程中个递增序列长度int resINT_MIN;//记录最长递增序列长度for(int i1;inums.size();i){if(nums[i]nums[i-1])count;else count1;//重新取递增序列头元素resmax(res,count);}return res;}
};与前一题的区别是
本题dp[i]状态之和dp[i-1]有关因为是连续的。
而前一题因为是不连续的所以dp[i]状态和dp[0]/dp[1]/.../dp[i-1]都有关系
32. LeetCode18. 最长重复子数组
1.dp[i][j]以nums1[i]结尾的nums1和以nums2[j]结尾的nums2的重复子数组长度
2.if(nums1[i]nums[j])dp[i][j]dp[i-1][j-1]1;else dp[i][j]0;
3.初始化dp普通动态规划二维表
class Solution {
public:int findLength(vectorint nums1, vectorint nums2) {//长度是1看唯一元素是否相同if(nums1.size()1nums2.size()1)return nums1[0]nums2[0]?1:0;//dp[i][j]以nums1[i]结尾的nums1和以nums2[j]结尾的nums2的重复子数组长度vectorvectorintdp(nums1.size(),vectorint(nums2.size()));//记录最长重复子数组长度int res0;//初始化dpfor(int i0;inums1.size();i){if(nums1[i]nums2[0])dp[i][0]1;resmax(res,dp[i][0]);}for(int j0;jnums2.size();j){if(nums2[j]nums1[0])dp[0][j]1;resmax(res,dp[0][j]);}//完善dpfor(int i1;inums1.size();i){for(int j1;jnums2.size();j){if(nums1[i]nums2[j]){dp[i][j]dp[i-1][j-1]1;}else{//如果nums1[i]!nums2[j]那必不可能重复因为子数组一定要包含nums1[i]和nums2[j]dp[i][j]0;}resmax(res,dp[i][j]);}}return res;}
};观察上方代码发现不仅要额外判断数组长度为1时的情况还要在初始化dp时更新res代码略显臃肿。
再看转移方程我们可以多一行一列基础值为0但也因此有额外空间开销
1.dp[i][j]以nums1[i-1]结尾的nums1和以nums2[j-1]结尾的nums2的重复子数组长度
2.if(nums1[i]nums[j])dp[i][j]dp[i-1][j-1]1;else dp[i][j]0;
3.初始化dp
改良动态规划二维表代码行数更少
class Solution {
public:int findLength(vectorint nums1, vectorint nums2) {//dp[i][j]以nums1[i-1]结尾的nums1和以nums2[j-1]结尾的nums2的重复子数组长度vectorvectorintdp(nums1.size()1,vectorint(nums2.size()1));//记录最长重复子数组长度int res0;//完善dpfor(int i1;inums1.size()1;i){for(int j1;jnums2.size()1;j){if(nums1[i-1]nums2[j-1])dp[i][j]dp[i-1][j-1]1;else dp[i][j]0;resmax(res,dp[i][j]);}}return res;}
};滚动数组
观察转移方程dp是一行一行更新并且是从左到右
class Solution {
public:int findLength(vectorint nums1, vectorint nums2) {vectorintdp(nums2.size()1);int res0;for(int i1;inums1.size()1;i){for(int jnums2.size();j1;j--){//滚动数组应当优先更新那些不用来递推其他dp值的if(nums1[i-1]nums2[j-1])dp[j]dp[j-1]1;else dp[j]0;resmax(res,dp[j]);}}return res;}
};总结
实现出动态规划二维表后观察转移方程看是否能够利用滚动数组实现一般来说一行一行遍历的都可以转成一维数组。
33. LeetCode1143. 最长公共子序列
1.dp[i][j]text1[0,i-1]和text2[0,j-1]的最长公共子序列长度
2.if(text[i]text[j])dp[i][j]dp[i-1][j-1]1;else dp[i][j]max(dp[i-1][j],dp[i][j-1]);class Solution {
public:int longestCommonSubsequence(string text1, string text2) {//dp[i][j]text1[0,i-1]和text2[0,j-1]的最长公共子序列长度vectorvectorintdp(text1.length()1,vectorint(text2.length()1));//完善dpfor(int i1;itext1.length()1;i){for(int j1;jtext2.length()1;j){if(text1[i-1]text2[j-1]){dp[i][j]dp[i-1][j-1]1;}else{//text1[i-1]!text2[j-1]//1.text1[i-2]和text[j-1]比较//2.text1[i-1]和text[j-2]比较//上述两种情况已经涵盖了所有可能性text1[i-2]子序列涵盖了text1[i-3]所有子序列//text1[i-1]和text2[j-1]是新出现的字符所以必须带着dp[i][j]max(dp[i-1][j],dp[i][j-1]);//记忆化搜索}}}return dp[text1.length()][text2.length()];}
};
34. LeetCode1035. 不相交的线
思路
线只要在连接nums1和nums2的元素时按照相对同样的顺序就不会相交所以本质上是求nums1和nums2最长公共子序列长度。1.dp[i][j]nums1[0,i-1]和nums2[0,j-1]的公共子序列长度
2.if(nums1[i-1]nums2[j-1])dp[i][j]dp[i-1][j-1]1;else dp[i][j]max(dp[i-1][j],dp[i][j-1]);class Solution {
public:int maxUncrossedLines(vectorint nums1, vectorint nums2) {//dp[i][j]nums1[0,i-1]和nums2[0,j-1]的公共子序列长度vectorvectorintdp(nums1.size()1,vectorint(nums2.size()1));//完善dpfor(int i1;inums1.size()1;i){for(int j1;jnums2.size()1;j){if(nums1[i-1]nums2[j-1])dp[i][j]dp[i-1][j-1]1;else dp[i][j]max(dp[i][j-1],dp[i-1][j]);}}return dp[nums1.size()][nums2.size()];}
};
35. LeetCode53. 最大子数组和
1.dp[i]以nums[i-1]结尾的最大子数组和
2.if(dp[i-1]0)dp[i]dp[i-1]nums[i];else dp[i]nums[i-1];class Solution {
public:int maxSubArray(vectorint nums) {//dp[i]以nums[i]结尾的最大子数组和vectorintdp(nums.size()1);int resINT_MIN;//完善dpfor(int i1;inums.size()1;i){//只有前面子数组和为正才对自己有帮助才能够获取最大子数组和if(dp[i-1]0)dp[i]dp[i-1]nums[i-1];else dp[i]nums[i-1];resmax(res,dp[i]);}return res;}
};dp[i]只与dp[i-1]有关与dp[i-1]前的元素都无关所以我们只需一个值即可
class Solution {
public:int maxSubArray(vectorint nums) {int cur0;int resINT_MIN;for(int i0;inums.size();i){if(cur0){curcurnums[i];}else{//cur0只会减少后续子数组和curnums[i];}resmax(res,cur);}return res;}
};
36. LeetCode392.判断子序列
1.dp含义
dp[i][j]以s[i-1]结尾的字符串s和以t[j-1]结尾的字符串t相同子序列长度
注意是判断s是否为t的子序列所以t.length()s.length()s一定要包含s[i-1]t不一定要包含t[j-1]2.转移方程
只需要考虑删除字符串t的元素即可
if(s[i-1]t[j-1])dp[i][j]dp[i-1][j-1]1;//t中新出现的字符能够和s[i-1]匹配
else dp[i][j]dp[i][j-1];//无法匹配t删除元素继续匹配然前一个字符去处理3.初始化dp
//初始化二维数组dp时就已经完成了
dp[0][j]0;
dp[i][0]0;4.遍历顺序
dp值从左上角递推而得
i从上到下
j从左至右class Solution {
public:bool isSubsequence(string s, string t) {//dp[i][j]以s[i-1]结尾的字符串s和以t[j-1]结尾的字符串t相同子序列长度vectorvectorintdp(s.length()1,vectorint(t.length()1));//完善dpfor(int i1;is.length()1;i){for(int ji;jt.length()1;j){if(s[i-1]t[j-1])dp[i][j]dp[i-1][j-1]1;else dp[i][j]dp[i][j-1];}}return dp[s.length()][t.length()]s.length();}
};双指针法
创建两个索引指针sIndex、tIndex分别指向s和t如果t[tIndex]s[sIndex]那么两根指针同时后移否则tIndex后移直到sIndex扫完s
恰好也符合子序列顺序。
class Solution {
public:bool isSubsequence(string s, string t) {int sIndex0;//指向s字符的指针int tIndex0;//指向t字符的指针while(sIndexs.length()tIndext.length()){if(s[sIndex]t[tIndex]){sIndex;tIndex;}else{tIndex;}}//sIndex扫过的区域都是在t中以同样的顺序出现过的return sIndexs.length();}
};
37. LeetCode115. 不同的子序列
解读题意从s中可以找出几个子序列恰好和t相同。s如何删除元素可以变成t
1.dp含义
dp[i][j]以s[i-1]结尾的字符串s中以t[j-1]结尾的字符串t个数2.转移方程
只有出现新字符时下一轮循环才会有未考虑的情况对于新出现字符只有两种考虑使用或不使用
if(s[i-1]t[j-1])dp[i][j]dp[i-1][j-1]dp[i-1][j];//s[i-1]可使用也可不使用(模拟删除)两种情况总和。t无法删除元素
else dp[i][j]dp[i-1][j];//不匹配不用考虑s[i-1]3.初始化dp
dp[0][j]0;
dp[i][0]1;
dp[0][0]1;4.遍历顺序
i从上到下
j从左到右class Solution {
public:int numDistinct(string s, string t) {//dp[i][j]以s[i-1]结尾的字符串s中以j[i-1]结尾的字符串t个数vectorvectoruint64_tdp(s.length()1,vectoruint64_t(t.length()1));//初始化dpfor(int i0;is.length()1;i){dp[i][0]1;}for(int j1;jt.length()1;j){dp[0][j]0;}//完善dpfor(int i1;is.length()1;i){for(int j1;jt.length()1;j){if(s[i-1]t[j-1])dp[i][j]dp[i-1][j-1]dp[i-1][j];else dp[i][j]dp[i-1][j];}}return dp[s.length()][t.length()];}
};
38. LeetCode583. 两个字符串的删除操作
思路
二维数组因为需要操作两个字符串1.dp含义
dp[i][j]让以word1[i-1]结尾的字符串word1和以word2[j-1]结尾的字符串word2相同的最少操作数
2.转移方程
对于新字符word1[i-1]和word2[j-1]只有相同和不相同两种情况
if(word1[i-1]word[j-1])dp[i][j]dp[i-1][j-1];//保留这两字符可以减少两步删除操作
else dp[i][j]min(dp[i-1][j]1,dp[i][j-1]1,dp[i-1][j-1]2);//二者选一个删除或都删除取最小操作数
3.遍历顺序
i从上到下
j从左到右
4.初始化dp
dp[0][j]j;//word1是空字符word2必须删掉所有字符才能相同
dp[i][0]i;class Solution {
public:int minDistance(string word1, string word2) {//dp[i][j]让以word1[i-1]结尾的字符串word1和以word2[j-1]结尾的字符串word2相同的最少操作数vectorvectorintdp(word1.length()1,vectorint(word2.length()1));//初始化dpfor(int i0;iword1.length();i){dp[i][0]i;}for(int j0;jword2.length();j){dp[0][j]j;}//完善dpfor(int i1;iword1.length();i){for(int j1;jword2.length();j){if(word1[i-1]word2[j-1])dp[i][j]dp[i-1][j-1];else dp[i][j]min(dp[i-1][j]1,min(dp[i][j-1]1,dp[i-1][j-1]2));}}return dp[word1.length()][word2.length()];}
};也可以求最长公共子序列长度然后经过计算得出结果。
39. LeetCode72. 编辑距离
思路
虽然题目说让word1变成word2但也可以让word2变成word1。因为删除word1的字符等效于在word2中添加字符所以删除操作包含了添加操作1.dp含义
dp[i][j]让以word1[i-1]结尾的字符串word1和以word2[j-1]结尾的字符串word2相同的最少操作数
2.转移方程
if(word1[i-1]word2[j-1])dp[i][j]dp[i-1][j-1];
else{dp[i][j]min(dp[i-1][j]1,dp[i][j-1]1);//删除这二者已经包含了dp[i-1][j-1]2dp[i][j]min(dp[i][j],dp[i-1][j-1]1);//替换
}
3.遍历顺序
i从上到下
j从左到右
4.初始化dp
dp[0][j]j;
dp[i][0]i;class Solution {
public:int minDistance(string word1, string word2) {//dp[i][j]让以word1[i-1]结尾的字符串word1和以word2[j-1]结尾的字符串word2相同的最少操作数vectorvectorintdp(word1.length()1,vectorint(word2.length()1));//初始化dpfor(int i0;iword1.length();i){dp[i][0]i;}for(int j0;jword2.length();j){dp[0][j]j;}//完善dpfor(int i1;iword1.length();i){for(int j1;jword2.length();j){if(word1[i-1]word2[j-1])dp[i][j]dp[i-1][j-1];else{dp[i][j]min(dp[i-1][j]1,dp[i][j-1]1);//删除这二者已经包含了dp[i-1][j-1]2dp[i][j]min(dp[i][j],dp[i-1][j-1]1);//替换}}}return dp[word1.length()][word2.length()];}
};
