Given two non-negative integers, num1 and num2 represented as string, return the sum of num1 and num2 as a string.
You must solve the problem without using any built-in library for handling large integers (such as BigInteger). You must also not convert the inputs to integers directly.
Example 1:
Input: num1 = "11", num2 = "123"
Output: "134"
Example 2:
Input: num1 = "456", num2 = "77"
Output: "533"
Example 3:
Input: num1 = "0", num2 = "0"
Output: "0"
Constraints:
1 <= num1.length, num2.length <= 104num1andnum2consist of only digits.num1andnum2don’t have any leading zeros except for the zero itself.
解题思路
这道题要求做的是，对给定字符串，求和。题目已经对输入做了明确的限制，保证输入是合法的正整数对应的字符串，并且对长度也有限制。
解决思路，就是从最低位开始遍历，维护一个“进位”信息。
public String addStrings(String num1, String num2) {
// no input validation
int num1Ind = num1.length() - 1;
int num2Ind = num2.length() - 1;
int carry = 0;
StringBuilder result = new StringBuilder();
while (num1Ind >= 0 || num2Ind >= 0) {
int a = num1Ind >= 0 ? num1.charAt(num1Ind) - '0' : 0;
int b = num2Ind >= 0 ? num2.charAt(num2Ind) - '0' : 0;
int sum = a + b + carry;
carry = sum / 10;
result.insert(0, (char) ( '0' + sum % 10));
num1Ind--;
num2Ind--;
}
if (carry != 0) {
result.insert(0, (char)('0' + carry));
}
return result.toString();
}
测试用例：
public class AddStringsTest {
private final Solution solution = new Solution();
/**
* Key words:
* - non negative
* - non leading zero, except "0" itself
* - length limited
*/
@Test
public void test() {
doEvaluate(0, 0);
doEvaluate(11, 123);
doEvaluate(456, 77);
doEvaluate(11, 9);
}
private void doEvaluate(int num1, int num2) {
assertEquals(
String.valueOf(num1 + num2),
solution.addStrings(String.valueOf(num1),
String.valueOf(num2)));
}
}
注意的问题
对输入的字符串遍历完成之后，注意检查是否还有“进位”，有的话需要添加到结果中。
「真诚赞赏，手留余香」
Yuanyeex
真诚赞赏，手留余香
使用微信扫描二维码完成支付
