【数据结构和算法】大数相加，3种方式解决

1，从尾部插入

实际上这道题求的是两个字符串相加，我们就用两个很短的字符串"12367"+"89"为例画个图来看下是怎么计算的

它相当于两个字符串从最右边开始相加，比如我们要计算s字符串的最右边的那个数字和t字符串最右边的那个字符相加

int i = s.length() - 1, j = t.length() - 1;
int x = s.charAt(i) - '0';
int y = t.charAt(j) - '0';
int sum = x + y;

把计算的结果放到一个新的字符串后面，但字符串每一位只能保存一位数字，而我们相加的结果sum可能是个两位数，所以这里我们只取他的个位数，十位数要往前进一位。比如我们要计算s和t的倒数第二位

int x = s.charAt(i - 1) - '0';
int y = t.charAt(j - 1) - '0';
int sum = x + y + carry;

carry就是上一步相加结果的进位，上一步如果进位了就是1，如果没进位就是0。搞懂了上面的相加过程，剩下的就是一些边界条件的判断。最后不要忘了对字符串进行反转，因为我们相加的时候是从s和t的尾部开始加的，下面我们来看下完整代码

    public String solve(String s, String t) {
        StringBuilder stringBuilder = new StringBuilder();
        int i = s.length() - 1, j = t.length() - 1, carry = 0;
        while (i >= 0 || j >= 0 || carry != 0) {
            int x = i < 0 ? 0 : s.charAt(i--) - '0';
            int y = j < 0 ? 0 : t.charAt(j--) - '0';
            int sum = x + y + carry;
            stringBuilder.append(sum % 10);//添加到字符串尾部
            carry = sum / 10;
        }
        return stringBuilder.reverse().toString();//对字符串反转
    }

2，从头部插入

上面是插入到字符串的尾部，最后再反转。实际上我们在计算的时候还可以先插入到字符串的头部，最后直接返回即可，不需要再反转了，代码和上面差不多，我们来看下

    public String solve(String s, String t) {
        StringBuilder stringBuilder = new StringBuilder();
        int carry = 0, i = s.length() - 1, j = t.length() - 1;
        while (i >= 0 || j >= 0 || carry != 0) {
            int x = i < 0 ? 0 : s.charAt(i--) - '0';
            int y = j < 0 ? 0 : t.charAt(j--) - '0';
            int sum = x + y + carry;
            stringBuilder.insert(0, sum % 10);//插入到s字符串的第一个位置
            carry = sum / 10;
        }
        return stringBuilder.toString();
    }

3，使用栈来解决

我们还可以先把相加的结果放到一个栈中，最后再一个个出栈。其实也是换汤不换药，代码都差不多，我们来看下

    public String solve(String s, String t) {
        Stack<integer> stack = new Stack&lt;&gt;();
        StringBuilder stringBuilder = new StringBuilder();
        int i = s.length() - 1, j = t.length() - 1, carry = 0;
        while (i &gt;= 0 || j &gt;= 0 || carry != 0) {
            carry += i &gt;= 0 ? s.charAt(i--) - '0' : 0;
            carry += j &gt;= 0 ? t.charAt(j--) - '0' : 0;
            stack.push(carry % 10);
            carry = carry / 10;
        }
        while (!stack.isEmpty())
            stringBuilder.append(stack.pop());
        return stringBuilder.toString();
    }

如果觉得有用就给个赞吧，还可以关注我的《牛客博客》查看更多的详细题解