Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2.
Note:
The length of both num1 and num2 is < 5100.
Both num1 and num2 contains only digits 0-9.
Both num1 and num2 does not contain any leading zero.
You must not use any built-in BigInteger library or convert the inputs to integer directly.
题意: 给定以字符串形式表示的两个非负整数 num1 和 num2, 返回这两个整数的和.
Note:
1. num1 和 num2 的长度都小于 5100.
2. num1 和 num2 只包含 0-9 中的数字.
3. num1 和 num2 不存在最高位为 0 的情况.
4. 不能使用任何内置方法 (如 BigInteger) 或将字符串直接转换为整型.
思路: 同 Add Binary 一题.
直接用程序模拟十进制相加的竖式. 将进位设置成标志位
1. 从后向前遍历, 逐位取出字符串 num1,num2 的数字 a 和 b, 如果长度不足, 就用 0 代替
2. 用 carry 代表进位
3. a + b + carry 除以 10, 取余代表当前位的结果, 取整代表进位
4. 最后循环结束后, 如果进位标志 carry 为 1, 则代表最高位有进位, 对字符串最高位再加 1
思想: 以十进制为例, 在竖式求和里面, 对应位的两个数相加, 横线下面的数相当于除以 10 取余; 进位的数相当于除以 10 取整
例: 95
+ 26
----
121
java 实现如下:
public String addStrings(String num1, String num2) {
int len1 = num1.length();
int len2 = num2.length();
int maxLen = Math.max(len1, len2);
int carry = 0; //carry 表示进位
String sum = "";
for (int i = 0; i < maxLen; i++) {
// 从右往左, 逐位取数字, 长度不足就用 0 代替
int a = i < len1 ? num1.charAt(len1 - 1 - i) - '0': 0;
int b = i < len2 ? num2.charAt(len2 - 1 - i) - '0': 0;
sum = (a + b + carry) % 10 + sum;
carry = (a + b + carry) / 10;
}
if (carry == 1) sum = carry + sum;
return sum;
}
来源: http://www.bubuko.com/infodetail-2481473.html