一、最长回文串
二、题目理解
1、按照示例理解,遍历字符串,找到下一个与之相同的位置,存储在新字符串里面,输出即可!但是这个相同位置不好找!两重循环过于麻烦!
2、观察回文串的特点:两边对称相等。那就考虑二分法!!!
二分法,判断,左边的内容是否与右边的内容相同!!
class Solution {
public:
string longestPalindrome(string s) {
//if(s.empty()) return ;
int len = s.size();
int l = 0 ; int r = len-1;
while(l<r){
int m = (l+r)/2;
if(s[l] == s[r]){
return s.substr(l, r);
}
else if(s[l]<s[r]){
l = m+1;
}
else{
r = m+1;
}
}
return s;
}
};
借鉴大神思路,重新写一遍!!!
class Solution {
public:
bool checkPalindrom(string& s, int i, int j){// 二分法,判断左右数值是否相等
// i = 0;
//j = s.size()-1
if(j>s.size()) return false;
bool change = true;
while(i<j){
if(s[i] != s[j]){
return change = false;
}
i++;
j--;
}
return change;
}
string longestPalindrome(string s) {
if(s.empty() || s.size() < 2)
return s;
int len = s.size();
int l=0, r=len;
string news; // 这个一定不能省略,因为要进行下一次的遍历的时候,存储十分重要!!!之前直接return 所有结果,悲剧了!!!
while(l<=r){
int m = (l+r)/2;
bool change = false;
for(int i=0; i<len-m; i++){
if(checkPalindrom(s, i, i+m-1)){
change = true;
news = s.substr(i, m);
break;
}
}
for(int i=0; i<len-m; i++){
if(checkPalindrom(s, i, i+(m+1)-1)){
change = true;
news = s.substr(i, m+1);
break;
}
}
if(!change){
r = m -1;
}
else{
l = m + 1;
}
}
return news;
}
};
三、题目解答
1、二分法
可以理解,将判断单独写一个函数。之后在遍历时,直接调用判断是否左右相等,等的话,直接返回即可~
不明白为啥一定要有两个遍历, mid,mid+1 无法理解其中意思!!!
为了判断奇数与偶数,写两次循环判断!!!