题解 | #大数加法#

大数加法

http://www.nowcoder.com/practice/11ae12e8c6fe48f883cad618c2e81475

算法思想

通过遍历两个字符串的字符，使其相加有进位就标记。

当遍历次数大于某个字符串的长度：

当进位标识符 flag = 1时

如果字符串继续遍历的字符为 9时，将"0"放进缓冲区并设置flag = 1。

如果字符串继续遍历的字符不为 9时，将相加结果放入缓存区并设置flag = 0。
当进位标识符 flag = 0时

将后续需要遍历的字符直接放入缓存区并退出循环。

退出遍历，检查进位标识为是否还为 1，防止后续字符都为 9 的情况没有进位。

最好时间复杂度： $O (1)$

最坏时间复杂度： $O (n)$

平均时间复杂度： $O (n)$

空间复杂度： $O (1)$

代码实现


class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算两个数之和
     * @param s string字符串 表示第一个整数
     * @param t string字符串 表示第二个整数
     * @return string字符串
     */
    public static String add(String s, String t){
        int sLen = s.length();
        int tLen = t.length();
        int flag = 0;
        int result = 0;
        StringBuffer b = new StringBuffer();
        for(int i=0;i<(sLen>tLen?sLen:tLen);i++){
            if(i<sLen&&i<tLen){
                result = s.charAt(sLen-i-1)+t.charAt(tLen-i-1) + flag - 96;
                flag = 0;
                if(result>=10)flag = 1;
                b.insert(0, result%10);
            }else{
                if(flag==1){
                    if(sLen>tLen&&s.charAt(sLen-i-1)==57){
                        b.insert(0, "0");
                        // b.append("0");
                    }else if(sLen<tLen&&t.charAt(tLen-i-1)==57){ 
                        b.insert(0, "0");
                        // b.append("0");
                    }else{
                        b.insert(0, s.charAt(sLen-i-1)+flag-48);
                        // b.append(s.charAt(i)+flag-48);
                        flag = 0;
                    }
                } else {
                    b.insert(0, (sLen>tLen?s:t).substring(0, (sLen>tLen?sLen:tLen)-i));
                    // b.append((sLen>tLen?s:t).substring(i, (sLen>tLen?sLen:tLen)));
                    break;
                }
            }
        }
        if(flag == 1)b.insert(0, "1");
        return b.substring(0, b.length());
    }
    public String solve (String s, String t) {
        // write code here
        if(s.length()<1&&t.length()<1)return "0";
        else if(s.length()<1)return t;
        else if(t.length()<1)return s;;
        return add(s, t);
    }
}