字符串相加＜难度系数⭐＞

1、 字符串相加＜难度系数⭐＞

📝 题述：给定两个字符串形式的非负整数 num1 和 num2 ，计算它们的和并同样以字符串形式返回。你不能使用任何內建的用于处理大整数的库 (比如 BigInteger：大数运算)， 也不能直接将输入的字符串转换为整数形式。

💨示例1：

输入：num1 = “11”, num2 = “123”
输出：“134”

💨示例2：

输入：num1 = “456”, num2 = “77”
输出：“533”

💨示例3：

输入：num1 = “0”, num2 = “0”
输出：“0”

⚠ 提示

• 1 <= num1.length, num2.length <= 10^4^
• num1 和 num2 都只包含数字 0 - 9
• num1 和 num2 都不包含任何前导零

🧷 平台：Visual studio 2017 && windows

🍳 拓展：

有些语言里会提供一个库叫 BigInteger(大数运算)：顾名思义，就是很大的数值的数进行一系列的运算。由于编程语言提供的基本数值数据类型表示的数值范围有限，不能满足较大规模的高精度数值计算，因此需要利用其他方法实现高精度数值的计算，于是产生了大数运算。大数运算主要有加、减、乘三种方法。

我们平时表示较大整型时用的是 long long 或 int64，它们都是 8Byte，能表示的范围是 2^64^，已经很大了，大概是一个 20 位的整数(严格来说是 19 位)，但是在一些高科技领域要进行科学计算，所以还远远不够，那么怎么处理呢？？？

这时有人就写出了 BigInteger，它用字符串来表示整数 —— 意味着无论多大的整数都可以表示。

可以看到这道题用 C语言去做，两个数字相加之和是多大，不好开空间，但是用 string 的话就可以不用管了，string 的底层实现了自动增容。

🔑 核心思想 1：

leetcode原题

class Solution {
public:
    string addStrings(string num1, string num2) {
        string retStr;
        int end1 = num1.size() - 1;
        int end2 = num2.size() - 1;
        int carry = 0;
        while(end1 >= 0 || end2 >= 0)//只要还有一位那么就继续
        {
            int val1 = 0, val2 = 0;
            if(end1 >= 0)
            {
                val1 = num1[end1] - '0';
                --end1;
            }
            if(end2 >= 0)
            {
                val2 = num2[end2] - '0';
                --end2;
            }
            int ret = val1 + val2 + carry;
            if(ret > 9)//进位
            {
                ret -= 10;
                carry = 1;
            }
            else
            {
                carry = 0;
            }
            //头插
            retStr.insert(0, 1, '0' + ret);
            //retStr.insert(retStr.begin(), '0' + ret);//同上
        } 
        if(carry == 1)//还有一位的情况："1","9"
        {
           retStr.insert(retStr.begin(), '1');
        }
        return retStr;
    }
};

📝说明

假设 num1 和 num2 的长度为 n，则如上代码的时间复杂度是多少 ❓

O(N) ？？？

就思路来说时间复杂度是 O(N)，但是这里使用了 insert，所以原本是 O(N) 的时间复杂度硬是写成了 O(N^2^)

🧿 优化版本

🔑 核心思想 2：

每次将结果尾插，最后再逆置。

C++ 在算法这个头文件里提供了此类函数：

只要有迭代器，它就可以针对任何容器去使用：

class Solution {
public:
    string addStrings(string num1, string num2) {
        string retStr;
        int end1 = num1.size() - 1;
        int end2 = num2.size() - 1;
        int carry = 0;
        while(end1 >= 0 || end2 >= 0)//只要还有一位那么就继续
        {
            int val1 = 0, val2 = 0;
            if(end1 >= 0)
            {
                val1 = num1[end1] - '0';
                --end1;
            }
            if(end2 >= 0)
            {
                val2 = num2[end2] - '0';
                --end2;
            }
            int ret = val1 + val2 + carry;
            if(ret > 9)//进位
            {
                ret -= 10;
                carry = 1;
            }
            else
            {
                carry = 0;
            }
            //尾插
            retStr += ('0' + ret);
        } 
        if(carry == 1)//还有一位的情况："1","9"
        {
           retStr += '1';
        }
        //逆置
        reverse(retStr.begin(), retStr.end());
        return retStr;
    }
};

📝说明