题解 | #大数加法#

题目主要信息:

• 以字符串形式读入两个正整数，返回其相加结果
• 结果也是字符串形式
• 字符串只有数字0-9

举一反三：

学习完本题的思路你可以解决如下题目：

BM11. 链表相加（二）

方法：模拟法（建议使用）

思路：

大整数相加，就可以按照整数相加的方式，从个位开始，逐渐往上累加，换到字符串中就是从两个字符串的末尾开始相加。

具体做法:

• step 1：若是其中一个字符串为空，直接返回另一个，不用加了。
• step 2：交换两个字符串的位置，我们是s为较长的字符串，t为较短的字符串，结果也记录在较长的字符串中。
• step 3：从后往前遍历字符串s，每次取出字符转数字，加上进位制，将下标转换为字符串t中从后往前相应的下标，如果下标为非负数则还需要加上字符串t中相应字符转化的数字。
• step 4：整型除法取进位，取模算法去掉十位，将计算后的结果放入较长数组对应位置。
• step 5：如果遍历结束，进位值还有，则需要直接在字符串s前增加一个字符‘1’。

图示：

Java代码实现:

import java.util.*;
public class Solution {
    public String solve (String s, String t) {
         //若是其中一个为空，返回另一个
        if(s.length()<=0)
            return t;
        if(t.length()<=0)
            return s;
        //让s为较长的，t为较短的
        if(s.length() < t.length()){ 
            String temp = s;
            s = t;
            t = temp;
        }
        int carry = 0; //进位标志
        char[] res = new char[s.length()];
        //从后往前遍历较长的字符串
        for(int i = s.length() - 1; i >= 0; i--){ 
            //转数字加上进位
            int temp = s.charAt(i) - '0' + carry; 
            //转较短的字符串相应的从后往前的下标
            int j = i - s.length() + t.length(); 
            //如果较短字符串还有
            if(j >= 0) 
                //转数组相加
                temp += t.charAt(j) - '0'; 
            //取进位
            carry = temp / 10; 
            //去十位
            temp = temp % 10; 
            //修改结果
            res[i] = (char)(temp + '0'); 
        }
        String output = String.valueOf(res);
        //最后的进位
        if(carry == 1) 
            output = '1' + output;
        return output;
    }
}

C++代码实现:

class Solution {
public:
    string solve(string s, string t) {
        //若是其中一个为空，返回另一个
        if(s.empty())
            return t;
        if(t.empty())
            return s;
        //让s为较长的，t为较短的
        if(s.length() < t.length()) 
            swap(s, t);
        //进位标志
        int carry = 0; 
        //从后往前遍历较长的字符串
        for(int i = s.length() - 1; i >= 0; i--){ 
            //转数字加上进位
            int temp = s[i] - '0' + carry; 
            //转较短的字符串相应的从后往前的下标
            int j = i - s.length() + t.length(); 
            //如果较短字符串还有
            if(j >= 0) 
                //转数组相加
                temp += t[j] - '0'; 
            //取进位
            carry = temp / 10; 
            //去十位
            temp = temp % 10; 
            //修改结果
            s[i] = temp + '0'; 
        }
        //最后的进位
        if(carry == 1) 
            s = '1' + s;
        return s;
    }
};

Python实现代码：

class Solution:
    def solve(self , s: str, t: str) -> str:
        #若是其中一个为空，返回另一个
        if len(s) == 0:
            return t
        if len(t) == 0:
            return s
        #让s为较长的，t为较短的
        if len(s) < len(t): 
            temp = t
            t = s
            s = temp
        #进位标志
        carry = 0 
        i = len(s) - 1
        #从后往前遍历较长的字符串
        while i>=0 :
            #转数字加上进位
            temp = ord(s[i]) - ord('0') + carry
            #转较短的字符串相应的从后往前的下标
            j = i - len(s) + len(t) 
            #如果较短字符串还有
            if j >= 0: 
                #转数组相加
                temp += ord(t[j]) - ord('0') 
            #取进位
            carry = int(temp / 10) 
            #去十位
            temp = temp % 10 
            s = s[:i] + chr(temp + ord('0')) + s[i+1:]
            i -= 1
        #最后的进位
        if carry == 1: 
            s = '1' + s
        return s

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为较长字符的长度，遍历字符串
• 空间复杂度：$O(1)O(1)$，常数级空间，没有使用额外辅助空间