刷单做任务的网站,wordpress文章 404,现在网站开发哪个语言好,加强 网站群建设管理有点难度#xff0c;一开始想到的两种方法都不对#xff0c;花了不少时间。
先说之前的方法#xff1a;
① 遍历每个点#xff0c;每个点向外扩张#xff0c;如果左等于右就一直扩展直到不等。
这个方法可是可以#xff0c;但我没有考虑到两个相同字母也是回文串的情况…
有点难度一开始想到的两种方法都不对花了不少时间。
先说之前的方法
① 遍历每个点每个点向外扩张如果左等于右就一直扩展直到不等。
这个方法可是可以但我没有考虑到两个相同字母也是回文串的情况偶数长度的回文串所以失败了并且也没有用到考点动态规划遂放弃。
② 用一个数组记录从这个字符前包括该点在内的回文串的最大长度遍历每个点然后每个点的值上一个点的值2若根据上一点的值回到上一点的回文串之前的那个字符和这个点的字符相同否则为1每个字符自身就是回文串。
后来发现这个做法完全不行因为有些比如acccc这种计算最后一个c时由于每次只会记录最大的回文串倒数第二个c的数是3于是就会判定ca无法记录最长的回文串cccc。
所以还是得二维数组。
根据首位序号维护布尔类型的二维数组每个值记录首位字符括起来的串是否为回文串这样做状态转换方程比较难想。
自己在草稿纸上画个二维数组就好想得多。
我的方法是将palindrome[i][j]设为第i个字符到第j个字符是否是回文串包括边界i和j。
当前字符palindrome[i][j]是回文串的条件是palindrome[i-1][j1]意思是两边界缩小1位是否是回文串并且s[j]s[i]两边界自身相同。
然后palindrome[i][i]必为回文串如果s[i-1]s[i]那么palindrome[i-1][i]也为回文串。
从i1开始遍历到结束i是起始字符从ji-1开始遍历到j0j是结束字符中间字符长度要从小到大所以j要从大到小。
class Solution {
public:string longestPalindrome(string s) {vectorvectorbool palindrome(s.size(),vectorbool (s.size(),0));int result1;string res.substr(0,1);for(int i0;is.size();i){palindrome[i][i]1;for(int ji-1;j0;j--){if(ji-1s[j]s[i]) palindrome[i][j]1;if(palindrome[i-1][j1]1s[j]s[i]) palindrome[i][j]1;if(palindrome[i][j]1i-j1result){resulti-j1;res.substr(j,i-j1);}}}return re;}
};
