小旭讲解 LeetCode 415. 字符串相加

原题

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。

注意：

• num1 和num2 的长度都小于 5100.
• num1 和num2 都只包含数字 0-9.
• num1 和num2 都不包含任何前导零。
• 你不能使用任何內建 BigInteger 库， 也不能直接将输入的字符串转换为整数形式。

思路

这是一道大整数相加的经典题目，值得注意的是，为了方便计算我们通常习惯性地会将数字的低位存放到字符数组（或字符串）的低位。无论是加减乘除。

class Solution {
public:
    string addStrings(string num1, string num2) {
        string ans;
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());
        int i = 0, t = 0;
        while (i < num1.size() || i < num2.size()) {
            int n1 = 0, n2 = 0;
            if (i < num1.size()) n1 = num1[i] - '0';
            if (i < num2.size()) n2 = num2[i] - '0';
            ans.push_back('0' + (n1 + n2 + t) % 10);
            t = (n1 + n2 + t) / 10;
            ++i;
        }
        if (t > 0) ans.push_back('0' + t);
        while (ans.size() > 1 && ans.back() == 0) ans.pop_back();
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

关于大整数（高精度）的加减乘除可以参考如下代码：

高精度加法 – 算法板子

高精度减法 – 算法板子

高精度乘法 – 算法板子

高精度除法 – 算法板子

复杂度分析

时间复杂度：O(n)
空间复杂度：O(1)

参考

[1]. LeetCode 原题. https://leetcode-cn.com/problems/add-strings/

本文为原创文章，欢迎分享，勿全文转载，如果内容你实在喜欢，可以加入收藏夹，说不定哪天故事又继续更新了呢。
本文地址：https://qoogle.top/xiaoxu-tutorial-leetcode-415-add-string/