题目描述

以字符串的形式读入两个数字，编写一个函数计算它们的和，以字符串形式返回。
（字符串长度不大于100000，保证字符串仅由'0'~'9'这10种字符组成）
示例1
输入："1","99"
返回值："100"
说明：1+99=100

题目分析

根据加法的运算过程可知，需要从字符串的低位开始依次进行加法运算，记录每一位的结果，最后拼接成字符串，如下图。
图片说明
这里主要需要解决两个问题：
①用什么保存计算结果
②明确最后拼接的结果顺序

解题思路

方法1：从字符串尾部计算结果，依次拼接
直接使用StringBuilder来保存计算结果，若是直接使用append方法，则结果是正确结果的倒序（因为从低位开始计算，高位在低位后面），需要将最后的结果进行反转。
或者直接使用insert()方法，将后面高位的计算结果直接拼接在首位，则最后结果不需要反转。

方法2：使用栈来存储结果，再按顺序拼接
根据栈的“先入后出”的特点，可以用栈来保存每位的运算结果，最后使用StringBuilder按导出顺序拼接即可。

代码实现

方法1：从字符串尾部计算结果，依次拼接

public String solve (String s, String t) {
        // write code here
        // 表示字符串的字符位置，需要从低位开始计算
        int s1 = s.length()-1;
        int t1 = t.length()-1;
        // 表示进位
        int carry = 0;
        StringBuilder sb = new StringBuilder();
        while(s1>=0 || t1>=0 || carry > 0){
            int n1 = s1 < 0 ? 0 : (s.charAt(s1--)-'0');
            int n2 = t1 < 0 ? 0 : (t.charAt(t1--)-'0');
            // 计算和
            int sum = n1 + n2 + carry;
            // 计算进位
            carry = sum / 10;
            sum = sum % 10;
            // 从头部插入，保证结果的顺序
            sb.insert(0,sum);
        }
        return sb.toString();

时间复杂度：O(n+m)，n,m为两个字符串的长度，因为需要遍历两个字符串，所以时间复杂度为O(n+m)；
空间复杂度：O(n)，n为两个字符串中长的那个字符串的长度，需要使用额外的n空间来保存计算结果。

方法2：使用栈来存储结果，再按顺序拼接

public String solve (String s, String t) {
        // write code here
        // 表示字符串的字符位置，需要从低位开始计算
        int s1 = s.length()-1;
        int t1 = t.length()-1;
        // 表示进位
        int carry = 0;
        // 使用栈来保存结果，可以按顺序导出
        Stack<Integer> stack = new Stack<>();
        while(s1>=0 || t1>=0 || carry > 0){
            int n1 = s1 < 0 ? 0 : (s.charAt(s1--)-'0');
            int n2 = t1 < 0 ? 0 : (t.charAt(t1--)-'0');
            // 计算和
            int sum = n1 + n2 + carry;
            // 计算进位
            carry = sum / 10;
            sum = sum % 10;
            // 从头部插入，保证结果的顺序
            stack.push(sum);
        }
        StringBuilder sb = new StringBuilder();
        while(!stack.isEmpty()){
            // 从栈中导出结果
            sb.append(stack.pop());
        }
        return sb.toString();
    }

时间复杂度：O(n+m)，n,m为两个字符串的长度，因为需要遍历两个字符串，所以时间复杂度为O(n+m)；
空间复杂度：O(n)，n为两个字符串中长的那个字符串的长度，需要使用额外的2*n空间来保存计算结果。