LeetCode415 Add Strings

文章目录
  1. 1. 描述
  2. 2. 样例
  3. 3. 思路
  4. 4. 代码

描述

Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2.

Note:

  1. The length of both num1 and num2 is < 5100.
  2. Both num1 and num2 contains only digits 0-9.
  3. Both num1 and num2 does not contain any leading zero.
  4. You must not use any built-in BigInteger library or convert the inputs to integer directly.

样例

1
2
3
4
5
Input:
num1 = "123"
num2 = "456"
Output:
"579"

思路

给两个以字符串表示的非负数num1num2,返回其和。

模拟一遍加法的过程即可。

$sum[i] = (num1[i] + num2[i] + carry[i-1]) \% 10$

$carry[i] = (num1[i] + num2[i] + carry[i-1]) / 10$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
string addStrings(string num1, string num2) {
string ans;
int a, b, carry = 0;
int n = num1.size(), m = num2.size(), len = max(n, m);
for (int i = 0; i < len; ++i) {
a = i < n ? num1[n-1-i] - '0' : 0;
b = i < m ? num2[m-1-i] - '0' : 0;
ans += char(((a + b + carry) % 10) + '0');
carry = (a + b + carry) / 10;
}
if (carry > 0) ans += char(carry + '0');
reverse(ans.begin(), ans.end());
return ans;
}
};
分享到 评论