AddStringsOPT [source code]

public class AddStringsOPT {
    public String addStrings(String num1, String num2) {
        char[] ch2 = num2.toCharArray();
        char[] ch1 = num1.toCharArray();
        int i = ch1.length - 1;
        int j = ch2.length - 1;
        int len = i > j ? i + 1 : j + 1;
        int addten = 0;
        int add = 0;
        char[] res = new char[len + 1];
        for (; i >= 0 && j >= 0; i--, j--, len--) {
            add = addten + ch1[i] + ch2[j] - 2 * '0';
            if (add > 9) {
                addten = 1;
                res[len] = (char)(add + '0' - 10);
            } else {
                res[len] = (char)(add + '0');
                addten = 0;
            }
        }
        if (i >= 0) {
            while (i >= 0 && addten != 0) {
                if (ch1[i] == '9') {
                    res[len--] = '0';
                    i--;
                } else {
                    res[len--] = (char)(ch1[i--] + 1);
                    addten = 0;
                    break;
                }
            }
            while (i >= 0) res[len--] = ch1[i--];
        }
        if (j >= 0) {
            while (j >= 0 && addten != 0) {
                if (ch2[j] == '9') {
                    res[len--] = '0';
                    j--;
                } else {
                    res[len--] = (char)(ch2[j--] + 1);
                    addten = 0;
                    break;
                }
            }
            while (j >= 0) res[len--] = ch2[j--];
        }
        if (addten == 1) {
            res[0] = '1';
            return new String(res);
        } else {
            return new String(res, 1, res.length - 1);
        }

    }

    public static void main(String[] args) {
        AddStringsOPT tester = new AddStringsOPT();
        System.out.println(tester.addStrings("123", "932"));
    }
}

这个是 submission 最优解: 22(96). 看这个长度估计又是一个reinvent the wheel 之类的低层实现的方法.

大概砍了一下, 基本就是这样, 避免使用string concatenation, 避免使用 mod 这类的操作. 这个大概看看就行了, 面试的时候要是绕这么深, 估计也是走弯路了, 不看了.

这个解用的是类似我的思路, 不过他对于各方面的处理都简化了不少:

public class Solution {  
    public String addStrings(String num1, String num2) {  
        StringBuilder sb = new StringBuilder();  
        int carry = 0;  
        for(int i = num1.length() - 1, j = num2.length() - 1; i >= 0 || j >= 0 || carry == 1; i--, j--){  
            int x = i < 0 ? 0 : num1.charAt(i) - '0';  
            int y = j < 0 ? 0 : num2.charAt(j) - '0';  
            sb.append((x + y + carry) % 10);  
            carry = (x + y + carry) / 10;  
        }  
        return sb.reverse().toString();  
    }  
}

最后的速度是30(47).
注意他这里并没有用我的外层只使用一个 loopvar, 然后这个单独的 i 再进去分别转换成两个 array 的 index 的思路. 我这个思路确实过于复杂了, 他就直接在同一个 loop 里面同是使用 i,j 两个 var, 然后分别进行处理就行了(除了 termination condition 两者共同参与判断).

这个问题应该可以命名为shared loop问题, 估计以后会经常碰到.

Problem Description

Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2.

Note:

The length of both num1 and num2 is < 5100.
Both num1 and num2 contains only digits 0-9.
Both num1 and num2 does not contain any leading zero.
You must not use any built-in BigInteger library or convert the inputs to integer directly.
Difficulty:Easy
Category:Algorithms
Acceptance:41.24%
Contributor: LeetCode
Companies
google airbnb
Related Topics
math
Similar Questions
Add Two Numbers Multiply Strings