2023年7月17日每日一题--415. 字符串相加

leetcode链接：
415. 字符串相加

题目分析

方案一

class Solution {
    public String addStrings(String num1, String num2) {

        StringBuilder stringBuilder = new StringBuilder();
        int flage = 0, // 进位的标志
            num1Length = num1.length(),
            num2Length = num2.length(),
            maxLength = num1Length > num2Length ? num1Length : num2Length,
            minLength = num1Length < num2Length ? num1Length : num2Length,
            temp = 0;

        for (int i = 0; i < minLength; i++) {
            temp = num1.charAt(num1Length - i - 1) - '0' + num2.charAt(num2Length - i - 1) - '0' + flage;
            stringBuilder.insert(0, temp % 10);
            flage = temp / 10;
        }

        if (num1.length() > num2.length()) {
            for (int i = minLength; i < maxLength; i++) {
                temp = num1.charAt(num1Length - i - 1) - '0' + flage;
                stringBuilder.insert(0, temp % 10);
                flage = temp / 10;
            }
        } else {
            for (int i = minLength; i < maxLength; i++) {
                temp = num2.charAt(num2Length - i - 1) - '0' + flage;
                stringBuilder.insert(0, temp % 10);
                flage = temp / 10;
            }
        }
        if (flage == 1) {
            stringBuilder.insert(0, flage);
        }

        return stringBuilder.toString();
    }
}

结果

解答成功:
执行耗时:3 ms,击败了18.03% 的Java用户
内存消耗:42.5 MB,击败了13.01% 的Java用户

分析

时间复杂度：
O( max(n, m) )

空间复杂度：
O( max(n, m) )

方案一的改进

通过查看官方答案，其使用了StringBuffer的翻转函数，请宽恕我的无知，以下是优化后的代码

class Solution {
    public String addStrings(String num1, String num2) {

        StringBuilder stringBuilder = new StringBuilder();
        int flage = 0, // 进位的标志
            num1Length = num1.length(),
            num2Length = num2.length(),
            maxLength = num1Length > num2Length ? num1Length : num2Length,
            minLength = num1Length < num2Length ? num1Length : num2Length,
            temp = 0;

        for (int i = 0; i < minLength; i++) {
            temp = num1.charAt(num1Length - i - 1) - '0' + num2.charAt(num2Length - i - 1) - '0' + flage;
//            stringBuilder.insert(0, temp % 10);
            stringBuilder.append(temp % 10);
            flage = temp / 10;
        }

        if (num1.length() > num2.length()) {
            for (int i = minLength; i < maxLength; i++) {
                temp = num1.charAt(num1Length - i - 1) - '0' + flage;
//                stringBuilder.insert(0, temp % 10);
                stringBuilder.append(temp % 10);
                flage = temp / 10;
            }
        } else {
            for (int i = minLength; i < maxLength; i++) {
                temp = num2.charAt(num2Length - i - 1) - '0' + flage;
//                stringBuilder.insert(0, temp % 10);
                stringBuilder.append(temp % 10);
                flage = temp / 10;
            }
        }
        if (flage == 1) {
//            stringBuilder.insert(0, flage);
            stringBuilder.append(flage);
        }

        return stringBuilder.reverse().toString();
    }
}

结果

解答成功:
执行耗时:1 ms,击败了100.00% 的Java用户
内存消耗:40.4 MB,击败了84.74% 的Java用户

分析

修改之后，耗时和内存占用均有所降低，尤其是耗时，特别明显。

官方题解

https://leetcode.cn/problems/add-strings/solution/zi-fu-chuan-xiang-jia-by-leetcode-solution/

思想和方案一差不多

class Solution {
    public String addStrings(String num1, String num2) {
        int i = num1.length() - 1, j = num2.length() - 1, add = 0;
        StringBuffer ans = new StringBuffer();
        while (i >= 0 || j >= 0 || add != 0) {
            int x = i >= 0 ? num1.charAt(i) - '0' : 0;
            int y = j >= 0 ? num2.charAt(j) - '0' : 0;
            int result = x + y + add;
            ans.append(result % 10);
            add = result / 10;
            i--;
            j--;
        }
        // 计算完以后的答案需要翻转过来
        ans.reverse();
        return ans.toString();
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/add-strings/solution/zi-fu-chuan-xiang-jia-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。