字符串题目

字符串

1、string数组的最长公共前缀

https://leetcode-cn.com/problems/longest-common-prefix/comments/

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string res = strs[0];

        for(int i=1; i<strs.size(); i++)
        {
            for(int j=0; j<res.size();j++)
            {
                if(res[j] != strs[i][j])
                {
                    res = res.substr(0,j);
                    break;
                }
            }
        }
        return res;
    }
};

2、求字符串中不含重复字符的最长字串

https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.length()<=1) return s.length();

        int res = -1, right = 0;
        unordered_set<char> store;

        for(int left=0; left<s.length();left++)
        {
            while(right < s.length() && !store.count(s[right]))
            {
                store.insert(s[right]);
                right++;
            }

            res = max(res,right - left);
            store.erase(s[left]);

            if(right>=s.length()) break;
        }
        return res;
    }
};

3、完美子串的个数

参考：https://blog.csdn.net/qq_44745063/article/details/114627854

vector<string> GetPerfectStr(string& s)
{
    int len = s.size();//记录字符串长度
    vector<string> res;//用来储存结果
    vector<vector<string>> dp(len + 1, vector<string>(len + 1));//实现动归的数组
    map<char,int> mp;//用map的去重来统计包含字符
    for (auto str : s)
    {
        mp[str]++;
    }
    string countstr = "";
    for (auto c : mp)
    {
        countstr+=c.first;
    }//到此，统计字符结束

    //初始化
    for (int i = 0; i < len + 1; i++)
    {
        for (int j = 0; j <= i; j++)
        {
            dp[i][j] = countstr;
        }
    }

    for (int i = 0; i < len + 1; i++)
    {
        for (int j = 1; j < len + 1; j++)
        {
            int pos = dp[i][j - 1].find(s[i]);
            if (pos != string::npos)
            {
                dp[i][j] = dp[i][j - 1].erase(pos, 1);
            }
            else
                dp[i][j] = dp[i][j - 1];
            if (dp[i][j] == "")
            {
                res.push_back(s.substr(i, j));
            }
        }
    }
    return res;
}

4、删除s1中所有S2中的字符

#include<iostream>
#include<set>
#include<string.h>

using namespace std;



void re_str_delete(string& a, string& b)
{
    set<char> temp;
    for (auto s : b)
    {
        temp.insert(s);
    }

    int i = 0;
    while (a[i]!= '\0')
    {

        while(temp.find(a[i]) != temp.end())
        {
            a.erase(a.begin()+i);
        }
        i++;
    }
}



int main()
{
    string a = "abcdefghdijabklcmn";
    string b = "abcdef";

    re_str_delete(a, b);

    for (int i = 0; i < a.size(); ++i)
    {
        cout << a[i];
    }
    cout << endl;

    system("pause");
    return 0;
}

5、最长回文子串

动态规划

class Solution {
public:
    int getLongestPalindrome(string A, int n) {
        // write code here
        if(n < 2 ) return n;

        vector<vector<bool>> dp(n,vector<bool>(n));

        int maxLen = 0;

        for(int i=0; i<n; i++)
        {
            dp[i][i] = 1;
        }

        for(int L=2; L<=n; L++)
        {
            for(int i=0; i<n; i++)
            {
                int j = L + i - 1;

                if(j >=n) break;

                if(A[i] != A[j]) dp[i][j] = false;
                else{
                    if(j - i < 3) dp[i][j] =true;
                    else{
                        dp[i][j] = dp[i+1][j-1];
                    }
                }
                if(dp[i][j] == true && j - i + 1 > maxLen)
                {
                    maxLen = j - i + 1;
                }
            }
        }
        return maxLen;
    }
};

6、最长递增子序列

动态规划+二分
上面的动态规划算法需要向前遍历找到前一个k，导致算法复杂度为O(nn)，一个牛逼的想法是使用二分查找优化，使复杂度降低为O(nlogn)。
基本点在于维护一个数组maxEnd，其元素maxEnd[k]表示长度为k+1的递增长子序列的最后一个元素，并且是字典序最小的那个。显然maxEnd是一个递增数组。
1 如果arr[i] > maxEnd.back()时，显然直接..., maxEnd.back(), arr[i]依然是一个递增子序列。
2 问题是arr[i] <= maxEnd.back()时怎么处理？
我们找到maxEnd中大于等于arr[i]的元素位置k，将maxEnd[k]替换为arr[i]，这表示将长度为k+1的子序列的最后一个元素更新为更小的值。显然更合理。然后再同步更新dp[k]值的为i。

class Solution {
public:
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型vector the array
     * @return int整型vector
     */
    vector<int> LIS(vector<int>& nums) {
        // write code here
        if (nums.size() <= 1)
            return nums;
        vector<int> dp(nums.size(), 0);
        vector<int> pos(nums.size(), 0);//pos[i]=j用来记录nums[i]在dp中的第j个位置
        int len = 0;
        dp[len] = nums[0];
        for (int i = 1; i < nums.size(); ++i) {
            if (nums[i] > dp[len]) {
                dp[++len] = nums[i];
                pos[i] = len;
            }
            else {
                int low = 0, high = len;
                while (low <= high) {
                    int mid = (low + high) >> 1;
                    if (dp[mid] < nums[i])
                        low = mid + 1;
                    else 
                        high = mid - 1;
                }
                if (low != -1) { 
                    dp[low] = nums[i];  
                    pos[i] = low; 
                }
                else { 
                    dp[0] = nums[i]; 
                    pos[i] = 0; 
                }
            }
        }
        vector<int> res(len + 1, INT_MAX);
        for (int i = nums.size() - 1; i >= 0; i--) {
            if (pos[i] == len) {
                res[len] = min(res[len], nums[i]);
                len--;
            }
        }
        return res;
    }
};