字符串总结_牛客博客

陆续更新字符串题目

1、最长回文子串

暴力解题法

class Solution {
public:
    string longestPalindrome(string s) {
        string res="";//存放结果
        string temp="";//存放子串
        for(int i=0;i<s.length();i++)
        {
            for(int j=i;j<s.length();j++)
            {
                temp=temp+s[j];
                string tem=temp;//tem存放子串反转结果
                std::reverse(tem.begin(),tem.end());//反转
                if(temp==tem)
                    res=res.length()>temp.length()?res:temp;
            }
            temp="";
        }
        return res;
    }
};

中心扩展法

我们观察到回文中心的两侧互为镜像。因此，回文可以从它的中心展开，并且只有 2n - 1 个这样的中心。因为回文的中心要区分单双。

假如回文的中心为双数，例如 abba，那么可以划分为 ab bb ba，对于n长度的字符串，这样的划分有 n-1 种。

假为回文的中心为单数，例如 abcd, 那么可以划分为 a b c d，对于n长度的字符串，这样的划分有 n 种。

class Solution {
public:
    string longestPalindrome(string s)            
    {
        if (s.length() < 1)
        {
            return "";
        }
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++)
        {
            int len1 = expandAroundCenter(s, i, i);//一个元素为中心
            int len2 = expandAroundCenter(s, i, i + 1);//两个元素为中心
            int len = max(len1, len2);
            if (len > end - start)
            {
                start = i - (len - 1) / 2;
            //对称个数是偶数个的时候，start离i近，如abba ->0123 ->  1-3/2=0
                end = i + len / 2;
            }
        }
        return s.substr(start, end - start + 1);
    }

    int expandAroundCenter(string& s, int left, int right)
    {
        int L = left, R = right;
        while (L >= 0 && R < s.length() && s[L] == s[R])
        {// 计算以left和right为中心的回文串长度
            L--;
            R++;
        }
        return R - L - 1;
    }    
};

2、重复的DNA序列

所有 DNA 都由一系列缩写为 A，C，G 和 T 的核苷酸组成，例如：“ACGAATTCCG”。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。

编写一个函数来查找目标子串，目标子串的长度为 10，且在 DNA 字符串 s 中出现次数超过一次。

首先要理解题目，题目的意思是编写一个函数来查找子串，这个子串长度为10，在原字符串中出现超过一次。

思路：用哈希表关联方式，从头以长度10遍历字符串，然后放进哈希表里，如果有相同的就加1，最后输出大于一的就好。

class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        int n =10;
        vector<string> res;
        if(s.size() < 10)
            return res; 
        map<string , int> m;
        for(int i = 0 ; i <= s.size() - n;i++)
        {
            m[s.substr(i,n)]++;
        }
        for(auto p:m)
        {
            if(p.second > 1)
                res.push_back(p.first);
        }
        return res;

    }
};

3. 无重复字符的最长子串

思路：采用滑窗法，并用map记录字符出现的位置，记录最大值。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.empty())
            return 0;
        map<char,int> m;
        int res = 0,left = 0; // 由于map不能初始化，所以默认为0
        for(int i=0;i<s.size();++i)
        {
            left = max(left,m[s[i]]);
            m[s[i]] = i+1; //此处记录的是第几个的位置
            res = max(res,i-left+1);//上面加1了，此处就要-1；
        }
        return res;
    }
};

4、替换空格

用到之前总结的双指针法，注意string需要扩容。

class Solution {
public:
    string replaceSpace(string s) {
        //length属性:用于获取数组长度。
        //length属性:用于获取数组长度。
        //size()方法：用于获取泛型集合有多少个元素。
        int orginalLength = s.size() - 1;
        int numberOfBlank =0;
        for (auto c : s){
            if (c == ' ') ++numberOfBlank;
        }

        int newLength = orginalLength + numberOfBlank * 2;
        s += string(numberOfBlank * 2,' ');//扩容
        int indexOriginal = orginalLength;
        int indexNew = newLength;
        for(int i = orginalLength , j=newLength ;i<j ; i--)
        {
            if(s[i] == ' ')
                {
                    s[j--] = '0';
                    s[j--] = '2';
                    s[j--] = '%';
                }
            else
            {
                s[j--] =s[i];
            }
        }
        return s;
    }
};

5、字符串排列

输入一个字符串，打印出该字符串中字符的所有排列。

class Solution {
public:
    vector<string> Permutation(string str)
    {
        vector<string> result;
        if(str.empty()) return result;

        Permutation(str,result,0);

        // 此时得到的result中排列并不是字典顺序，可以单独再排下序
        sort(result.begin(),result.end());

        return result;
    }

    void Permutation(string str,vector<string> &result,int begin)
    {
        if(begin == str.size()-1) // 递归结束条件：索引已经指向str最后一个元素时
        {
            if(find(result.begin(),result.end(),str) == result.end())
            {
                // 如果result中不存在str，才添加；避免aa和aa重复添加的情况
                result.push_back(str);
            }
        }
        else
        {
            // 第一次循环i与begin相等，相当于第一个位置自身交换，关键在于之后的循环，
            // 之后i != begin，则会交换两个不同位置上的字符，直到begin==str.size()-1，进行输出；
            for(int i=begin;i<str.size();++i)
            {
                swap(str[i],str[begin]);
                Permutation(str,result,begin+1);
                swap(str[i],str[begin]); // 复位，用以恢复之前字符串顺序，达到第一位依次跟其他位交换的目的
            }
        }
    }

    void swap(char &fir,char &sec)
    {
        char temp = fir;
        fir = sec;
        sec = temp;
    }
};

字符串总结

1、 最长回文子串