字符串加法
字符串加法
http://www.nowcoder.com/questionTerminal/829ae8987a424bd6b9a95a240ebdb0e3
题目难度：二星
考察点：字符串、高精度
方法：高精度
1.分析：
这个题就是一个二进制的加法，其实在转换一下就是一个高精度的加法，我们就按照实际做加法的方法来进行模拟就可以了，具体如下图：
首先将两个字符串a,b倒序，然后保证字符串a是长度比较小的，即如果a的长度大的话，就跟b进行交换。然后我们就模拟现实中的加法，即每一位相加，如果有进位的话，就用一个变量记录下，等下一位进行相加的时候加上进位，然后保留的显然是相加结果之后对2取余，即保留各位，然后等到遍历完a字符串后，剩下的显然就只有b字符串了， 我们只需要在b字符串上加上一个进位就可以了。最后将得到的串ans在进行逆序，就得到结果了。
算法实现：
(1). 输入两个字符串a和b。 (2). 用上述的方法进行高精度加法，求出ans
(3). 输出进行加法操作之后的结果ans。
2.复杂度分析：
时间复杂度：O(n)空间复杂度：O(n)
3.代码：
#include <bits/stdc++.h>
using namespace std;
string add(string a, string b) {
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
if(a.size() > b.size()) swap(a, b);
int la = a.size(), lb = b.size(), i = 0, c = 0;
string ans = "";
while(i < la) {
int t = a[i]-'0'+b[i]-'0'+c;
c = t / 2;
ans += (t%2+'0');
i++;
}
while(i < lb) {
int t = b[i]-'0'+c;
c = t / 2;
ans += (t%2+'0');
i++;
}
if(c) ans += (c+'0');
reverse(ans.begin(), ans.end());
return ans;
}
int main(){
string a, b; cin>>a>>b;
cout<<add(a, b)<<endl;
return 0;
}
