题目描述

Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2.

Note:

  1. The length of both num1 and num2 is < 5100.
  2. Both num1 and num2 contains only digits 0-9.
  3. Both num1 and num2 does not contain any leading zero.
  4. You must not use any built-in BigInteger library or convert the inputs to integer directly.

解法一

思路

这题其实只用模拟一下小学的竖式加法就好了,更多的技巧是在如何让代码写的更优雅。

我们以1254147相加为例来看看竖式加法:

  1 2 5 4
+   1 4 7
---------
  1 4^0^1

Out: 1401
Note: ^ 符号代表低位产生进位

下面来说说竖式加法的几个要注意的地方:

  • 低位对齐,即以字符串尾对齐;
  • 加法仅为0-90-9间的数字相加,除此之外还要带上低位的进位;
  • 低位的进位只可能是01,且初始为0
  • 加法可能产生进位,但进位最多为10-90-9间的数字相加,再加上进位,最大为19)。

那么算法就呼之欲出了:

  • 想要低位对齐,就同步从两个字符串的最后一个字符向前遍历,直到两个字符串均遍历完成。若中途有一个字符串遍历完成,则此后将此字符串的字符认作0
  • 定义变量carry记录低位的进位,初始值为0
  • 每次遍历时,将carry更新为加上两个字符值之后的值,再以carry的个位的数字作为当前位置的结果,更新carry为其十位上的数字(进位)。
  • 遍历字符串完成后,如果carry1(最高位有进位),则将1添加到结果。
  • 输出结果。

Python

class Solution(object):
    def addStrings(self, num1, num2):
        """
        :type num1: str
        :type num2: str
        :rtype: str
        """
        i = len(num1) - 1
        j = len(num2) - 1
        result = ''
        carry = 0
        while i >= 0 or j >= 0:
            if i >= 0:
                carry += ord(num1[i]) - ord('0')
            if j >= 0:
                carry += ord(num2[j]) - ord('0')
            result += chr(carry % 10 + ord('0'))
            carry //= 10
            i -= 1
            j -= 1
        if carry == 1:
            result += '1'
        return result[::-1]

Java

public class Solution {
    public String addStrings(String num1, String num2) {
        int i = num1.length() - 1;
        int j = num2.length() - 1;
        StringBuilder builder = new StringBuilder();
        int carry = 0;
        while (i >= 0 || j >= 0) {
            if (i >= 0) {
                carry += num1.charAt(i) - '0';
            }
            if (j >= 0) {
                carry += num2.charAt(j) - '0';
            }
            builder.append((char)(carry % 10 + '0'));
            carry /= 10;
            i--;
            j--;
        }
        if (carry == 1) {
            builder.append('1');
        }
        return builder.reverse().toString();
    }
}

C++

class Solution {
public:
    string addStrings(string num1, string num2) {
        int i = num1.size() - 1;
        int j = num2.size() - 1;
        string result = "";
        int carry = 0;
        while (i >= 0 || j >= 0) {
            if (i >= 0) {
                carry += num1[i] - '0';
            }
            if (j >= 0) {
                carry += num2[j] - '0';
            }
            result += (char)(carry % 10 + '0');
            carry /= 10;
            i--;
            j--;
        }
        if (carry == 1) {
            result += '1';
        }
        reverse(result.rbegin(), result.rend());
        return result;
    }
};