怎么在网站添加链接,影视设计,用vue做的网站怎么实现响应式,软件开发项目管理办法本文内容参考了代码随想录#xff0c;并进行了自己的总结。 序列问题
不连续序列
300. 最长递增子序列
int n nums.length;
int[] dp new int[n];
dp[0] 1;
for(int i 1; i n; i ) {dp[i] 1; // 每个数字自己是一个子序列for(int j 0; j i; j ) {if (num… 本文内容参考了代码随想录并进行了自己的总结。 序列问题
不连续序列
300. 最长递增子序列
int n nums.length;
int[] dp new int[n];
dp[0] 1;
for(int i 1; i n; i ) {dp[i] 1; // 每个数字自己是一个子序列for(int j 0; j i; j ) {if (nums[i] nums[j]) { // 严格递增dp[i] Math.max(dp[j] 1, dp[i]);}}
}
int res -1;
for(int i 0; i n; i ) res Math.max(dp[i], res);
return res;1143. 最长公共子序列
int n text1.length();
int m text2.length();
// dp[i][j]: nums1以i-1结尾和nums2中以j-1结尾时的公共最长子序列的长度
int[][] dp new int[n 1][m 1];
for(int i 1; i n; i ) {for(int j 1; j m; j ) {char c1 text1.charAt(i - 1);char c2 text2.charAt(j - 1);if (c1 c2) dp[i][j] dp[i - 1][j - 1] 1;else dp[i][j] Math.max(dp[i][j - 1], dp[i - 1][j]);}
}
return dp[n][m];516. 最长回文子序列
最长公共子序列变体
String s2 new StringBuffer(s).reverse().toString();
// 求s和s2的最长公共子序列的长度
int n s.length();
int[][] dp new int[n 1][n 1];
for(int i 1; i n; i ) {for(int j 1; j n; j ) {char c1 s.charAt(i - 1);char c2 s2.charAt(j - 1);if (c1 c2) dp[i][j] dp[i - 1][j - 1] 1;else dp[i][j] Math.max(dp[i - 1][j], dp[i][j - 1]);}
}
return dp[n][n];1035. 不相交的线
最长公共子序列变体
int n nums1.length;
int m nums2.length;
// dp[i][j]: nums1以i-1结尾和nums2中以j-1结尾时的公共最长子序列的长度
int[][] dp new int[n 1][m 1];
for(int i 1; i n; i ) {for(int j 1; j m; j ) {if (nums1[i - 1] nums2[j - 1]) dp[i][j] dp[i - 1][j - 1] 1;else dp[i][j] Math.max(dp[i][j - 1], dp[i - 1][j]); }
}
return dp[n][m];583. 两个字符串的删除操作
最长公共子序列变体
// 先求最长公共子序列的长度
int n word1.length();
int m word2.length();
int[][] dp new int[n 1][m 1];
for(int i 1; i n; i ) {for(int j 1; j m; j ) {char c1 word1.charAt(i - 1);char c2 word2.charAt(j - 1);if (c1 c2) dp[i][j] dp[i - 1][j - 1] 1;else dp[i][j] Math.max(dp[i - 1][j], dp[i][j - 1]);}
}
return n m - 2 * dp[n][m];注意1143. 最长公共子序列和718. 最长重复子数组的区别。
/* 1143. 最长公共子序列 */
int n text1.length();
int m text2.length();
// dp[i][j]: nums1以i-1结尾和nums2中以j-1结尾时的公共最长子序列的长度
int[][] dp new int[n 1][m 1];
for(int i 1; i n; i ) {for(int j 1; j m; j ) {char c1 text1.charAt(i - 1);char c2 text2.charAt(j - 1);if (c1 c2) dp[i][j] dp[i - 1][j - 1] 1;else dp[i][j] Math.max(dp[i][j - 1], dp[i - 1][j]); }
}
return dp[n][m]; /* 718. 最长重复子数组 */
int n nums1.length;
int m nums2.length;
// dp[i][j]: nums1以i-1结尾和nums2中以j-1结尾时的公共最长子数组的长度
int res 0;
int[][] dp new int[n 1][m 1];
for(int i 1; i n; i ) {for(int j 1; j m; j ) {if (nums1[i - 1] nums2[j - 1]) dp[i][j] dp[i - 1][j - 1] 1;res Math.max(res, dp[i][j]);}
}
return res;为什么要 n1 和 m1而不是 n 和 m因为在递推式中会用到 dp[0][0]、dp[0][0~m-1]、dp[0~n-1][0]。取成 n1 和 m1 就可以从 [1, n] 和 [1,m] 开始遍历。如果取 n 和 m 的话就要从 [0, n-1] 和 [0,m-1] 开始遍历就要单独把 dp[0][0~m-1]、dp[n-1][0] 拿出来考虑代码会显得比较冗长。从题目的区别来说1143 这个题是求的分开的子序列的长度718 这个题是球的连续的子序列的长度。注意两个区别 (1). 递推式中1143 这个题 c1 ! c2 时会进行递推。而 718 这个题 nums1[i - 1] ! nums2[j - 1] 时不会进行递推而是直接置为 0。为什么会这样具体看 718 上面这个题的总结。 (2). 取答案的时候1143 这个题是直接返回的 dp[n][m]因为取的是分开的公共子序列的最长长度所以答案一定是会累加到最后的 dp[n][m] 上的。而 718 这个题返回的是 Math.max(dp[i][j])因为求的时候一旦不连续了就会置为 0前面计算的连续的长度就不会累加到后面每个 dp[i][j] 计算的就是断开的几段连续子序列的长度断开是因为置为 0 了导致断开了。所以要求答案得时候就要每个 dp[i][j] 取最大值即求所有断开的连续子序列的最大长度。
连续序列
718. 最长重复子数组
int n nums1.length;
int m nums2.length;
// dp[i][j]: nums1以i-1结尾和nums2中以j-1结尾时的公共最长子数组的长度
int res 0;
int[][] dp new int[n 1][m 1];
for(int i 1; i n; i ) {for(int j 1; j m; j ) {if (nums1[i - 1] nums2[j - 1]) dp[i][j] dp[i - 1][j - 1] 1;else dp[i][j] 0;res Math.max(res, dp[i][j]);}
}
return res;// ✔ 正确写法
if (nums1[i] nums2[j]) dp[i][j] dp[i - 1][j - 1] 1;
else dp[i][j] 0;// ❌ 错误写法
if (nums1[i] nums2[j]) dp[i][j] dp[i - 1][j - 1] 1;
else dp[i][j] Math.max(dp[i - 1][j], dp[i][j - 1]);注意第二种写法和第一种写法的区别。我最开始是写的第二种写法但仔细分析就会发现这种写法算的实际上是分开的子数组长度不是连续的子数组长度。因为要保证连续所以一旦nums1[i] ! nums2[j]即当前两个子序列的最后一个数不一样就说明不连续了 dp[i][j] 就要置为 0而不是取子序列的长度。
编辑距离
72. 编辑距离
// dp[i][j]: word1前i个字符和word2前j个字符的最短编辑距离/**c1 c2, 不需要编辑, dp[i][j] dp[i - 1][j - 1]; c1 ! c2, 需要编辑. 编辑分三种情况:(1). 删除, 将word1中, c1删除 (2). 删除, 将word2中, c2删除(3). 替换, 将word1中c1替换成c2由于删除和添加是一样的效果所以可以选择删除作为操作。*/int n word1.length();
int m word2.length();
int[][] dp new int[n 1][m 1];// 初始化当一个字符串为空的时候剩下一个字符串要做i/j次操作才能保证二者相同
for(int i 0; i n; i ) dp[i][0] i;
for(int j 0; j m; j ) dp[0][j] j;for(int i 1; i n; i ) {for(int j 1; j m; j ) {char c1 word1.charAt(i - 1);char c2 word2.charAt(j - 1);if (c1 c2) dp[i][j] dp[i - 1][j - 1];else dp[i][j] Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) 1;}
}return dp[n][m];
