楚雄网站建设rewlkj,施工企业价值链,个人网页设计模板教程,有哪些可以免费做视频的网站一#xff0c;最长回文串
1.题目 给你一个字符串 s #xff0c;找出其中最长的回文子序列#xff0c;并返回该序列的长度。 子序列定义为#xff1a;不改变剩余字符顺序的情况下#xff0c;删除某些字符或者不删除任何字符形成的一个序列。 示例 1#xff1a; 输入…
一最长回文串
1.题目 给你一个字符串 s 找出其中最长的回文子序列并返回该序列的长度。 子序列定义为不改变剩余字符顺序的情况下删除某些字符或者不删除任何字符形成的一个序列。 示例 1 输入s bbbab
输出4
解释一个可能的最长回文子序列为 bbbb 。示例 2 输入s cbbd
输出2
解释一个可能的最长回文子序列为 bb 。提示 1 s.length 1000s 仅由小写英文字母组成 2.题目接口
class Solution {
public:int longestPalindromeSubseq(string s) {}
}; 3.解题思路及其代码 在思考这道题时我们先想到的可能是dp[i]来作状态转移方程,表示以第i个位置为结尾的最长回文子序列。但是我们是不能这样定义的。因为第i个位置能不能加入到这个子序列中是要看当前子序列的开头位置的字符是否与之匹配的。 在弄明白抛弃掉这种想法以后我们便可以试着以区间dp的方式来解决 1.状态表示dp[i][j]表示在区间[i,j]的最长子序列。 2.状态转移方程对于状态转移方程的推导需要分类讨论分类如下 在第二种情况下dp[i][j]要等于在这三种情况下的最大值又因为dp[i1][j-1]其实是在剩下的两种情况中包含的所以dp[i][j] max(dp[i1][j],dp[i][j-1])。 代码 根据以上思路写出代码如下 class Solution {
public:int longestPalindromeSubseq(string s) {int n s.size();vectorvectorintdp(n,vectorint(n));for(int i n-1;i0;i--)//因为有dp[i][j] dp[i1][j]的情况所以要从下到上初始化{for(int j i;jn;j)//ji{if(s[i] s[j])//第一种情况{if(ji) dp[i][j] dp[i1][j-1]2;//ji才能加2else dp[i][j] 1;//i j个数为1}else//第二种情况{dp[i][j] max(dp[i1][j],dp[i][j-1]);//不用担心越界的情况因为当j 0时//i一定等于0所以会在第一种情况中处理}}}return dp[0][n-1];}}; 二让字符串成为回文串的最小插入次数
1题目 1312. 让字符串成为回文串的最少插入次数 提示 困难 218 相关企业 给你一个字符串 s 每一次操作你都可以在字符串的任意位置插入任意字符。 请你返回让 s 成为回文串的 最少操作次数 。 「回文串」是正读和反读都相同的字符串。 示例 1 输入s zzazz
输出0
解释字符串 zzazz 已经是回文串了所以不需要做任何插入操作。示例 2 输入s mbadm
输出2
解释字符串可变为 mbdadbm 或者 mdbabdm 。示例 3 输入s leetcode
输出5
解释插入 5 个字符后字符串变为 leetcodocteel 。提示 1 s.length 500s 中所有字符都是小写字母。 2.题目接口
class Solution {
public:int minInsertions(string s) {}
};
3.解题思路及其代码 对于这种回文串问题因为有了上面的定义状态表示的经验所以还是使用一个二维的dp表解决问题。 1.状态表示dp[i][j]表示在[i,j]这个区间内使这个区间内的字符串成为回文串的最小插入次数。 2.状态转移方程在这里状态转移方程还是要分类讨论还是要看s[i]s[j]是否相等 在第二种情况下要取两者的较小值。 代码 由以上思路写出代码如下 class Solution {
public:int minInsertions(string s) {int n s.size();vectorvectorintdp(n,vectorint(n));for(int i n-1;i0;i--)//有dp[i][j] dp[i1][j]1的情况所以要从下到上遍历{for(int j i;jn;j){if(s[i] s[j]){if(ji) dp[i][j] dp[i1][j-1];//只有一个字符不用搞了}else{dp[i][j] min(dp[i1][j],dp[i][j-1])1;}}}return dp[0][n-1];}
};
