信誉好的福州网站建设,本网站建设,做网站的职位叫什么问题,短网址恢复前言
差单调栈就结束代码随想录一刷啦#xff0c;回家二刷打算改用python补充进博客#xff0c;小涛加油#xff01;#xff01;#xff01;
647. 回文子串 - 力扣#xff08;LeetCode#xff09; 双指针法 中心点外扩#xff0c;注意中心点可能有一个元素可能有两个…前言
差单调栈就结束代码随想录一刷啦回家二刷打算改用python补充进博客小涛加油
647. 回文子串 - 力扣LeetCode 双指针法 中心点外扩注意中心点可能有一个元素可能有两个元素 class Solution {
public:int countSubstrings(string s) {int result 0;for (int i 0; i s.size(); i) {result extend(s, i, i, s.size()); // 以i为中心result extend(s, i, i 1, s.size()); // 以i和i1为中心}return result;}// 中心点出发回文则持续外扩int extend(const string s, int i, int j, int n) {int res 0;while (i 0 j n s[i] s[j]) {i--;j;res;}return res;}
}; 动态规划法 dp数组含义 dp[i][j]表示区间范围[i,j] 左闭右闭的子串是否是回文子串如果是dp[i][j]为true否则为false递推公式 s[i]与s[j]不相等dp[i][j] falses[i]与s[j]相等 情况一i 与 j相同adp[i][j] true情况二i 与 j相差1aadp[i][j] true情况三i 与 j相差大于1例如cabac看dp[i 1][j - 1]是否为true if (s[i] s[j]) {if (j - i 1) { // 情况一 和 情况二result;dp[i][j] true;} else if (dp[i 1][j - 1]) { // 情况三result;dp[i][j] true;}
} 初始化 dp[i][j] false遍历顺序从下到上从左到右 class Solution {
public:int countSubstrings(string s) {vectorvectorbool dp(s.size(), vectorbool(s.size(), false));int result 0;for (int i s.size() - 1; i 0; i--) { // 注意遍历顺序for (int j i; j s.size(); j) {if (s[i] s[j]) {if (j - i 1) { // 情况一 和 情况二result;dp[i][j] true;} else if (dp[i 1][j - 1]) { // 情况三result;dp[i][j] true;}}}}return result;}
};
516. 最长回文子序列 - 力扣LeetCode
dp[i][j]含义 字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]递推公式 s[i]与s[j]相同 dp[i][j] dp[i 1][j - 1] 2;s[i]与s[j]不相同 dp[i][j] max(dp[i 1][j], dp[i][j - 1]);初始化 dp[i][i] 1其他为1从下到上从左到右 class Solution {
public:int longestPalindromeSubseq(string s) {vectorvectorint dp(s.size(), vectorint(s.size(), 0));for (int i 0; i s.size(); i) dp[i][i] 1;for (int i s.size() - 1; i 0; i--) {for (int j i 1; j s.size(); j) { // j从i1开始if (s[i] s[j]) {dp[i][j] dp[i 1][j - 1] 2;} else {dp[i][j] max(dp[i 1][j], dp[i][j - 1]);}}}return dp[0][s.size() - 1];}
};
子序列问题总结 动态规划总结
