柳州建网站,苏州高端网页设计,百度怎么推广自己的信息,电网商城这道题我主要是通过动态规划来进行解题#xff0c;看了我好久#xff08;解析#xff09;#xff0c;生疏了呀。
首先就是判断一个字符串是不是回文#xff0c;我们可以设置两个指针#xff0c;从前往后进行判断即可#xff0c;运用暴力解题法#xff0c;这里运用的动…
这道题我主要是通过动态规划来进行解题看了我好久解析生疏了呀。
首先就是判断一个字符串是不是回文我们可以设置两个指针从前往后进行判断即可运用暴力解题法这里运用的动态规划法主要是要搞清楚原理即可。
中心思想就是先判断两端的是否相等若是则 dp[i][j] true然后是从短到长的一个过程与此同时不断更新最长子串的下标最后再返回代码里面有详细的解释。
class Solution {
public:string longestPalindrome(string s) {// 1.动态规划很有意思int ns.size();if(n2) return s; //长度为1时直接返回即可// maxLen和begin的作用在于存满足条件的字符串的上限和下限用于最后结果的截取int maxLen1,begin0;// dp[i][j] 表示 s[i..j] 是否是回文串vectorvectorint dp(n,vectorint(n));for(int i0;in;i) dp[i][i]true;// L表示子串长度for(int L2;Ln;L){// i表示能确定左边界for(int i0; in;i){//j为右边界int jiL-1;if(jn) break; // 越界 跳//左右边界值相等且在长度if(s[i] ! s[j]){dp[i][j]false;}else{//当满足条件的子串的长度小于等于3时此时的j-i是2的所以可以以此来进行判断if(j-i3 ){dp[i][j]true;}else{dp[i][j]dp[i1][j-1];}}//最后进行判断,并更新下标的值最后进行返回即可if(dp[i][j]j-i1maxLen){maxLenj-i1;begini;}}}return s.substr(begin,maxLen);}
}; 龙年快乐哦~
