博业建站网,做logo网站,手机制作app模板,代刷网站推广全网最便宜⭕️583. 两个字符串的删除操作 思路#xff1a;核心代码就是最长公共子序列#xff0c;但是需要注意的是结果 就是如果说公共子序列为0#xff0c;则需要两个字符串长度的才行 如果有#xff0c;就是 n m ∗ 2 d p [ n ] [ m ] nm*2dp[n][m] nm∗2dp[n][m]
int minDist…⭕️583. 两个字符串的删除操作 思路核心代码就是最长公共子序列但是需要注意的是结果 就是如果说公共子序列为0则需要两个字符串长度的才行 如果有就是 n m ∗ 2 d p [ n ] [ m ] nm*2dp[n][m] nm∗2dp[n][m]
int minDistance(string word1, string word2) {int n word1.size();int m word2.size();vectorvectorint dp(n1, vectorint(m1, 0));for(int i 1; i n 1; i){for(int j 1; j m 1; j){if(word1[i - 1] word2[j - 1]){dp[i][j] dp[i - 1][j - 1] 1;}else{dp[i][j] max(dp[i - 1][j], dp[i][j - 1]);}}}return nm-2*dp[n][m];
}712. 两个字符串的最小ASCII删除和
本质上换汤不换药~参考前面的公共子序列问题。
int minimumDeleteSum(string s1, string s2) {int n s1.size();int m s2.size();vectorvectorint dp(n1, vectorint(m1, 0));int ascii_count 0;for(int i 0; i n; i){ascii_count s1[i];}for(int i 0; i m; i){ascii_count s2[i];}for(int i 1; i n 1; i){for(int j 1; j m1; j){if(s1[i-1] s2[j-1]){dp[i][j] dp[i-1][j-1] (int)s1[i-1];}else{dp[i][j] max(dp[i-1][j], dp[i][j-1]);}}}if(dp[n][m] 0){return ascii_count;}return ascii_count-2*dp[n][m]; }1035. 不相交的线 思路本质就是求最长公共子序列 因为这道题两个连线不想交你想想如果不想交不就是公共子序列按顺序找吗 leetcode真的恶心
int maxUncrossedLines(vectorint nums1, vectorint nums2) {int n nums1.size();int m nums2.size();vectorvectorint dp(n1, vectorint(m1, 0));for(int i 1; i n 1; i){for(int j 1; j m 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 - 1][j], dp[i][j - 1]);}}}return dp[n][m];}392. 判断子序列 思路这道题很简单但是道题给了另一个不简单的方向即要匹配的字符串就数十亿个如何考虑 简单的 脑瘫写法 bool isSubsequence(string s, string t) {int n s.size();int m t.size();if(n 0){return true;}int temp 0;for(int i 0; i m; i){if(s[temp] t[i]){temp;if(temp n){return true;}}}return false;}双指针 bool isSubsequence(string s, string t) {int i 0;int j 0;int n s.size();int m t.size();while(i n j m){if(s[i] t[j]){i;}j;}return i n;}进阶数十亿的 如果有大量输入的 S称作 S1, S2, … , Sk 其中 k 10 亿你需要依次检查它们是否为 T 的子序列。在这种情况下你会怎样改变代码 空间换时间的思想。关键点是利用一个二维数组记录每个位置的下一个要匹配的字符的位置这里的字符是a ~ z所以这个数组的大小是 dp[n][26]n 为 T 的长度。那么每处理一个子串只需要扫描一遍 S 即可因为在数组的帮助下我们对 T 是“跳跃”扫描的。 如下图一很自然的当T索引为0时候对应的第0列就是当前字符在T中出现位置的下标没有的标-1就行 /*ahbgdc这个T字符串构成的数组如下重点在于从后往前构造会简单很多*/
1 -1 -1 -1 -1 -1 -1
3 3 3 -1 -1 -1 -1
6 6 6 6 6 6 -1
5 5 5 5 5 -1 -1
-1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1
4 4 4 4 -1 -1 -1
2 2 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 这个图应该能说明思想其实就是跳表的思想只要有-1就不比了不用完全遍历t时间换空间的思想。 bool isSubsequence(string s, string t) {t.insert(0, );int len t.size();vectorvectorint vec(len, vectorint(26, 0));//创建一个二维数组for(char char_t a; char_t z; char_t){int next_pos -1;//这个要放在循环里面不能放在外面for(int i len-1; i 0 ;i--){vec[i][char_t-a] next_pos;if(t[i] char_t){next_pos i;}}}//开始匹配int index 0;for(char c : s){index vec[index][c - a];if(index -1){return false;}}return true;
}115. 不同的子序列 思路 说句题外话就是两个字符串或者数字比较的话大概率不是dp就是双指针dp的话ij表示s1的前i个和s2的前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];}状态转移方程为啥是上述的只有一个办法就是画表。以后看到子序列问题的dp 画表就完事儿了 int numDistinct(string s, string t) {int n s.size();int m t.size();if(n m){return 0;}vectorvectorlong long dp(n1, vectorlong long(m1, 0));//切记空字符串匹配为1for(int i 0; i n 1; i){dp[i][0] 1; }for(int i 1; i n 1; i){for(int j 1; j m 1; j){if(s[i - 1] t[j - 1]){dp[i][j] dp[i - 1][j - 1] dp[i -1][j];if(dp[i][j]INT_MAX){dp[i][j]0;}}else{dp[i][j] dp[i - 1][j];}}}return dp[n][m];}⭕️72. 编辑距离 前面说过两个单词或者两个字符串的问题不是双指针就是动态规划问题很明显这个这么难的问题就是动态规划。 同时又是两个字符串比较那肯定 d p [ i ] [ j ] dp[i][j] dp[i][j]啊主要是这个状态转移方程不太好想 当两个字符不相等的时候有三种操作删除、插入和替换这才是状态转移方程的重点 当 word1[i] word2[j]dp[i][j] dp[i-1][j-1] 当 word1[i] ! word2[j]dp[i][j] min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) 1 其中dp[i-1][j-1] 表示替换操作dp[i-1][j] 表示删除操作dp[i][j-1] 表示插入操作。
int third_min(int a, int b, int c){int temp a b ? a : b; return temp c ? temp : c;
}
int minDistance(string word1, string word2) {int n word1.size();int m word2.size();vectorvectorint dp(n1, vectorint(m1, 0));//确定完dp后还是得考虑极端情况for(int i 0; i m 1; i){dp[0][i] i ;}for(int i 0; i n 1; i){dp[i][0] i ;}for(int i 1; i n 1; i){for(int j 1; j m 1; j){if(word1[i - 1] word2[j - 1]){dp[i][j] dp[i - 1][j - 1];}else{dp[i][j] third_min(dp[i - 1][j - 1] 1, //替换dp[i - 1][j] 1, //word1删除一个字符然后换和word2相同的这个是一个操作dp[i][j - 1] 1 //word2删除一个字符然后换和word1相同的这个是一个操作);}}}return dp[n][m];
}
