389,两个超级大数相加

389,两个超级大数相加

If you want the rainbow, you have to deal with the rain.

你若想要彩虹,必须经历风雨。

 

问题描述

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

 

注意:

num1 和num2 的长度都小于 5100.

num1 和num2 都只包含数字 0-9.

num1 和num2 都不包含任何前导零。

你不能使用任何內建 BigInteger 库, 也不能直接将输入的字符串转换为整数形式。

 

示例 1:

"12345678901278"+"234"="12345678901512"

问题分析

实际上这道题求的是两个字符串相加,我们就用两个很短的字符串"12367"+"89"为例画个图来看下是怎么计算的

389,两个超级大数相加

它相当于两个字符串从最右边开始相加,比如我们要计算num1字符串的最右边的那个数字和num2字符串最右边的那个字符相加

  •  
int i = num1.length() - 1, j = num2.length() - 1;int x = num1.charAt(i) - '0';int y = num2.charAt(j) - '0';int sum = x + y;

把计算的结果放到一个新的字符串后面,但字符串每一位只能保存一位数字,而我们相加的结果sum可能是个两位数,所以这里我们只取他的个位数,十位数要往前进一位。比如我们要计算num1和num2的倒数第二位

  •  
int x = num1.charAt(i - 1) - '0';int y = num2.charAt(j - 1) - '0';int sum = x + y + carry;

carry就是上一步相加结果的进位,上一步如果进位了就是1,如果没进位就是0。搞懂了上面的相加过程,剩下的就是一些边界条件的判断。最后不要忘了对字符串进行反转,因为我们相加的时候是从num1和num2的尾部开始加的,下面我们来看下完整代码

  •  
public String addStrings(String num1, String num2) {    StringBuilder s = new StringBuilder();    int i = num1.length() - 1, j = num2.length() - 1, carry = 0;    while (i >= 0 || j >= 0 || carry != 0) {        int x = i < 0 ? 0 : num1.charAt(i--) - '0';        int y = j < 0 ? 0 : num2.charAt(j--) - '0';        int sum = x + y + carry;        s.append(sum % 10);//添加到字符串尾部        carry = sum / 10;    }    return s.reverse().toString();//对字符串反转}

 

从头部插入

上面是插入到字符串的尾部,最后再反转。实际上我们在计算的时候还可以先插入到字符串的头部,最后直接返回即可,不需要再反转了,代码和上面差不多,我们来看下

  •  
public String addStrings(String num1, String num2) {    StringBuilder s = new StringBuilder();    int carry = 0, i = num1.length() - 1, j = num2.length() - 1;    while (i >= 0 || j >= 0 || carry != 0) {        int x = i < 0 ? 0 : num1.charAt(i--) - '0';        int y = j < 0 ? 0 : num2.charAt(j--) - '0';        int sum = x + y + carry;        s.insert(0, sum % 10);//插入到s字符串的第一个位置        carry = sum / 10;    }    return s.toString();}

 

使用栈来解决

我们还可以先把相加的结果放到一个栈中,最后再一个个出栈。其实也是换汤不换药,代码都差不多,我们来看下

  •  
public String addStrings(String num1, String num2) {    Stack<Integer> stack = new Stack<>();    StringBuilder sb = new StringBuilder();    int i = num1.length() - 1, j = num2.length() - 1, carry = 0;    while (i >= 0 || j >= 0 || carry != 0) {        carry += i >= 0 ? num1.charAt(i--) - '0' : 0;        carry += j >= 0 ? num2.charAt(j--) - '0' : 0;        stack.push(carry % 10);        carry = carry / 10;    }    while (!stack.isEmpty())        sb.append(stack.pop());    return sb.toString();}

 

递归的方式解决

除了上面介绍的几种以外,我们还可以把它改为递归的方式

  •  
public String addStrings(String num1, String num2) {    return addBinaryHelper(num1, num1.length() - 1, num2, num2.length() - 1, 0);}
public String addBinaryHelper(String num1, int indexA, String num2, int indexB, int carry) { if (indexA < 0 && indexB < 0 && carry == 0) return ""; carry += indexA < 0 ? 0 : num1.charAt(indexA--) - '0'; carry += indexB < 0 ? 0 : num2.charAt(indexB--) - '0'; int digit = carry % 10; carry = carry / 10; String res = addBinaryHelper(num1, indexA, num2, indexB, carry); return res + digit;}

 

总结

这题非常简单,解题思路大同小异,都是先从两个字符串的最后一位开始相加,只不过写的时候会有多种方式。

 

 

389,两个超级大数相加

385,位1的个数系列(二)

384,整数反转

383,不使用“+”,“-”,“×”,“÷”实现四则运算

380,缺失的第一个正数(中)

 

 

389,两个超级大数相加

长按上图,识别图中二维码之后即可关注。

 

如果喜欢这篇文章就点个"在看"吧

上一篇:430,剑指 Offer-动态规划求正则表达式匹配


下一篇:纪念一次面试机试失败的题目: