LeetCode: 字符串 --- 最长回文串

一、最长回文串

LeetCode: 字符串 --- 最长回文串

二、题目理解

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 无法理解其中意思!!!

为了判断奇数与偶数,写两次循环判断!!!

2、官方解答

上一篇:关于整型指针作为函数的形参


下一篇:Vue + Element-ui的下拉框el-select获取额外参数详解