C++ 字符串OJ

目录

1、14. 最长公共前缀

2、 5. 最长回文子串

3、 67. 二进制求和

4、43. 字符串相乘

---

1、14. 最长公共前缀

 思路一：两两字符串进行比较，每次比较过程相同，可以添加一个函数辅助比较，查找最长公共前缀。

class Solution {
public:
    string longestCommonPrefix(vector& strs) {
        string ret = strs[0];
        for (int i = 0; i < strs.size(); i++) {
            ret = findcommon(ret, strs[i]);
        }
        return ret;
    }
    string findcommon(string& s1, string& s2) {
        int i = 0;
        while (i < min(s1.size(), s2.size()) && s1[i] == s2[i]) {
            i++;
        }
        return s1.substr(0, i);
    }
};

思路二：选取一个字符串与其他字符串逐位比较，比较过程中如果有一个字符串能遍历到最后或某个字符与当前比较的字符不相等，则该字符串为最长公共前缀。

class Solution {
public:
    string longestCommonPrefix(vector& strs) {
        for (int i = 0; i < strs[0].size(); i++) {
            char s = strs[0][i];
            for (int j = 1; j < strs.size(); j++) {
                if (i == strs[j].size() || s != strs[j][i])
                    return strs[0].substr(0, i);
            }
        }
        return strs[0];
    }
};

2、 5. 最长回文子串

 

 思路：中心扩展法

• 中心扩展法：这种方法的核心思想是，回文子串的构造是对称的，所以可以从中心开始向两边扩展，检查两边的字符是否相等。这种方法需要考虑奇数长度和偶数长度的回文子串，因此对每个字符尝试两次扩展：一次将其视为中心（奇数长度），一次将其和下一个字符共同视为中心（偶数长度）。

• 时间复杂度：由于需要对字符串中的每个字符都尝试向两边扩展，最坏情况下每次扩展可能会遍历整个字符串，因此总的时间复杂度为O(n^2)，其中n是字符串的长度。

• 空间复杂度：这个算法只使用了固定的额外空间（begin、len等变量），因此空间复杂度为O(1)。

通过这种方法，即使在字符串长度较长的情况下，也能有效地找到最长的回文子串。

class Solution {
public:
    string longestPalindrome(string s) {
        int begin = 0, len = 0, n = s.size();
        for (int i = 0; i < n; i++) {
            int left = i, right = i;
            while (left >= 0 && right < n && s[left] == s[right]) {
                left--, right++;
            }
            if (right - left - 1 > len) {
                begin = left + 1;
                len = right - left - 1;
            }
 
            left = i, right = i + 1;
            while (left >= 0 && right < n && s[left] == s[right]) {
                left--, right++;
            }
            if (right - left - 1 > len) {
                begin = left + 1;
                len = right - left - 1;
            }
        }
        return s.substr(begin, len);
    }
};

1. 首先，定义了三个变量：begin（记录最长回文子串的起始位置）、len（记录最长回文子串的长度）、n（记录字符串s的长度）。

2. 然后，通过一个循环遍历字符串s中的每个字符。在循环中，以当前字符为中心，向两边扩展，找到以当前字符为中心的最长回文子串长度。

3. 在第一个循环中，以当前字符为中心，向左右两边扩展，直到不再满足回文条件（即字符不相等或越界）。在扩展的过程中，记录下当前回文子串的起始位置和长度。

4. 接着，在第二个循环中，以当前字符和下一个字符为中心，向左右两边扩展，找到以这两个字符为中心的最长回文子串长度。

5. 在每次扩展过程中，比较当前找到的回文子串长度与之前记录的最长回文子串长度，如果当前找到的更长，则更新begin和len。

6. 最后，返回找到的最长回文子串，通过使用substr函数从原始字符串s中截取出最长回文子串。

3、 67. 二进制求和

 思路：模拟列竖式计算，注意二进制求和逢二进一。

