您现在的位置是:首页 >其他 >数据结构基础day9网站首页其他

数据结构基础day9

cccc楚染rrrr 2023-06-25 15:48:51
简介数据结构基础day9

题目:187. 重复的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){	//从开头遍历到最后一个长度为10的子串开头
            string temp = s.substr(i,L);
            if(++mp[temp]==2){	//当数量==2时即可加入答案序列
                ans.push_back(temp);
            }
        }
        return ans;
    }
};

解法2:哈希表+滑动窗口+位运算

好长,不想看

题目:5. 最长回文子串

解法1:暴力解法

遍历每一个子串,当其是回文子串且长度最大,存储初始位置和长度。
时间复杂度O(n^3),空间复杂度O(1)

class Solution {
public:
    bool isPalindrome(string s, int left, int right){	//判断s字符串中left到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;	//最大长度可以是一个字母
        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)){	//当子串长度大于当前最大长度,且子串为回文串
                    maxLen = j-i+1;	//更新最大长度
                    begin = i;	//更新起始位置
                }
            }
        }

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

解法2:动态规划

相当于在暴力解法的基础上空间换时间,时间复杂度O(n^2),空间复杂度O(n)
状态定义(定义子问题):一个字符串是否是回文串看去掉两头字符后的字符串是否是回文串,因此子问题定义为:dp[i][j]表示s[i,...,j]为回文子串
状态转移方程(描述子问题之间的联系)dp[i][j] = (s[i]==s[j]) && (dp[i+1][j-1]=true)
初始化:边界条件就是当子串长度为1的时候,显然是回文子串,比如,ij的一个子串在i和j位置的字符相同时,判断去掉ij位置字符后的子串长度是否是回文子串,一致判断到去掉ij位置字符后的子串长度小于2,即j-1-(i+1)+1<2 -> j-i<3
输出dp[i][j]表示ij的子串是否是回文子串,判断j-i+1是否大于maxLen,如果大于,记录maxLenbegin=i
优化空间:见解法3中心拓展法
PS:注意都是先确定起始位置和长度,最后再截取最长回文子串
在这里插入图片描述

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

        int maxLen = 1;	//最大回文子串长度
        int begin = 0;	//最大回文子串起始位置

        vector<vector<int>> dp(n, vector<int>(n));	//dp定义,true是非0数,false是0
        for(int i=0; i<n; ++i){	//初始定义,每个字符单独都是回文子串,对角线为true
            dp[i][i] = true;
        }
        for(int j=1; j<n; ++j){	//从左上角开始遍历,注意从1开始,先遍历列
            for(int i=0; i<j; ++i){	//后遍历行,到对角线(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{	//继续判断i+1到j-1的子串
                        dp[i][j] = dp[i+1][j-1];
                    }
                }
                if(dp[i][j]==true && j-i+1>maxLen){	//检查i到j子串长度是否大于maxLen
                    maxLen = j-i+1;	//更新最大回文子串长度
                    begin = i;	//更新最大回文子串初始位置
                }
            }
        }

        return s.substr(begin, maxLen);	//截取最长回文子串
    }
};

解法3:中心扩展法

时间复杂度:O(n^2),空间复杂度:O(1)
枚举中心位置的个数2(n-1),每个中心向两边扩散看是否为回文子串,偶数回文子串和奇数回文子串

class Solution {
public:
    int ExpandfromCentre(string s, int i, int j){	//从中心开始扩展,检查扩展子串是否是回文子串
        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位置的字符相同时退出循环,因此返回的回文子串的长度为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;	//最大回文子串长度
        int begin = 0;	//最大回文子串起始位置

        for(int i=0; i<n-1; ++i){	//枚举中心位置
            int oddLen = ExpandfromCentre(s, i, i);	//最大奇数回文子串长度
            int evenLen = ExpandfromCentre(s, i, i+1);	//最大偶数回文子串长度
            if(max(oddLen, evenLen) > maxLen){	//更新maxLen和begin
                maxLen = max(oddLen, evenLen);
                begin = i-(maxLen-1)/2;	//注意这里是推导出来的
            }
        }
        
        return s.substr(begin, maxLen);	//截取最长回文子串
    }
};

从i和maxLen倒推begin有点麻烦,可以选另一个写法:

class Solution {
public:
    pair<int, int> ExpandfromCentre(string s, int i, int j){	//注意函数类型是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位置的字符相同时退出循环,因此返回的回文子串的长度为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;	//最大回文子串长度
        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);	//截取最长回文子串
    }
};
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。