长沙专业网站建设团队,做PPT的网站canva,怎么向谷歌提交网站,网站建设费用计入哪个会计科目目录
leetcode题目
一、回文子串
二、最长回文子串
三、分割回文串 IV
四、分割回文串 II
五、最长回文子序列
六、让字符串成为回文串的最少插入次数 leetcode题目
一、回文子串
647. 回文子串 - 力扣#xff08;LeetCode#xff09;https://leetcode.cn/problems/…目录
leetcode题目
一、回文子串
二、最长回文子串
三、分割回文串 IV
四、分割回文串 II
五、最长回文子序列
六、让字符串成为回文串的最少插入次数 leetcode题目
一、回文子串
647. 回文子串 - 力扣LeetCodehttps://leetcode.cn/problems/palindromic-substrings/1.题目解析 返回给定字符串中所有回文子串的个数 2.算法分析 1.状态表示 如果是暴力解法只需要先固定下标i, 然后j从i的位置开始往后一路枚举即可下一次i, j无需回到0号下标因为[i, j]与[j, i]本质是同一个子串j直接从i位置开始枚举即可, 因此我们就把状态表示定义成二维的~ dp[i][j]: s字符串中位于区间 [i, j] 的字符串, 是否是回文串 (隐含条件: i j) 2.状态转移方程 3.初始化 初始化的目的是 保证填表时不越界 后续填表是正确的 4.填表顺序 填dp[i][j]时需要dp[i1][j-1]的值因此需要从下往上填每一行即可 5.返回值 返回dp表中值为true的个数即可 3.算法代码
class Solution {
public:int countSubstrings(string s) {//1.创建dp表int n s.size();vectorvectorbool dp(n, vectorbool(n, false));//2.填表返回值int sum 0;for(int i n-1; i 0; i--) //从下往上填表{for(int j i; j n; j){if(s[i] s[j])dp[i][j] i 1 j ? dp[i1][j-1] : true;if(dp[i][j]) sum; }}return sum;}
};
二、最长回文子串
5. 最长回文子串 - 力扣LeetCodehttps://leetcode.cn/problems/longest-palindromic-substring/1.题目解析 返回给定字符串中的最长回文子串 2.算法分析
求最长回文子串之前先要知道哪些字符串是回文串而题目一通过dp表记录了[i, j]子串是否是回文串根据dp表的值即可得到想要的结果
3.算法代码
class Solution {
public:string longestPalindrome(string s) {//1.创建dp表int n s.size();vectorvectorbool dp(n, vectorbool(n, false));//2.填表返回值int begin 0, len 0;for(int i n-1; i 0; i--) //从下往上填表{for(int j i; j n; j){if(s[i] s[j])dp[i][j] i 1 j ? dp[i1][j-1] : true;//更新结果if(dp[i][j] len j - i 1) {len j - i 1;begin i;}}}return s.substr(begin, len);}
};
三、分割回文串 IV
1745. 分割回文串 IV - 力扣LeetCodehttps://leetcode.cn/problems/palindrome-partitioning-iv/1.题目解析 判断给定的字符串是否能够分割成三个回文字符串 返回true/false 2.算法分析
本题的关键就是看给定字符串能否被分割成三个回文子串 也就是判断[0, i-1], [i, j], [j1, n-1]这三个区间的字符串是否是回文子串而题目一中我们用动态规划做到了使用dp表保存所有的子串是否是回文信息因此用o(1)的时间复杂度判断即可
3.算法代码
class Solution {
public:bool checkPartitioning(string s) {//1.创建dp表int n s.size();vectorvectorbool dp(n, vectorbool(n, false));//2.填表for(int i n-1; i 0; i--)for(int j i; j n; j)if(s[i] s[j])dp[i][j] i 1 j ? dp[i1][j-1] : true; //3.返回值for(int i 1; i n - 1; i) //第二个字符串的开始for(int j i; j n - 1; j) //第二个字符串的结束if(dp[0][i-1] dp[i][j] dp[j1][n-1])return true;return false;}
};
四、分割回文串 II
132. 分割回文串 II - 力扣LeetCodehttps://leetcode.cn/problems/palindrome-partitioning-ii/本题与 139. 单词拆分 - 力扣LeetCode 这道题目非常类似大家可以对比一下两道题的做法
【动态规划三】子数组系列-CSDN博客文章浏览阅读803次点赞20次收藏21次。f[i]以 i 位置为结尾的所有子数组中最后呈现 上升 状态下的最长的湍流子数组的长度。g[i]以 i 位置为结尾的所有子数组中最后呈现 下降 状态下的最长的湍流子数组的长度。数组中相邻元素对之间的大小关系相反这就是湍流数组题目要求返回数组中最长的湍流子数组的长度。将dp表里面所有的值都初始化成1 因此dp[i] dp[i-1] 即可。dp[i]: [0, i]区间内的字符串, 能否被字典中的单词拼接而成。dp[i] 表示 以 i 位置元素为结尾的所有子数组的最大和。https://blog.csdn.net/m0_74126249/article/details/138501298?spm1001.2014.3001.55011.题目解析 给定字符串s将s分割使得每个部分都是回文子串求最少的分割次数 2.算法分析 1.状态表示 dp[i] 表示 [0, i] 区间上的字符串, 分割成回文串的最少分割次数 2.状态转移方程 而本题目要频繁的用到判断一个字符串是否是回文因此用到题目一的做法把所有子串是否是回文的信息保存在dp表中 3.初始化 j 0, 所以填表一定不会越界 但是 dp[i] min(dp[j-1] 1, dp[i]), 所以我们把dp[i]都初始化成无穷大不会干扰结果 4.填表顺序 从左往右 5.返回值 dp[n-1] 3.算法代码
class Solution {
public:int minCut(string s) {//1.预处理isPal表int n s.size();vectorvectorbool isPal(n, vectorbool(n, false));for(int i n-1; i 0; i--)for(int j i; j n; j)if(s[i] s[j])isPal[i][j] i 1 j ? isPal[i1][j-1] : true; //2.创建dp表 初始化vectorint dp(n, INT_MAX);//3.填表for(int i 0; i n; i){if(isPal[0][i])dp[i] 0;else{for(int j 0; j i; j)if(isPal[j][i]) dp[i] min(dp[i], dp[j-1]1);}}//4.返回值return dp[n-1];}
};
五、最长回文子序列
516. 最长回文子序列 - 力扣LeetCodehttps://leetcode.cn/problems/longest-palindromic-subsequence/1.题目解析 与题目二的区别是子序列不一定连续本题求的是原字符串中最长的回文子序列 2.算法分析 1.状态表示 dp[i][j][i, j]内的所有子序列中最长的回文子序列的长度(隐含条件: i j) 2.状态转移方程 2.1 i j时, s[i] 必然 s[j], 因此我们可以在刚进入第一层for循环时就将dp[i][i]填成1 2.2 上面的s[i] s[j]中的 i 1 j 的情况合并到 i 1 j 的情况中因为当i1 j 时, dp[i1][j]都是下三角元素默认是0, 0 2还是2 不影响结果的正确性 3.初始化 无需初始化 4.填表 从下往上填表每一行从左往右填 5.返回值 dp[0, n-1] 3.算法代码
class Solution {
public:int longestPalindromeSubseq(string s) {//1.创建dp表int n s.size();vectorvectorint dp(n, vectorint(n));//2.填表for(int i n - 1; i 0; i--){dp[i][i] 1; //对应s[i] s[j] i j 的情况for(int j i 1; j n; j){if(s[i] s[j])dp[i][j] dp[i1][j-1] 2;elsedp[i][j] max(dp[i1][j], dp[i][j-1]);}}//3.返回值return dp[0][n-1];}
};
六、让字符串成为回文串的最少插入次数
1312. 让字符串成为回文串的最少插入次数 - 力扣LeetCodehttps://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome/1.题目解析 给定字符串可以在任意位置插入任意字符使其变为回文串求最少的插入次数 2.算法分析 1.状态表示 dp[i][j]s里面[i, j]区间上的字符串, 使它成为回文串的最少插入次数 2.状态转移方程 s[i] s[j]时i 1 j 的情况可以合并到 i 1 j的情况中因为i 1 j 时用到的dp[i1][j-1]本质是下三角元素直接等于0不影响结果的正确性 3.初始化 无需初始化 4.填表顺序 从下往上填表每一行从左往右 5.返回值 dp[0][n-1] 3.算法代码
class Solution
{
public:int minInsertions(string s) {//1.创建dp表int n s.size();vectorvectorint dp(n, vectorint(n));//2.填表for(int i n - 1; i 0; i--)for(int j i 1; j n; j)if(s[i] s[j]) dp[i][j] dp[i1][j-1];else dp[i][j] min(dp[i1][j], dp[i][j-1]) 1; //3.返回值return dp[0][n-1];}
};
