详解LeetCode中用字符串实现整数相加,字符串转整数及其溢出处理详解

目录

题目背景

代码整体逻辑

变量初始化

逐位相加过程

处理最后进位

结果反转

示例演示

总结

---

在LeetCode中，有一道经典的算法题是实现两个字符串形式的非负整数相加，今天我们就来深入分析一段用C++实现该功能的代码，探究其背后的逻辑与实现细节。

题目背景

在实际编程中，我们经常会遇到处理超大整数的情况，由于编程语言中内置的数据类型（如 int 、 long long ）存在表示范围的限制，无法直接存储和处理这些超大整数。此时，将整数以字符串的形式存储，并通过自定义的算法来实现相应的运算就显得尤为重要。本题就是要求我们实现两个用字符串表示的非负整数相加的功能。

代码整体逻辑

我们来看这段C++代码，它定义了一个名为 Solution 的类，其中包含一个 addStrings 成员函数，该函数用于实现两个字符串形式整数的相加。整体思路是从两个字符串的末尾开始逐位相加，同时处理进位的情况，最后将结果反转得到正确的顺序。

cppclass Solution {public:string addStrings(string num1, string num2) {int end1=num1.size()-1,end2=num2.size()-1;int next =0;string retstr;while(end1>=0||end2>=0){int val1=0,val2=0;if(end1>=0){val1=num1[end1]-'0'; }if(end2>=0){val2=num2[end2]-'0'; }int ret=val1+val2+next;if(ret>9){ret%=10;next=1;}else{next=0;}retstr+=(ret+'0');--end1;--end2;}if(next==1){retstr+='1';}reverse(retstr.begin(),retstr.end());return retstr;}};

变量初始化

 end1 和 end2 分别用于记录 num1 和 num2 字符串的末尾索引，通过字符串的 size() 函数获取长度后减1得到。 next 变量用于记录进位，初始化为0，表示一开始没有进位。 retstr 用于存储最终的相加结果，初始化为空字符串。

逐位相加过程

cppwhile(end1>=0||end2>=0){int val1=0,val2=0;if(end1>=0){val1=num1[end1]-'0'; }if(end2>=0){val2=num2[end2]-'0'; }int ret=val1+val2+next;if(ret>9){ret%=10;next=1;}else{next=0;}retstr+=(ret+'0');--end1;--end2;}

- 获取当前位数字：在每次循环中，首先初始化 val1 和 val2 为0。然后通过条件判断，若 end1 或 end2 仍在有效索引范围内（即大于等于0），则将 num1 和 num2 对应位置的字符转换为数字。这里通过 -'0' 的操作实现字符到数字的转换，例如字符 '5' 减去字符 '0' ，在ASCII码表中，字符 '5' 的编码值减去字符 '0' 的编码值，就得到数字5。

- 计算当前位和及处理进位：将 val1 、 val2 与 next （进位）相加得到 ret 。若 ret 大于9，说明产生了进位，此时将 ret 对10取模得到当前位应保留的数字，同时将 next 设为1，表示有进位；若 ret 小于等于9，则没有进位，将 next 设为0。

- 存储结果：将计算得到的当前位数字 ret 转换回字符（通过 ret + '0' ），并添加到 retstr 字符串中。最后将 end1 和 end2 分别减1，指向下一位数字，继续循环。

处理最后进位

cppif(next==1){retstr+='1';}

循环结束后，有可能还存在进位（即 next 为1），此时需要在结果字符串 retstr 的末尾添加字符 '1' ，以表示最高位的进位。

结果反转

cppreverse(retstr.begin(),retstr.end());return retstr;

由于我们是从字符串末尾开始逐位相加，得到的结果字符串 retstr 是逆序的，所以需要使用 reverse 函数将其反转，使其成为正确的顺序，最后返回结果字符串。

示例演示

假设 num1 = "123" ， num2 = "456" ：

1. 初始化： end1 = 2 ， end2 = 2 ， next = 0 ， retstr = "" 。

