LC.P415[字符串相加]

方法一：高精度加法(模板)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public String addStrings(String num1, String num2) {
        int n = num1.length(), m = num2.length();
        int[] A = new int[n], B = new int[m];
        for (int i = n - 1, j = 0; i >= 0; --i, ++j) A[j] = num1.charAt(i) - '0';
        for (int i = m - 1, j = 0; i >= 0; --i, ++j) B[j] = num2.charAt(i) - '0';

        int carry = 0;
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < n || i < m; ++i) {
            if (i < n) carry += A[i];
            if (i < m) carry += B[i];
            builder.append(carry % 10);
            carry /= 10; // 进位
        }
        // 如果最高位还有进位，则在最高位添加1
        if (carry > 0) builder.append(1);
        return builder.reverse().toString();
    }
}
  • 时间复杂度：$O(max(m, n))$
  • 空间复杂度：$O(m + n)$

方法二：双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public String addStrings(String num1, String num2) {
        int i = num1.length() - 1, j = num2.length() - 1;
        StringBuilder builder = new StringBuilder();
        for (int carry = 0; i >= 0 || j >= 0 || carry > 0; --i, --j) {
            if (i >= 0) carry += num1.charAt(i) - '0';
            if (j >= 0) carry += num2.charAt(j) - '0';
            builder.append(carry % 10);
            carry /= 10; // 进位
        }
        return builder.reverse().toString();
    }
}
  • 时间复杂度：$O(max(m, n))$
  • 空间复杂度：$O(1)$