这是第68篇LeetCode题解 大数加法
昨天的题目大数乘法中涉及到了大数加法，但是那个大数加法写的实在不够优雅，而且效率不够高，因此今天专门做一道大数加法的题目。
1 题目描述
给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。注意：
- num1 和num2 的长度都小于 5100.
- num1 和num2 都只包含数字 0-9.
- num1 和num2 都不包含任何前导零。
- 你不能使用任何內建 BigInteger 库， 也不能直接将输入的字符串转换为整数形式。
2 题解
按照加法规则，需要将两个整数按照个位对齐，从右往左进行计算。在对字符数组进行加法的时候也是一样的，因此首先要将两个字符串以各位为基准对齐，这里有两种基本的方法：
- 将两个字符串逆序之后再相加，相加得到的字符串再逆序即可(这是常规的链表加法的解法)
- 找到较短的字符串，在较短字符串前面补0使得两个字符串的长度相同之后进行计算
这里使用第1种思路，我使用空间换时间的方式，定义3个整数数组分别保存被加数、jia数和最终的和，数组a和b保存逆序之后的结果，再将加法的结果保存在整数数组c中，最终的代码如下：
class Solution {
public:
string addStrings(string num1, string num2) {
vector<int> a(5105, 0), b(5105, 0), c(5105, 0);
int la = num1.length();
int lb = num2.length();
int lc = max(la, lb);
for (int i = 0; i 1] = num1[i] - '0';
for (int i = 0; i 1] = num2[i] - '0';
for (int i = 0; i c[i] += a[i] + b[i];
c[i + 1] = c[i] / 10;
c[i] %= 10;
}
string ret;
if (c[lc] > 0) lc += 1;
for (int i = lc - 1; i >= 0; i--) ret.append(to_string(c[i]));
return ret;
}
};
转播