2. 第一次循环：

-  val1 = num1[2] - '0' = '3' - '0' = 3 ， val2 = num2[2] - '0' = '6' - '0' = 6 。

-  ret = 3 + 6 + 0 = 9 ， next = 0 ， retstr = "9" ， end1 = 1 ， end2 = 1 。

3. 第二次循环：

-  val1 = num1[1] - '0' = '2' - '0' = 2 ， val2 = num2[1] - '0' = '5' - '0' = 5 。

-  ret = 2 + 5 + 0 = 7 ， next = 0 ， retstr = "79" ， end1 = 0 ， end2 = 0 。

4. 第三次循环：

-  val1 = num1[0] - '0' = '1' - '0' = 1 ， val2 = num2[0] - '0' = '4' - '0' = 4 。

-  ret = 1 + 4 + 0 = 5 ， next = 0 ， retstr = "579" ， end1 = -1 ， end2 = -1 。

5. 循环结束， next = 0 ，无需处理进位。

6. 反转 retstr 得到 "579" ，返回结果。

再假设 num1 = "99" ， num2 = "1" ：

1. 初始化： end1 = 1 ， end2 = 0 ， next = 0 ， retstr = "" 。

2. 第一次循环：

-  val1 = num1[1] - '0' = '9' - '0' = 9 ， val2 = num2[0] - '0' = '1' - '0' = 1 。

-  ret = 9 + 1 + 0 = 10 ， ret %= 10 = 0 ， next = 1 ， retstr = "0" ， end1 = 0 ， end2 = -1 。

3. 第二次循环：

-  val1 = num1[0] - '0' = '9' - '0' = 9 ， val2 = 0 。

-  ret = 9 + 0 + 1 = 10 ， ret %= 10 = 0 ， next = 1 ， retstr = "00" ， end1 = -1 ， end2 = -1 。

4. 循环结束， next = 1 ， retstr += '1' ，此时 retstr = "100" 。

5. 反转 retstr 得到 "100" ，返回结果。

---

C++实现
 

在编程过程中，将字符串转换为整数是一个常见的需求。但由于字符串的复杂性以及整数类型的取值范围限制，这个过程需要考虑诸多细节，尤其是溢出处理。本文将围绕一段C++代码，详细解析字符串转整数功能的实现逻辑以及溢出处理机制。
 

题目需求与代码功能概述
 

给定一个字符串，将其转换为对应的整数。同时需要处理字符串开头的空格、正负号，并且在转换过程中要考虑整数溢出的情况。上述代码通过定义 Solution 类中的 strToInt 函数实现了该功能，下面我们逐行分析代码的具体实现。
 

代码详细解析
 

