題目：187. 重復(fù)的DNA序列

解法1：哈希表

class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        vector<string> ans;
        unordered_map<string, int> mp;
        int n=s.size(), L=10;
        for(int i=0; i<=n-L; ++i){	//從開頭遍歷到最后一個(gè)長(zhǎng)度為10的子串開頭
            string temp = s.substr(i,L);
            if(++mp[temp]==2){	//當(dāng)數(shù)量==2時(shí)即可加入答案序列
                ans.push_back(temp);
            }
        }
        return ans;
    }
};

解法2：哈希表+滑動(dòng)窗口+位運(yùn)算

好長(zhǎng)，不想看

題目：5. 最長(zhǎng)回文子串

解法1：暴力解法

遍歷每一個(gè)子串，當(dāng)其是回文子串且長(zhǎng)度最大，存儲(chǔ)初始位置和長(zhǎng)度。
時(shí)間復(fù)雜度O(n^3)，空間復(fù)雜度O(1)

class Solution {
public:
    bool isPalindrome(string s, int left, int right){	//判斷s字符串中l(wèi)eft到right位置的子串是否為回文串
        while(left<right){
            if(s[left] != s[right]) return false;
            ++left; --right;
        }
        return true;
    }

    string longestPalindrome(string s) {
        int n = s.size();
        if(n<2) return s;	//特判

        int maxLen = 1;	//最大長(zhǎng)度可以是一個(gè)字母
        int begin = 0;	//初始位置

        for(int i=0; i<n-1; ++i){	//遍歷頭，注意遍歷到n-1
            for(int j=i+1; j<n; ++j){	//遍歷從i開始的子串的尾，
                if(j-i+1>maxLen && isPalindrome(s, i, j)){	//當(dāng)子串長(zhǎng)度大于當(dāng)前最大長(zhǎng)度，且子串為回文串
                    maxLen = j-i+1;	//更新最大長(zhǎng)度
                    begin = i;	//更新起始位置
                }
            }
        }

        return s.substr(begin, maxLen);	//返回s的最大長(zhǎng)度回文子串
    }
};

解法2：動(dòng)態(tài)規(guī)劃

相當(dāng)于在暴力解法的基礎(chǔ)上空間換時(shí)間，時(shí)間復(fù)雜度O(n^2)，空間復(fù)雜度O(n)
狀態(tài)定義（定義子問題）：一個(gè)字符串是否是回文串看去掉兩頭字符后的字符串是否是回文串，因此子問題定義為：dp[i][j]表示s[i,...,j]為回文子串
狀態(tài)轉(zhuǎn)移方程（描述子問題之間的聯(lián)系）：dp[i][j] = (s[i]==s[j]) && (dp[i+1][j-1]=true)
初始化：邊界條件就是當(dāng)子串長(zhǎng)度為1的時(shí)候，顯然是回文子串，比如，i到j的一個(gè)子串在i和j位置的字符相同時(shí)，判斷去掉i和j位置字符后的子串長(zhǎng)度是否是回文子串，一致判斷到去掉i和j位置字符后的子串長(zhǎng)度小于2，即j-1-(i+1)+1<2 -> j-i<3
輸出：dp[i][j]表示i到j的子串是否是回文子串，判斷j-i+1是否大于maxLen，如果大于，記錄maxLen和begin=i
優(yōu)化空間：見解法3中心拓展法
PS：注意都是先確定起始位置和長(zhǎng)度，最后再截取最長(zhǎng)回文子串

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        if(n<2) return s;	//特判

        int maxLen = 1;	//最大回文子串長(zhǎng)度
        int begin = 0;	//最大回文子串起始位置

        vector<vector<int>> dp(n, vector<int>(n));	//dp定義，true是非0數(shù)，false是0
        for(int i=0; i<n; ++i){	//初始定義，每個(gè)字符單獨(dú)都是回文子串，對(duì)角線為true
            dp[i][i] = true;
        }
        for(int j=1; j<n; ++j){	//從左上角開始遍歷，注意從1開始，先遍歷列
            for(int i=0; i<j; ++i){	//后遍歷行，到對(duì)角線（j）為止
                if(s[i]!=s[j]) dp[i][j]=false;	//如果i和j位置的字符不相同，則直接false
                else{	//i和j位置字符相同
                    if(j-i<3){  //邊界：j-1-(i+1)+1<2 -> j-i<3
                        dp[i][j] = true;
                    }else{	//繼續(xù)判斷i+1到j(luò)-1的子串
                        dp[i][j] = dp[i+1][j-1];
                    }
                }
                if(dp[i][j]==true && j-i+1>maxLen){	//檢查i到j(luò)子串長(zhǎng)度是否大于maxLen
                    maxLen = j-i+1;	//更新最大回文子串長(zhǎng)度
                    begin = i;	//更新最大回文子串初始位置
                }
            }
        }

        return s.substr(begin, maxLen);	//截取最長(zhǎng)回文子串
    }
};

