2024-07-04 大数加法

以字符串的形式读入两个数字，编写一个函数计算它们的和，以字符串形式返回。

数据范围：${s.length,t.length ≤ 100000}$，字符串仅由'0'~‘9’构成

大数加法

中等难度

解题思路

亮点

• 使用了 char 类型，如果已知一个 char 为数字，那么 valueOf(char) - 48 就可以得到对应的数字。
• 时间复杂度为 O(n)
• 空间复杂度为 O(max(n,m) + 1)

实现

public String solve(String s, String t) {
    // write code here
    int sLength = s.length();
    int tLength = t.length();
    int maxLength = Math.max(sLength, tLength);
    int[] result = new int[maxLength + 1];
    int index = 0;
    int carry = 0;
    for (int i = maxLength; i > 0; i--) {
        int mid = carry;
        if (index < sLength) {
            mid += s.charAt(sLength - index - 1) - 48;
        }
        if (index < tLength) {
            mid += t.charAt(tLength - index - 1) - 48;
        }
        result[index++] = mid % 10;
        carry = mid >= 10 ? 1 : 0;
    }
    if (carry == 1) {
        result[index] = carry;
    }
    StringBuilder b = new StringBuilder();
    for (int i = maxLength; i >= 0; i--) {
        if (i == maxLength && result[i] == 0) {
            continue;
        }
        b.append(result[i]);
    }
    return b.toString();
}