cppclass Solution {
public:int strToInt(string str) {int i = 0, flag = 1;int res = 0; //默认flag = 1，正数while (str[i] =='') i++;

1. 初始化变量：
 

-  i  用于记录当前处理到字符串的位置，初始化为 0，从字符串的第一个字符开始处理。
 
-  flag  用于标记整数的正负，初始化为 1，表示正数。如果后续遇到负号， flag  会被赋值为 -1。
 
-  res  用于存储转换后的整数结果，初始化为 0。
 
2. 跳过字符串开头的空格：通过 while 循环，只要当前字符是空格（ str[i] =='' ），就将 i 向后移动一位，直到遇到非空格字符。
 

cppif (str[i] == '-') flag = -1;if (str[i] == '-' || str[i] == '+') i++;

 
1. 处理正负号：
 

- 首先判断当前字符是否为负号（ str[i] == '-' ），如果是，将 flag 赋值为 -1，表示后续转换的整数为负数。
 
- 接着判断当前字符是否为负号或正号（ str[i] == '-' || str[i] == '+' ），无论哪种情况，都将 i 向后移动一位，跳过正负号，准备处理后面的数字字符。
 

cppfor (; i < str.size() && isdigit(str[i]); i++) {if (res > INT_MAX / 10 || (res == INT_MAX / 10 && str[i] - '0' > 7)) //溢出判定return flag == 1? INT_MAX : INT_MIN;res = res * 10 + (str[i] - '0');} 

 
 
1. 逐位转换数字字符：
 

- 通过 for 循环遍历字符串中剩余的字符。循环条件 i < str.size() && isdigit(str[i]) 表示只要当前位置在字符串范围内且当前字符是数字字符（通过 isdigit 函数判断，该函数在 <cctype> 头文件中定义，用于判断字符是否为 '0' 到 '9' 的数字字符），就继续执行循环体。
 

- 溢出判定：
 

-  res > INT_MAX / 10 ： INT_MAX 是 <climits> 头文件中定义的 int 类型的最大值。如果当前的结果 res 已经大于 INT_MAX / 10 ，那么当再乘以 10 并加上下一位数字时，必然会超过 int 类型能表示的最大值，导致溢出。
 
-  res == INT_MAX / 10 && str[i] - '0' > 7 ：当 res 等于 INT_MAX / 10 时，即使再乘以 10 恰好达到 INT_MAX ，但如果加上下一位数字后，仍可能超过 INT_MAX 。因为 INT_MAX 的最后一位数字是 7 （以十进制表示），所以当 res 等于 INT_MAX / 10 且下一位数字转换后的整数值大于 7 时，也会导致溢出。一旦检测到溢出，根据 flag 的值返回 INT_MAX （正数情况）或 INT_MIN （负数情况）。
 
- 数字转换： res = res * 10 + (str[i] - '0');  将当前数字字符转换为对应的整数值并累加到 res 中。 str[i] - '0' 通过字符的ASCII码差值将字符形式的数字转换为整数，例如 '5' - '0' 得到整数 5 ，再通过 res * 10 将之前的结果扩大10倍，以正确构建整数。
 

cppreturn flag * res;}
};

 
 
1. 返回结果：循环结束后，将最终的结果 res 乘以 flag ，根据正负号调整结果，然后返回转换后的整数。
 

示例分析
 

1. 示例一：输入字符串 "42" 
 
- 初始化： i = 0 ， flag = 1 ， res = 0 。
 
- 字符串无空格，直接处理。字符 '4' ， res = 0 * 10 + ('4' - '0') = 4 ；字符 '2' ， res = 4 * 10 + ('2' - '0') = 42 。
 
- 循环结束，返回 flag * res = 1 * 42 = 42 。
 
2. 示例二：输入字符串 "   -42" 
 
- 初始化： i = 0 ， flag = 1 ， res = 0 。
 
- 跳过开头的空格， i 移动到负号位置， flag = -1 ， i 再向后移动一位。
 
- 字符 '4' ， res = 0 * 10 + ('4' - '0') = 4 ；字符 '2' ， res = 4 * 10 + ('2' - '0') = 42 。
 
- 循环结束，返回 flag * res = -1 * 42 = -42 。
 
3. 示例三：输入字符串 "2147483648" （超过 int 最大值）
 
- 初始化： i = 0 ， flag = 1 ， res = 0 。
 
- 逐位转换过程中，当处理到最后一位 '8' 时， res 等于 INT_MAX / 10 ，且 '8' - '0' > 7 ，触发溢出判定，返回 INT_MAX 。
 
 

总结

这段代码通过从字符串末尾逐位相加、处理进位以及结果反转的方式，巧妙地实现了两个字符串形式非负整数的相加。在处理大整数运算时，这种方法非常实用，它避免了数据类型表示范围的限制，为我们在实际编程中处理超大整数运算提供了有效的解决方案。实现了字符串到整数的转换，并严谨地处理了可能出现的溢出情况。在实际开发中，处理数据类型转换时，考虑边界条件和溢出情况是保证程序正确性和稳定性的关键。通过对这段代码的分析，我们不仅掌握了字符串转整数的实现方法，也加深了对整数溢出处理的理解。同时，通过对代码的详细分析，我们也能更好地理解和掌握字符串处理与基础数学运算结合的编程技巧。