解法3：中心擴(kuò)展法

時(shí)間復(fù)雜度：O(n^2)，空間復(fù)雜度：O(1)
枚舉中心位置的個(gè)數(shù)2(n-1)，每個(gè)中心向兩邊擴(kuò)散看是否為回文子串，偶數(shù)回文子串和奇數(shù)回文子串

class Solution {
public:
    int ExpandfromCentre(string s, int i, int j){	//從中心開始擴(kuò)展，檢查擴(kuò)展子串是否是回文子串
        int n = s.size();
        int left = i, right = j;
        while(left>=0 && right<n){
            if(s[left]==s[right]){
                --left;
                ++right;
            }else{
                break;
            }
        }   //不符合i和j位置的字符相同時(shí)退出循環(huán)，因此返回的回文子串的長(zhǎng)度為j-1-(i+1)+1=j-i-1，這里是left和right?。?！
        return right-left-1;
    }

    string longestPalindrome(string s) {
        int n = s.size();
        if(n<2) return s;	//特判

        int maxLen = 1;	//最大回文子串長(zhǎng)度
        int begin = 0;	//最大回文子串起始位置

        for(int i=0; i<n-1; ++i){	//枚舉中心位置
            int oddLen = ExpandfromCentre(s, i, i);	//最大奇數(shù)回文子串長(zhǎng)度
            int evenLen = ExpandfromCentre(s, i, i+1);	//最大偶數(shù)回文子串長(zhǎng)度
            if(max(oddLen, evenLen) > maxLen){	//更新maxLen和begin
                maxLen = max(oddLen, evenLen);
                begin = i-(maxLen-1)/2;	//注意這里是推導(dǎo)出來(lái)的
            }
        }
        
        return s.substr(begin, maxLen);	//截取最長(zhǎng)回文子串
    }
};

從i和maxLen倒推begin有點(diǎn)麻煩，可以選另一個(gè)寫法：文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-672305.html

class Solution {
public:
    pair<int, int> ExpandfromCentre(string s, int i, int j){	//注意函數(shù)類型是pair
        int n = s.size();
        int left = i, right = j;
        while(left>=0 && right<n){
            if(s[left]==s[right]){
                --left;
                ++right;
            }else{
                break;
            }
        }   //不符合i和j位置的字符相同時(shí)退出循環(huán)，因此返回的回文子串的長(zhǎng)度為j-1-(i+1)+1=j-i-1，這里是left和right！??！
        return {left+1, right-1};	//注意返回值和{}
    }

    string longestPalindrome(string s) {
        int n = s.size();
        if(n<2) return s;	//特判

        int maxLen = 1;	//最大回文子串長(zhǎng)度
        int begin = 0;	//最大回文子串起始位置

        for(int i=0; i<n-1; ++i){
            auto [odd_l, odd_r] = ExpandfromCentre(s, i, i);	//注意加[]
            auto [even_l, even_r] = ExpandfromCentre(s, i, i+1);
            if(odd_r-odd_l+1 > maxLen){
                maxLen = odd_r-odd_l+1;
                begin = odd_l;
            }
            if(even_r-even_l+1 > maxLen){
                maxLen = even_r-even_l+1;
                begin = even_l;
            }
        }
        
        return s.substr(begin, maxLen);	//截取最長(zhǎng)回文子串
    }
};

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)day9的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！