Leetcode第415题. 字符串相加

题目描述

https://leetcode.cn/problems/add-strings/

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。

你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。

个人思路

就是模拟加法，从后往前加。

    public String addStrings(String num1, String num2) {
        if(num2.length()==0)return num1;
        if(num1.length()==0)return num2;
        int i=num1.length();
        int j=num2.length();
        int cin=0;
        StringBuilder s=new StringBuilder();
        while (i--!=0 && j--!=0){
            int temp = Integer.parseInt(String.valueOf(num1.charAt(i))) + Integer.parseInt(String.valueOf(num2.charAt(j))) + cin;
            cin=0;
            if(temp >= 10 ) cin++;
            s.append(temp%10);
            if(i==0 || j==0)break;
        }
        while (cin!=0){
            if(i-->0){
                int temp = Integer.parseInt(String.valueOf(num1.charAt(i)))+cin;
                cin=0;
                if(temp >= 10 ) cin++;
                s.append(temp%10);
            }
            if(j-->0){
                int temp = Integer.parseInt(String.valueOf(num2.charAt(j)))+cin;
                cin=0;
                if(temp >= 10 ) cin++;
                s.append(temp%10);
            }
            if(i==0 && j==0){
                s.append(cin);
                cin=0;
            }
        }
        if (i>0){
            s.append(num1.substring(0,i));
        }
        if (j>0){
            s.append(num2.substring(0,j));
        }
        return s.reverse().toString();
    }

优化

在提交就超时之后，我们开始优化代码

  1. 源代码里，我们为了防止下标越界，只要i或者j其中一个等于0就停止运行，然后再将其余剩下的i或j与cin相加之后加入。这里想到另一种方式,直接判断下标，如果要越界直接使用0来代替。
 int digit1 = i >= 0 ? num1.charAt(i) - '0' : 0;
 int digit2 = j >= 0 ? num2.charAt(j) - '0' : 0;
  1. 最后再加一个进位cin就行
  2. 优化之后的代码
 public String addStrings(String num1, String num2) {
        int i = num1.length() - 1;
        int j = num2.length() - 1;
        int cin = 0;
        StringBuilder sb = new StringBuilder();

        while (i >= 0 || j >= 0) {
            int digit1 = i >= 0 ? num1.charAt(i) - '0' : 0;
            int digit2 = j >= 0 ? num2.charAt(j) - '0' : 0;
            int sum = digit1 + digit2 + cin;
            cin = sum / 10;
            sb.append(sum % 10);
            i--;
            j--;
        }

        if (cin != 0) {
            sb.append(cin);
        }

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

最后时间超越100%

总结

如何规避数组下标越界一直是一个问题，学到一个小技巧。