leetcode解题: Add Strings (415)

发表于 | 分类于

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

Note:

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

解法1：Two pointers, O(N + M) Time

经典的两数相加问题，主要的考察就是每一位上怎么计算digit和carry。digit = (temp + carry) % 10, carry = (temp + carry) / 10;
容易忘记的几个点：

  1. 如果两个string的长度不相等，最后要遍历剩下较长的string
  2. 最后要判断carry是否为0，如果不是，要在string的最前面加上carry的值

C++

C++ 里的几个用法：

  • char& to int: 只能用c - ‘0’这种办法
  • int to string: 在c++ 11里有std::to_string 的函数，用法为std::to_string(string& s)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    class Solution {
    public:
        string addStrings(string num1, string num2) {
            if (num1.empty()) {
                return num2;
            }
            if (num2.empty()) {
                return num1;
            }
            string res = "";
            int carry = 0;
            int i, j;
            for (i = num1.size() - 1, j = num2.size() - 1; i >= 0 && j >= 0; --i, --j) {
                int temp = num1[i] - '0' + num2[j] - '0';
                int digit = (temp + carry) % 10;
                carry = (temp + carry) / 10;
                res = to_string(digit) + res;
            }
            for (; i >= 0; --i) {
                int temp = num1[i] - '0';
                int digit = (temp + carry) % 10;
                carry = (temp + carry) / 10;
                res = to_string(digit) + res;
            }
            for (; j >= 0; --j) {
                int temp = num2[j]  - '0';
                int digit = (temp + carry) % 10;
                carry = (temp + carry) / 10;
                res = to_string(digit) + res;
            }
            if (carry > 0) {
                res = to_string(carry) + res;
            }
            return res;
        }
    };

Java

1