小旭讲解 LeetCode 415. 字符串相加
小旭讲解 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/
最后修改日期:2020年8月3日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。