1. 题目描述
题目链接：415. 字符串相加
2. 解题思路
字符串相加，又名大整数相加，或者大数运算。
就是和我们平时计算两个数的和一样，我们从两个字符串的最后一个数字开始进行相加，也就是 end - 1 的位置开始相加，并设置一个变量 carry 记录是否需要进位（ carry 初始化为 0）。
这样一来，两个字符串相加的时候，每一位置的数字 = num1 对应位置的数字 + num2 对应位置的数字 + carry 进位变量。
若相加后，该位置的数字大于 9，则说明需要进位，这时我们设置进位变量 carry 为 1（两个数字相加，最多只能进位 1），并将该位置的数字减去 10 后的结果作为相加后该位置的数字即可。如此进行下去，直到两个字符串都遍历完毕即可。
特别注意，两个字符串相加结束后还需要判断进位变量是否为 1，若为 1，则需要头插一个字符 1 到最终的字符串中。
3. 代码实现
我们每得到一个位置（个位、十位、百位…）的结果就需要头插一个数字到最终的字符串中。
而头插的代价是比较大的，因为我们每次进行头插就需要将所有的数据都向后挪动一位，留出最前面的位置以供插入，这种算法的时间复杂度达到
O
(
N
)
O(N)
O(N)。
所以，我们可以将得到的每一位数字都尾插到字符串后面，只需最后进行一次字符串反转即可。
代码示例
class Solution {
public:
string addStrings(string num1, string num2) {
int end1 = num1.size() - 1;
int end2 = num2.size() - 1;
int carry = 0; //进位符
string retStr; //存储相加之后的结果
// num1和num2都遍历完以后，才终止循环
while (end1 >= 0 || end2 >= 0) {
int val1 = end1 >= 0 ? num1[end1] - '0' : 0;
int val2 = end2 >= 0 ? num2[end2] - '0' : 0;
int ret = val1 + val2 + carry;
if (ret > 9) { //判断ret是否需要进位
ret -= 10;
carry = 1;
}
else {
carry = 0;
}
retStr += ('0' + ret); //尾插
--end1;
--end2;
}
if (carry == 1) { //如果carry为1，说明还要进位
retStr += '1';
}
reverse(retStr.begin(), retStr.end()); //反转字符串
return retStr;
}
};
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/80841.html