class Solution {
public:
    string addBinary(string a, string b) {
        int cur1 = a.size() - 1, cur2 = b.size() - 1;
        string ret;
        int t = 0;
        while (cur1 >= 0 || cur2 >= 0 || t) {
            if (cur1 >= 0)
                t += a[cur1--] - '0';
            if (cur2 >= 0)
                t += b[cur2--] - '0';
            ret += t % 2 + '0';
            t /= 2;
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
};

4、43. 字符串相乘

 思路一：无进位相加，这个算法的关键在于通过逐位相乘和处理进位来实现大数乘法，避免了直接使用大数运算，使得算法能够处理非常大的数。

class Solution {
public:
    string multiply(string num1, string num2) {
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());
        int m = num1.size(), n = num2.size();
        vector<int> tmp(m + n - 1);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                tmp[i + j] += (num1[i] - '0') * (num2[j] - '0');
            }
        }
        int cur = 0, t = 0;
        string ret;
        while (cur < m + n - 1 || t) {
            if (cur < m + n - 1) {
                t += tmp[cur++];
            }
            ret += t % 10 + '0';
            t /= 10;
        }
        while (ret.size() > 1 && ret.back() == '0') {
            ret.pop_back();
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
};

 整个过程模拟了人工进行乘法计算的过程，先计算每一位的乘积然后逐步处理进位，最后得到结果。这种方法不依赖于任何大数处理库，能够处理非常大的数的乘法，只受限于内存和处理时间。

1. 反转字符串：首先，将num1和num2两个字符串反转，这样做是为了从最低位开始计算乘积，便于后续的逐位相乘和累加。

2. 初始化临时数组：创建一个长度为m + n - 1的临时数组tmp，用于存储乘积的每一位。这里m和n分别是num1和num2的长度。数组的长度之所以是m + n - 1，是因为两个数最多可以产生这么长的乘积。

3. 逐位相乘：遍历num1和num2的每一位，将每一位的乘积累加到tmp数组对应的位置上。这里使用(num1[i] - '0') * (num2[j] - '0')来计算两位数字的乘积，并累加到tmp[i + j]上。

4. 处理进位：遍历tmp数组，将每一位的值加上前一位的进位t，然后计算当前位的值（t % 10）和新的进位（t / 10）。这一步确保了每一位上的数字都是单个数字，并且正确处理了进位。

5. 去除前导零：由于最开始反转了字符串，最终得到的结果也是反转的，且可能包含前导零。因此，需要去除结果字符串尾部的所有'0'，直到结果字符串的长度大于1或者最后一个字符不是'0'。

6. 反转结果字符串：最后，将结果字符串再次反转，得到正确的乘积结果。

7. 返回结果：返回处理后的结果字符串。

思路二： 直接模拟

class Solution {
public:
    string multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0")
            return "0";
        int n1 = num1.size(), n2 = num2.size();
        string result(n1 + n2, '0');
        for (int i = n1 - 1; i >= 0; i--) {
            for (int j = n2 - 1; j >= 0; j--) {
                int product = (num1[i] - '0') * (num2[j] - '0') +
                              (result[i + j + 1] - '0');
                result[i + j + 1] = product % 10 + '0';
                result[i + j] += product / 10;
            }
        }
 
        size_t startpos = result.find_first_not_of("0");
        return result.substr(startpos);
    }
};

1. 特殊情况处理：如果num1或num2中任何一个是"0"，则乘积也是"0"，直接返回"0"。

2. 初始化结果字符串：创建一个长度为n1 + n2的字符串result，所有位初始化为'0'。这是因为两个长度分别为n1和n2的数相乘，其结果长度最多为n1 + n2。

3. 逐位相乘并累加：从num1和num2的最低位开始（即字符串的末尾），对每一对位进行乘法运算，并将乘积累加到结果字符串的相应位置。这里需要注意的是，乘积需要加上结果字符串中已经存在的数值（因为可能之前已经有累加的结果），所以使用(result[i + j + 1] - '0')来获取并更新结果。

4. 处理进位：计算每一步的乘积后，可能会产生进位。进位被加到下一位的累加结果中。这里通过result[i + j + 1] = product % 10 + '0';来更新当前位的结果，并通过result[i + j] += product / 10;来处理进位。

5. 去除前导零：由于初始化结果字符串时所有位都是'0'，乘积的计算可能会在结果字符串的前面留下一些不必要的零。使用find_first_not_of("0")找到第一个非零字符的位置，并使用substr方法截取从这个位置到字符串末尾的子串作为最终结果。

6. 返回结果：如果结果字符串中没有找到非零字符（即find_first_not_of返回string::npos），则说明结果为0；否则，返回去除前导零后的结果字符串。