0415. Add Strings ================= 题目信息 -------- :题号: 0415 :难度: Easy :主题: 非负整数字符串、十进制加法、进位、禁止整体转换 :原题: `LeetCode 0415 `_ :重点: 输入可能远超内置整数范围、不能直接转为整数或使用大整数库、返回规范十进制和 题目重述 -------- 给定两个表示非负整数的十进制字符串 ``num1`` 和 ``num2``,返回它们相加后的十进制字符串。 两个字符串长度均位于 ``[1, 10^4]``,只包含数字;除字符串 ``"0"`` 外不会含前导零。不能把完整字符串直接转换为整数,也不能使用专门的大整数运算库。结果应使用普通十进制写法,除零本身外不含前导零。 自建示例 -------- 连续产生进位: .. code-block:: text 输入:num1 = "999",num2 = "7" 输出:"1006" 解释:个位 9 + 7 产生进位,进位继续传递到更高位,最终新增最高位 1。 两个零相加: .. code-block:: text 输入:num1 = "0",num2 = "0" 输出:"0" 解释:结果使用单个字符 0,不能返回空字符串或含前导零的形式。 从末位模拟进位 ---------------- 字符串加法与手算相同,从两个字符串的末位开始,每一位加上当前进位,写入结果的末尾,再把指针向左移动。较短字符串缺少的高位按 0 处理;循环结束后若仍有进位,再追加一个 ``1``,最后反转结果。 C++ 实现 -------- .. code-block:: cpp class Solution { public: std::string addStrings(std::string num1, std::string num2) { int i = static_cast(num1.size()) - 1; int j = static_cast(num2.size()) - 1; int carry = 0; std::string result; while (i >= 0 || j >= 0 || carry != 0) { int sum = carry; if (i >= 0) sum += num1[i--] - '0'; if (j >= 0) sum += num2[j--] - '0'; result.push_back(static_cast('0' + sum % 10)); carry = sum / 10; } std::reverse(result.begin(), result.end()); return result; } }; 代码分析 -------- 每一位只依赖两个当前数字和一个进位,不会把完整字符串转换为固定宽度整数;输入为零时循环仍会写出一个 ``0``。设两串最大长度为 ``n``,时间复杂度为 ``O(n)``,额外空间为 ``O(n)``。