字符串 （算法十一）

简介

没有固定题型，内容很杂，可以学习下string接口与相关操作

1.最长公共前缀

link：

解法一：两两比较

code

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        // 两两比较
        string ans = strs[0];
        for(int i = 1; i < strs.size(); i++)
        {
            ans = func(ans, strs[i]);
        }
        return ans;
    }

    string func(string& s1, string& s2)
    {
        for(int i = 0; ;i++)
        {
            if(i >= min(s1.size(), s2.size()) || s1[i]!=s2[i]) return {s1.begin(), s1.begin()+i};
        }
    }
};

解法二：统一比较

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        // string ans = "";
        int ans = 0;
        while(true)
        {
            for(auto& e:strs)
            {   if(e.empty()) return "";
                if(ans >= e.size() || e[ans] != strs[0][ans]) return {strs[0].begin(), strs[0].begin()+ans};
            }
            ans++;
        }
        return {strs[0].begin(), strs[0].begin()+ans};
    }
};

2.最长回文字串

link:5. 最长回文子串 - 力扣（LeetCode）

中心扩散法

code

class Solution {
public:
    string longestPalindrome(string s) {
        // 中心扩散
        int maxl = 1, bgn = 0;
        for(int i = 0; i < s.size(); i++)
        {
            // 奇数长度
            int left = i-1, right = i+1;
            while(left >= 0 && right <= s.size()-1 && s[left] == s[right])
            {
                left--;
                right++;
            }
            if(right - left - 1 > maxl)
            {
                maxl = right - left - 1;
                bgn = left+1;
            }
            // 偶数长度
            left = i;
            right = i+1;
            while(left >= 0 && right <= s.size() - 1 && s[left] == s[right])
            {
                left--;
                right++;
            }
            if(right - left - 1 > maxl)
            {
                maxl = right - left - 1;
                bgn = left + 1;
            }
        }
        return s.substr(bgn, maxl);
    }
};

3.二进制求和

link:67. 二进制求和 - 力扣（LeetCode）

思路

        模拟即可，高精度加法

code

class Solution {
public:
    string addBinary(string a, string b) {
        int p1 = a.size() - 1, p2 = b.size() - 1;
        string ans;
        for(int t = 0; t || p1 >= 0 || p2 >= 0; )
        {
            t += p1 >= 0 ? a[p1--] - '0' : 0;
            t += p2 >= 0 ? b[p2--] - '0' : 0;
            ans += t % 2 + '0';
            t /= 2;
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

4.字符串相乘

Link：43. 字符串相乘 - 力扣（LeetCode）

思路：

        高精度乘法

        无进位相乘然后相加，最后处理进位

code

class Solution {
public:
    string multiply(string num1, string num2) {
        vector<int> tmp(num1.size() + num2.size(), 0);
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());
        for(int i = 0; i < num1.size(); i++)
        {
            for(int j = 0; j < num2.size(); j++)
            {
                tmp[i + j] += (num1[i] - '0') * (num2[j] - '0');
            }
        }
        // 进位
        for(int i = 0, t = 0; i < tmp.size(); i++)
        {
            t += tmp[i];
            tmp[i] = t % 10;
            t /= 10;
        }
        // 输出
        string ans = "";
        for(int i = 0; i < tmp.size(); i++) ans = string(1, tmp[i] + '0') + ans;
        for(auto it = ans.begin(); it != ans.end(); it++)// 去前导0
        {
            if(*it != '0') return string(it, ans.end());
        }
        return "0";
    }
};