C++之string题目练习

一.字符串相加

leetcode题目链接：https://leetcode.cn/problems/add-strings/description/

一.解题思路：模拟竖式加法

我们可以借鉴小学学习的竖式加法思路，从低位到高位逐位相加，并处理进位问题。具体步骤如下：

1. 初始化指针和进位
   定义两个指针 l1 和 l2，分别指向 num1 和 num2 的末尾（即最低位）。
   定义变量 tmp 表示当前位的进位（初始为 0）。
2. 逐位相加
   循环处理每一位的加法，直到两个字符串都遍历完毕：
   取出当前位的数字（字符转数字：char - ‘0’），与进位 tmp 相加。
   计算当前位的结果：和对 10 取余（得到当前位数值）。
   更新进位：和除以 10（得到进位值）。
   将当前位结果转换为字符，存入结果字符串。
3. 处理剩余高位
   若其中一个字符串先遍历完毕，继续处理另一个字符串的剩余高位，每次处理时仍需加上当前进位。
4. 处理最后进位
   若所有位处理完毕后仍有进位（tmp > 0），需将进位作为最高位添加到结果中。
5. 反转结果
   由于我们是从低位到高位逐位计算的，结果字符串是逆序的，最后需要反转得到正确顺序。

二.代码实现（C++）

cpp
class Solution {
public:
    string addStrings(string num1, string num2) {
        int l1 = num1.size() - 1;  // 指向num1的最低位
        int l2 = num2.size() - 1;  // 指向num2的最低位
        string ret;               // 存储结果（逆序）
        int tmp = 0;              // 进位

        // 处理两数长度相同的部分
        while (l1 >= 0 && l2 >= 0) {
            // 计算当前位之和（包含进位）
            tmp += (num1[l1] - '0') + (num2[l2] - '0');
            // 存储当前位结果（取余）
            ret.push_back(tmp % 10 + '0');
            // 更新进位（除以10）
            tmp = tmp / 10;
            l1--;
            l2--;
        }

        // 处理num1剩余高位
        while (l1 >= 0) {
            tmp += (num1[l1] - '0');
            ret.push_back(tmp % 10 + '0');
            tmp = tmp / 10;
            l1--;
        }

        // 处理num2剩余高位
        while (l2 >= 0) {
            tmp += (num2[l2] - '0');
            ret.push_back(tmp % 10 + '0');
            tmp = tmp / 10;
            l2--;
        }

        // 处理最后的进位
        if (tmp != 0) {
            ret.push_back(tmp + '0');
        }

        // 反转结果，得到正确顺序
        reverse(ret.begin(), ret.end());
        return ret;
    }
};

三.代码优化与细节说明

1. 进位处理的简化
   原代码中对进位的处理稍显繁琐（先判断是否大于 9，再拆分结果和进位）。优化后的代码通过 取余运算 和 除法运算 直接计算当前位结果和进位，逻辑更简洁：
   tmp % 10：得到当前位数值（如和为 13，当前位为 3）。
   tmp / 10：得到进位值（如和为 13，进位为 1）。
2. 结果字符串的逆序存储
   从低位到高位计算时，结果会先存储低位（如计算 123 + 456 时，先存 9，再存 7，最后存 5）。因此需要在最后反转字符串，得到正确顺序 579。
3. 边界情况处理
   长度不同的字符串：通过两个独立的循环处理剩余高位，确保所有位都被计算。
   最高位进位：如 999 + 1，计算完所有位后进位为 1，需添加到结果中，得到 1000。

四.复杂度分析

时间复杂度：O (max (N, M))，其中 N 和 M 分别为两个字符串的长度。需要遍历每个字符一次。
空间复杂度：O (max (N, M))，结果字符串最多存储 max (N, M) + 1 个字符（考虑进位）。

二.把字符串转换为整数

leetcode题目链接：https://leetcode.cn/problems/ba-zi-fu-chuan-zhuan-huan-cheng-zheng-shu-lcof/description/

从代码到理解：深入解析字符串转整数的实现

在编程中，字符串与整数的转换是一个常见的任务。今天，我们来深入探讨一个经典的算法问题：如何将一个字符串转换为整数。我们将通过分析一个具体的代码实现，来理解其中的关键点和技巧。

问题背景

将字符串转换为整数是一个看似简单，但实则充满细节的任务。我们需要处理各种情况，比如字符串中的空格、正负号、非数字字符等。此外，还需要考虑整数溢出的问题。在 C++ 中，atoi 函数可以实现这一功能，但今天我们通过手动实现一个类似的函数，来加深对这一问题的理解。

代码解析

以下是一个实现字符串转整数的 C++ 代码示例：

class Solution {
public:
    int myAtoi(string str) {
        int sign = 1; // 符号标志，1 表示正数，-1 表示负数
        int i = 0;    // 遍历字符串的索引
        int n = str.size(); // 字符串的长度
        int ret = 0;   // 最终结果

        // 跳过字符串开头的空格
        while( i < n && str[i] == ' ')
        {
            i++;
        }

        // 处理正负号
        if(i < n && str[i] == '-')
        {
            sign = -1;
            i++;
        }
        else if (i < n && str[i] == '+') {
            i++;
        }

        // 遍历字符串中的数字部分
        for(;i<n;i++)
        {
            if(str[i] >= '0' && str[i] <= '9')
            {
                // 检查是否会发生整数溢出
                if (ret > INT_MAX / 10 || 
                    (ret == INT_MAX / 10 && (str[i] - '0') > INT_MAX % 10)) {
                    return sign == 1 ? INT_MAX : INT_MIN;
                }
                ret = ret*10+(str[i] - '0');
            }
            else{
                // 遇到非数字字符，停止转换
                break;
            }
        }
        return sign*ret;
    }
};

1. 跳过空格

在字符串的开头，可能会有一些空格字符。我们需要跳过这些空格，以便从第一个非空格字符开始处理。代码中通过以下循环实现：

while( i < n && str[i] == ' ')
{
    i++;
}

2. 处理正负号

字符串中的数字可能带有正负号。我们需要判断正负号，并更新符号标志 sign。代码中通过以下逻辑处理：

if(i < n && str[i] == '-')
{
    sign = -1;
    i++;
}
else if (i < n && str[i] == '+') {
    i++;
}

如果字符串以 '-' 开头，将符号标志设置为 -1，并跳过该字符；如果以 '+' 开头，则跳过该字符，符号标志保持为 1。

3. 转换数字部分

接下来，我们需要将字符串中的数字字符转换为整数。代码中通过以下循环实现：

for(;i<n;i++)
{
    if(str[i] >= '0' && str[i] <= '9')
    {
        // 检查是否会发生整数溢出
        if (ret > INT_MAX / 10 || 
            (ret == INT_MAX / 10 && (str[i] - '0') > INT_MAX % 10)) {
            return sign == 1 ? INT_MAX : INT_MIN;
        }
        ret = ret*10+(str[i] - '0');
    }
    else{
        // 遇到非数字字符，停止转换
        break;
    }
}

关键点：整数溢出检查

在将字符转换为数字时，我们需要特别注意整数溢出的问题。INT_MAX 是 C++ 中表示最大整数的常量，如果当前结果 ret 超过了 INT_MAX / 10，或者等于 INT_MAX / 10 但下一位数字大于 INT_MAX % 10，则会发生溢出。

• 如果符号为正，直接返回 INT_MAX。
• 如果符号为负，返回 INT_MIN。
• 溢出情况实例：

输入："9223372036854775808"

输出：2147483647（INT_MAX）

解析：数字超出了 int 类型的范围，返回 INT_MAX。

4. 返回结果

最后，根据符号标志 sign，返回最终结果：

return sign*ret;

三.反转字符串中的单词

leetcode题目链接：https://leetcode.cn/problems/reverse-words-in-a-string-iii/description/

问题背景

给定一个字符串 s，其中包含若干单词，单词之间由空格分隔。我们的目标是将字符串中的单词顺序反转，但单词内部的字符顺序保持不变。例如，输入字符串 "Hello World"，反转后的结果应为 "World Hello"。

解题思路

要解决这个问题，我们可以采用两步策略：

1. 反转整个字符串：首先将整个字符串反转，这样单词的顺序会被颠倒，但单词内部的字符顺序也会被颠倒。
2. 反转每个单词：接着，我们需要将每个单词内部的字符顺序重新反转回来，以恢复单词的原始顺序。

