Leetcode415.字符串相加

Leetcode415.字符串相加

1.题目描述

给定两个字符串形式的非负整数 num1 和num2 ,计算它们的和。

注意:
num1 和num2 的长度都小于 5100.
num1 和num2 都只包含数字 0-9.
num1 和num2 都不包含任何前导零。
你不能使用任何內建 BigInteger 库, 也不能直接将输入的字符串转换为整数形式。

2.解答

这道题将测试用例已经限制在了很小的范围,输入字符串都是纯数字,而且还不包括前导0,不需要考虑太多的其他情况,实现逻辑也不是很复杂,但是在String类的一个api调用上还不是很熟练

思路:保证num1的长度比num2大,否则调换位置重新调用方法,将两个字符串的最后一个字符分别取出并进行相加运算,然后拼接到StringBuilder中,因为是单线程操作,所以这里我并没有选用StringBuffer,使用extra保存每一次的进位,需要特殊处理的就是可能最后一次循环的extra仍然是0,例如比较长的第一位是9,但是却收到上一次extra的进位,这是extra更新为1,需要继续拼接到StringBuilder的后面,最后将sd进行反转并转换为字符串即可

代码实现:

class Solution {
    public String addStrings(String num1, String num2) {
        if(num1 == null || num2 == null)  return null;
        int len1 = num1.length();
        int len2 = num2.length();
        if(len1 == 0)    return num2;
        if(len2 == 0)   return num1;
        if(len1 < len2) return addStrings(num2,num1);
        StringBuilder sd = new StringBuilder();
        int extra = 0;
        while(--len1 >= 0){
            while(--len2 >= 0){
                int sum =  (num1.charAt(len1) - '0')
                 + (num2.charAt(len2) - '0') + extra;
                if(sum / 10 == 1){
                    extra = 1;
                }else{
                    extra = 0;
                }   
                 sd.append(String.valueOf(sum%10));                 
                 len1--;
            }
            //比较短的字符串已经相加完毕
            if(len1 < 0){
                if(extra == 1)  sd.append(String.valueOf(extra));
                return sd.reverse().toString();
            }
            int sum = (num1.charAt(len1)-'0') + extra;
            if(sum / 10 == 1){
                    extra = 1;
            }else{
                extra = 0;
            }   
            sd.append(String.valueOf(sum%10));            
        }
        if(extra == 1){
            sd.append(String.valueOf(extra));
        }
        return sd.reverse().toString();
    }
}

加下来见识一种非常高端大气上档次的写法,总体的思路和我上面是一样的,但是上面的代码写完之后我自己都闲啰嗦了,除了这道题目以外,链表的相加,或者是二进制的相加都可以使用这种格式,

class Solution {
    public String addStrings(String num1, String num2) {
        StringBuilder sd = new StringBuilder();
        int carry = 0, i = num1.length()-1, j = num2.length()-1;
        while(i >= 0 || j >= 0 || carry != 0){
            if(i >= 0)  carry += num1.charAt(i--) - '0';
            if(j >= 0)  carry += num2.charAt(j--) - '0';
            sd.append(carry%10);
            carry /= 10;
        }
        return sd.reverse().toString();
    }
}

👍👍👍

这道题的另外一个收获就是提醒我需要复习一下这一块的API了,主要就是String和int之间的相互转换,还有int和char之间的相互转换

String转int
//这里的String默认都是整数字符串,否则会报错

  • int i = Integer.parseInt(str)
  • int i = Integer.valueOf(str).intValue();
    其实吧,我觉的把intValue()方法去掉也是可以的,因为Java是支持自动拆箱的,反正这样写还是比较严谨的吧

int转String

  • String s = String.valueOf(i);
  • String s = Integer.toString();
  • String s = i + "";

另外还有一个小技巧,如何将char类型的数字转换为int类型的数组呢,要求字面值一样?
刚开始我就直接这样做的:💣
int i = Integer.valueOf(str.charAt(index));
如果字符串为"123",索引index为2,那么目标输出为3,可是结果不是这样的,输出的51,为啥子嘞?
查看Integer类的api,Integer.valueOf()方法只支持这三种参数:
image.png
那么如果我们将一个char字符作为输入的话,那么就会自动向上转型为int,转换的结果也就是对应的ascii码
一个好用的方法是这样的:
int i = str.charAt(index) - '0'
当然还有其他的方法,但是还是推荐使用这种,为了知识的全面性这里做一个介绍:
Integer.parseInt(String.valueOf('1'));
Integer.parseInt(new String("1"));
//String类的valueOf()方法支持的参数可是非常广泛的