赞
踩
大数加法
以字符串的形式读入两个数字,编写一个函数计算它们的和,以字符串形式返回。
数据范围:length<10000,字符串仅由’0’~‘9’构成
要求: 空间复杂度 O(1)(仅在传入字符串上操作),时间复杂度 O(n)
示例1
输入:
“1”,“99”
返回值:
“100”
说明:
1+99=100
示例2
输入:
“114514”,""
复制
返回值:
“114514”
思路:从字符串后面往前加,每次相加一次,下标减1,直到某字符串消耗完 就用0来加。
public class BigNumAdd { public static String solve (String s, String t) { StringBuilder stringBuilder = new StringBuilder(); //x,y从两个字符串的最后一数字开始,jinwei是进位 int i=s.length()-1,j=t.length()-1,jinwei=0; //每用掉一次就i--,y--,当某个字符串先没有数了 就用0来加。 //可能两边都没有数了,但是jinwei还是>0,所以还要进来一次 while (i>=0 || j>=0 || jinwei>0){ int x=i<0?0:s.charAt(i--)-'0'; int y=j<0?0:t.charAt(j--)-'0'; int sum =x+y+jinwei; // 加入sum个位上的数,每次从头部插入就不用逆序返回了 stringBuilder.insert(0,sum%10); //进位 sum不满10就为0 jinwei=sum/10; } return stringBuilder.toString(); } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。