然而，上述方法虽然直观，但实现起来可能会比较复杂。我们可以通过另一种更简洁的方式实现目标：直接在原字符串上操作，逐个反转单词。这就是我们今天要介绍的代码实现的核心思想。

代码实现

以下是用 C++ 实现的代码：

class Solution {
public:
    string reverseWords(string s) {
        int n = s.size();
        int start = 0;
        for (int i = 0; i <= n; i++) {
            if (s[i] == ' ' || i == n) {
                reverse(s.begin() + start, s.begin() + i);
                start = i + 1;
            }
        }
        return s;
    }
};

代码解析

1. 初始化变量：

   • n 是字符串的长度。
   • start 用于记录当前单词的起始位置。

2. 遍历字符串：

   • 使用一个循环从头到尾遍历字符串，包括字符串的末尾（通过 i <= n 条件）。
   • 检查当前字符是否为空格（s[i] == ' '）或是否到达字符串末尾（i == n）。

3. 反转单词：

   • 每当遇到空格或字符串末尾时，说明找到了一个单词的结束位置。
   • 使用 reverse 函数反转从 start 到当前结束位置的子字符串（即单词）。
   • 更新 start 为下一个单词的起始位置（即当前结束位置的下一个字符）。

4. 返回结果：

   • 遍历完成后，整个字符串中的单词顺序已经被反转，直接返回结果即可。

四.反转字符串

leetcode题目链接：https://leetcode.cn/problems/reverse-string-ii/

问题背景

给定一个字符串 s 和一个正整数 k，我们需要对字符串进行如下操作：每 k 个字符反转一次，但反转的范围仅限于每一段长度为 k 的子字符串。如果最后一段不足 k 个字符，则将剩余部分全部反转。例如，对于字符串 "abcdefg" 和 k = 2，反转后的结果应为 "bacdfeg"。

解题思路

这个问题可以通过分段处理来解决。具体步骤如下：

1. 特殊情况处理：

   • 如果字符串长度小于 k，直接反转整个字符串。
   • 如果字符串长度在 [k, 2k) 之间，反转前 k 个字符，剩余部分保持不变。

2. 分段反转：

   • 对于长度大于等于 2k 的字符串，每 2k 个字符为一组，反转每组的前 k 个字符。
   • 遍历字符串，当遍历到每 2k 个字符的结尾时，反转当前组的前 k 个字符。

3. 处理剩余部分：

   • 如果字符串的长度不是 2k 的整数倍，最后一段不足 k 个字符的部分需要单独反转。

代码实现

以下是用 C++ 实现的代码：

class Solution {
public:
    string reverseStr(string s, int k) {
        int num = s.size();
        int begin = 0;

        // 特殊情况处理
        if (num < k) {
            reverse(s.begin(), s.end());
            return s;
        }
        if (num >= k && num < 2 * k) {
            reverse(s.begin(), s.begin() + k);
            return s;
        }

        // 分段反转
        for (int i = 1; i <= num; i++) {
            if (i % (2 * k) == 0) {
                reverse(s.begin() + begin, s.begin() + begin + k);
                begin = i;
            }
        }

        // 处理剩余部分
        if (num - begin < k)
            reverse(s.begin() + begin, s.end());
        else
            reverse(s.begin() + begin, s.begin() + begin + k);

        return s;
    }
};

代码解析

1. 初始化变量：

   • num 是字符串的长度。
   • begin 用于记录每段的起始位置。

2. 特殊情况处理：

   • 如果字符串长度小于 k，直接反转整个字符串并返回。
   • 如果字符串长度在 [k, 2k) 之间，反转前 k 个字符并返回。

3. 分段反转：

   • 使用一个循环从头到尾遍历字符串。
   • 每当遍历到每 2k 个字符的结尾时（i % (2 * k) == 0），反转当前组的前 k 个字符。
   • 更新 begin 为下一组的起始位置。

4. 处理剩余部分：

   • 如果字符串的长度不是 2k 的整数倍，最后一段不足 k 个字符的部分需要单独反转。
   • 如果剩余部分小于 k 个字符，反转从 begin 到字符串末尾的部分；否则，反转从 begin 开始的 k 个字符。

5. 返回结果：

   • 遍历完成后，返回处理后的字符串。