字符串

实现 strStr()

实现:

class Solution {
public:
    int strStr(string haystack, string needle) {
        if (needle.size() == 0) return 0;
        buildNext(needle);
        // 指向主串
        int n = haystack.size(), i = 0;
        // 指向模式串
        int m = needle.size(), j = 0;
        while (i < n && j < m) {
            // j < 0 说明 j==-1要从头开始匹配了
            if (j < 0 || haystack[i] == needle[j]) {
                i++;
                j++;
            } else {
                // haystack[i] 和 needle[j]不匹配，要从模式串下标为next[j]的继续匹配，也就是最长公共前缀后缀的长度
                j = next[j];
            }
        }
        // 如果j == m证明模式串匹配完毕，在主串中找到了模式串，范围模式串在主串中出现的第一个下标，i - j
        if (j == m) {
            return i - j;
        }
        return -1;
    }
private:
    vector<int> next;
    void buildNext(string s) { 
        int m = s.size(), j = 0;
        int t = -1;
        next.resize(m);
        // 因为第一个字母没有前缀，所以next[0] = -1
        next[0] = t;
        while (j < m - 1) {
            // t < 0 也就是 t == -1,要从模式串的第一位开始匹配，然后主串也要向后移一下
            if (t < 0 || s[j] == s[t]) {
                j++;
                t++;
                next[j] = t;
            } else {
                t = next[t];
            }
        }
    }
};

最长公共前缀

最长回文子串

解题思路:
采用动态规划
实现:

class Solution {
public:
    string longestPalindrome(string s) {
        int len = s.size();
        if (len < 2) return s;
        int maxLen = 1;
        int begin = 0;
        vector<vector<int>> dp(len, vector<int>(len));
        // 所有长度为1的子串都是回文串
        for (int i = 0; i < len; i++) dp[i][i] = true;

        // 开始递推
        for (int L = 2; L <= len; L++)
        {
            for(int i = 0; i < len; i++)
            {
                int j = L + i - 1;  // 右边界
                //越界处理
                if (j >= len) break;

                if(s[i] != s[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] && L > maxLen)
                {
                    maxLen = L;
                    begin = i;
                }
            }
        }
        return s.substr(begin, maxLen);
    }
};

验证回文串

实现:

class Solution {
public:
    bool isPalindrome(string s) {
        string res;
        for (char c : s)
        {
            if (isalnum(c))
            {
                res += c;
            }
        }
        string rres(res.rbegin(), res.rend());
        return res == rres;
    }
};

字符串相加(大数求和)

解题思路:

• 大数相加, 使用long long 无法表示, 因此要使用字符串相加
• 每一位计算, 并考虑进位
• carry = sum / 10每次对应位相加后, 计算进位值

实现:

class Solution {
public:
    string addStrings(string num1, string num2) {
        string res = "";
        int i  = num1.size() - 1, j = num2.size() - 1, carry = 0;
        while (i >= 0 || j >= 0)
        {
            int n1 = i >= 0 ? num1[i] - '0' : 0;
            int n2 = j >= 0 ? num2[j] - '0' : 0;
            int tmp = n1 + n2 + carry;
            carry = tmp / 10;
            res += to_string(tmp % 10);
            i--, j--;
        }
        if (carry == 1)
        {
            res += '1';
        }
        /// 由于是倒序相加, 需要反转
        reverse(res.begin(), res.end());
        return res;
    }
};