题目来源：牛客网
1、问题描述以字符串的形式读入两个数字，编写一个函数计算它们的和，以字符串形式返回。
数据范围：s.length,t.length le 100000s.length,t.length≤100000，字符串仅由’0’~‘9’构成
要求：时间复杂度 O(n)O(n)
示例：
思路：模拟加法过程
（1）先确定循环次数，取最短字符串长度为循环次数
（2）在循环中逐位计算，记得保存进制位，直到计算循环结束
（3）计算多出来的字串和进制位之间的加法计算，同样还要保存进制位
（4）循环结束后还要检测进制位是否为0，不为0还要加上进制位
class Solution {
public:
string solve(string s, string t) {
if(s.empty()){
return t;
}else if(t.empty()){
return s;
}
// write code here
int i=0;
int sum=0;
string ss="";
int n=s.size()-1,m=t.size()-1;
while(n>=0&&m>=0){
sum=s[n]-'0'+t[m]-'0'+i;
if(sum>=10){
sum-=10;
i=1;
}else{
i=0;
}
char sh=sum+'0';
ss.insert(ss.begin(),sh);
n--;
m--;
}
while(n>=0){
sum=s[n]-'0'+i;
if(sum>=10){
sum-=10;
i=1;
}else{
i=0;
}
char sh=sum+'0';
ss.insert(ss.begin(),sh);
n--;
}
while(m>=0){
sum=t[m]-'0'+i;
if(sum>=10){
sum-=10;
i=1;
}else{
i=0;
}
char sh=sum+'0';
ss.insert(ss.begin(),sh);
m--;
}
if(i==1){
ss.insert(ss.begin(),i+'0');
}
return ss;
}
};
大数乘法
题目来源：牛客网
1、题目描述以字符串的形式读入两个数字，编写一个函数计算它们的乘积，以字符串形式返回。
数据范围： 读入的数字大小满足 0 le n le 10^{1000}0≤n≤10 1000
要求：空间复杂度 O(n)O(n)，时间复杂度 O(n^2)O(n 2 )
思路：模拟乘法过程+大数加法
（1）从字符串s尾部开始取字符
（2）将拿到的字符去和字符串s逐位计算，保存进制位，将最后结果保存在字符换str中
（3）检测进制位是不是为0，不为0添加进制位
（4）扩大str 在str后边添加s.size()-1-i个0
（5）将扩大后的字符串str和ss进行大数加法运算结果保存在ss中
（6） 逐位拿到字符串s字符和字符串t计算，并进行大数加法
class Solution {
public:
string solveadd(string s, string t) {
if (s.empty()) {
return t;
}
else if (t.empty()) {
return s;
}
// write code here
int i = 0;
int sum = 0;
string ss = "";
int n = s.size() - 1, m = t.size() - 1;
while (n >= 0 && m >= 0) {
sum = s[n] - '0' + t[m] - '0' + i;
if (sum >= 10) {
sum -= 10;
i = 1;
}
else {
i = 0;
}
char sh = sum + '0';
ss.insert(ss.begin(), sh);
n--;
m--;
}
while (n >= 0) {
sum = s[n] - '0' + i;
if (sum >= 10) {
sum -= 10;
i = 1;
}
else {
i = 0;
}
char sh = sum + '0';
ss.insert(ss.begin(), sh);
n--;
}
while (m >= 0) {
sum = t[m] - '0' + i;
if (sum >= 10) {
sum -= 10;
i = 1;
}
else {
i = 0;
}
char sh = sum + '0';
ss.insert(ss.begin(), sh);
m--;
}
if (i == 1) {
ss.insert(ss.begin(), i + '0');
}
return ss;
}
string solve(string s, string t) {
if (s.size() == 1 && s[0] == '0') {
return "0";
}
if (t.size() == 1 && t[0] == '0') {
return "0";
}
// write code here
string ss = "";
for (int i = t.size() - 1;i >= 0;i--) {
string str = "";
int m = 0;
for (int j = s.size() - 1;j >= 0;j--) {
int sum = (t[i] - '0') * (s[j] - '0') + m;
if (sum >= 10) {
m = sum / 10;
sum %= 10;
}
else {
m = 0;
}
char ch = sum + '0';
str.insert(str.begin(), ch);
}
if (m > 0) {
char ch = m + '0';
str.insert(str.begin(), ch);
}
int n = t.size() - 1 - i;
//扩大str
while(n--) {
str.push_back('0');
}
//大数相加
ss = solveadd(ss, str);
}
return ss;
}
};
