C++之string题目练习
string
- 一.字符串相加
- 一.解题思路：模拟竖式加法
- 二.代码实现（C++）
- 三.代码优化与细节说明
- 四.复杂度分析
- 二.把字符串转换为整数
- 从代码到理解：深入解析字符串转整数的实现
- 问题背景
- 代码解析
- 1. 跳过空格
- 2. 处理正负号
- 3. 转换数字部分
- 关键点：整数溢出检查
- 4. 返回结果
- 三.反转字符串中的单词
- 问题背景
- 解题思路
- 代码实现
- 代码解析
- 四.反转字符串
- 问题背景
- 解题思路
- 代码实现
- 代码解析
一.字符串相加
leetcode题目链接：https://leetcode.cn/problems/add-strings/description/
一.解题思路：模拟竖式加法
我们可以借鉴小学学习的竖式加法思路，从低位到高位逐位相加，并处理进位问题。具体步骤如下：
- 初始化指针和进位
定义两个指针 l1 和 l2，分别指向 num1 和 num2 的末尾（即最低位）。
定义变量 tmp 表示当前位的进位（初始为 0）。
- 逐位相加
循环处理每一位的加法，直到两个字符串都遍历完毕：
取出当前位的数字（字符转数字：char - ‘0’），与进位 tmp 相加。
计算当前位的结果：和对 10 取余（得到当前位数值）。
更新进位：和除以 10（得到进位值）。
将当前位结果转换为字符，存入结果字符串。
- 处理剩余高位
若其中一个字符串先遍历完毕，继续处理另一个字符串的剩余高位，每次处理时仍需加上当前进位。
- 处理最后进位
若所有位处理完毕后仍有进位（tmp > 0），需将进位作为最高位添加到结果中。
- 反转结果
由于我们是从低位到高位逐位计算的，结果字符串是逆序的，最后需要反转得到正确顺序。
二.代码实现（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; } };三.代码优化与细节说明
- 进位处理的简化
原代码中对进位的处理稍显繁琐（先判断是否大于 9，再拆分结果和进位）。优化后的代码通过 取余运算 和 除法运算 直接计算当前位结果和进位，逻辑更简洁：
tmp % 10：得到当前位数值（如和为 13，当前位为 3）。
tmp / 10：得到进位值（如和为 13，进位为 1）。
- 结果字符串的逆序存储
从低位到高位计算时，结果会先存储低位（如计算 123 + 456 时，先存 9，再存 7，最后存 5）。因此需要在最后反转字符串，得到正确顺序 579。
- 边界情况处理
长度不同的字符串：通过两个独立的循环处理剩余高位，确保所有位都被计算。
最高位进位：如 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 INT_MAX % 10)) { return sign == 1 ? INT_MAX : INT_MIN; } ret = ret*10+(str[i] - '0'); } else{ // 遇到非数字字符，停止转换 break; } } return sign*ret; } };1. 跳过空格
在字符串的开头，可能会有一些空格字符。我们需要跳过这些空格，以便从第一个非空格字符开始处理。代码中通过以下循环实现：
while( i
2. 处理正负号
字符串中的数字可能带有正负号。我们需要判断正负号，并更新符号标志 sign。代码中通过以下逻辑处理：
if(i
如果字符串以 '-' 开头，将符号标志设置为 -1，并跳过该字符；如果以 '+' 开头，则跳过该字符，符号标志保持为 1。
3. 转换数字部分
接下来，我们需要将字符串中的数字字符转换为整数。代码中通过以下循环实现：
for(;i if(str[i] = '0' && str[i] // 检查是否会发生整数溢出 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"。
解题思路
要解决这个问题，我们可以采用两步策略：
- 反转整个字符串：首先将整个字符串反转，这样单词的顺序会被颠倒，但单词内部的字符顺序也会被颠倒。
- 反转每个单词：接着，我们需要将每个单词内部的字符顺序重新反转回来，以恢复单词的原始顺序。
然而，上述方法虽然直观，但实现起来可能会比较复杂。我们可以通过另一种更简洁的方式实现目标：直接在原字符串上操作，逐个反转单词。这就是我们今天要介绍的代码实现的核心思想。
代码实现
以下是用 C++ 实现的代码：
class Solution { public: string reverseWords(string s) { int n = s.size(); int start = 0; for (int i = 0; i if (s[i] == ' ' || i == n) { reverse(s.begin() + start, s.begin() + i); start = i + 1; } } return s; } }; public: string reverseStr(string s, int k) { int num = s.size(); int begin = 0; // 特殊情况处理 if (num
- 初始化指针和进位
- 代码解析
