LeetCode 415：字符串相加的独特求解之道
前言
🚀 欢迎来到《编程探索录》！
这里是算法与数据结构的实战天地，也是你从“基础解法”迈向“高效解法”的蜕变之所。
🔍 本专栏目标：
- 借助清晰的图示 + 多种语言代码（Python/Java/C++/C），剖析每道题背后的逻辑脉络。
- 不仅讲解“怎么做”，更深挖“为何如此做”——涵盖题目剖析、边界情形考量以及复杂度优化等方面。
- 适合想要夯实根基或冲刺面试的你，尤其针对LeetCode/牛客平台的高频题目！
💡 本专栏使用指南：
1️⃣ 先自主思索：尝试自行编写出第一版代码（哪怕较为简陋）。
2️⃣ 对比解法：对比我的思路与你的差异，汲取优化窍门。
3️⃣ 融会贯通：每篇结尾会附上相似题目链接，趁热打铁巩固所学。
📌 持续打卡：
算法并无捷径可循，但正确的方法能助你少走弯路。每日15分钟，和我一同用代码淬炼思维！
题目详情
给定两个以字符串形式呈现的非负整数 num1 和 num2，计算它们的和并同样以字符串形式返回。
需注意，不能运用任何内置的大数类型（比如BigInteger）或直接将输入的字符串转换为整数形式来计算。
典型示例
示例 1：
输入：num1 = "11", num2 = "123"
输出："134"
示例 2：
输入：num1 = "456", num2 = "77"
输出："533"
示例 3：
输入：num1 = "0", num2 = "0"
输出："0"
问题剖析
此问题要求我们实现两个字符串形式数字的相加操作，并返回字符串形式的结果。由于输入的数字可能极大，超出常规整数类型的范畴，所以不能直接将其转换为整数进行运算。
该问题本质上是对我们小学所学竖式加法运算流程的模拟：
- 从最低位（个位）起步，逐位进行相加运算
- 妥善处理进位状况
- 最后或许需要在最高位添加一个进位
求解思路
可依照以下步骤来解决此问题：
- 从两个字符串的末尾开始遍历（也就是从个位开始）
- 对对应位置的数字进行相加，再加上可能存在的进位
- 计算当前位的结果以及新的进位
- 将当前位的结果添加到结果字符串中
- 遍历结束后，检查是否还有进位，若有则添加到结果中
- 因为我们是从低位向高位计算的，所以最后要将结果字符串反转
代码实现
class Solution {
public:
string addStrings(string num１, string num２) {
string res;
res.reserve(max(num１.size(), num２.size()) + 1);
int pos1 = num１.size() - 1;
int pos2 = num２.size() - 1;
int carry = 0;
while (pos1 >= 0 || pos2 >= 0) {
int digit1 = pos1 >= 0 ? num１[pos1--] - '0' : 0;
int digit2 = pos2 >= 0 ? num２[pos2--] - '0' : 0;
int total = digit1 + digit2 + carry;
carry = total / 10;
total = total % 10;
res += ('0' + total);
}
if (carry == 1) {
res += '1';
}
reverse(res.begin(), res.end());
return res;
}
};
代码解析
- 初始化操作：
string res; res.reserve(max(num１.size(), num２.size()) + 1);
预先为结果字符串分配足够的空间，最大长度为两个输入字符串中较长的那个加1（考虑可能的进位情况）。
- 设定指针与进位标志：
int pos1 = num１.size() - 1; int pos2 = num２.size() - 1; int carry = 0;
pos1和pos2分别指向两个字符串的末尾（最低位），carry用于记录进位情况。
-
逐位相加运算：
while (pos1 >= 0 || pos2 >= 0) { int digit1 = pos1 >= 0 ? num１[pos1--] - '0' : 0; int digit2 = pos2 >= 0 ? num２[pos2--] - '0' : 0; int total = digit1 + digit2 + carry; carry = total / 10; total = total % 10; res += ('0' + total); }- 循环条件为只要还有任一字符串未处理完毕
- 将字符转换为数字：
num[i] - '0' - 若某个字符串已处理完毕，对应位置用0补充
- 计算当前位的数值以及新的进位
- 将当前位的结果添加到结果字符串中
-
处理最终进位：
if (carry == 1) {
res += '1';
}
若最后仍有进位，需在结果中添加一个’1’。
- 反转结果：
reverse(res.begin(), res.end());
由于我们是从低位到高位构建结果的，所以最后要对字符串进行反转。
算法复杂度考量
- 时间复杂度：O(max(n, m))，其中n和m分别为两个输入字符串的长度。需要对两个字符串各遍历一次。
- 空间复杂度：O(max(n, m))，用于存储结果字符串。
优化之处
- 运用
reserve()预先分配内存，避免多次内存重新分配，提升效率。 - 直接在循环中进行字符到数字的转换，减少了额外的转换步骤。
- 利用
+=运算符追加字符，使代码更为简洁。
总结
此题为经典的大数加法问题，通过模拟人工计算的过程，能够实现任意长度数字的相加操作。关键要点在于：
- 从低位向高位逐位进行计算
- 正确处理进位情况
- 最后对结果进行反转
该方法不仅可用于解决本题，还能拓展应用到其他需要处理大数运算的场景，比如大数减法、乘法等。
相关题目举荐
- LeetCode 2. 两数相加
- LeetCode 43. 字符串相乘
- LeetCode 66. 加一
- LeetCode 67. 二进制求和
- LeetCode 989. 数组形式的整数加法
📢 要是你也钟情于这种“非传统”的技术风格：
👁️ 【关注】 瞧瞧一位非典型程序员怎样用独特方式解决正经问题
👍 【点赞】 给“不搞八股文”的技术分享一些鼓励
🔖 【收藏】 把这些“新奇却实用”的代码技巧收纳起来
💬 【评论】 来聊聊——你碰到过最“奇葩”的 Bug 是啥？
🗳️ 【投票】 您的支持是我前行的动力
技术不存在标准答案，让我们一同以最有趣的方式，编写出最可靠的代码！ 🎮💻
相关文章
