首页 > 大数相加(C++)
头像
牛客205471383号
编辑于 2020-11-27 13:33
+ 关注

大数相加(C++)

#include <string>
#include <vector>
#include <cstdlib>

// 非负大整数相加
// 思路: 
// 1. 翻转两个字符串。
// 2. 依次相加两数的各位的,存储至vector<int>中,注意符数转换。
// 3. 依次对vector<int>中每个不小于10的数,保留个位,进位1加到后一位置的数中,最终到容器尾部若还有进位,要扩充一个位置。
// 4. 将最终的vector<int>每位置数字经数传转换并存储到一个string中。
// 5. 将得到的string倒序后输出。

int char2int(char c); // 符数转换
char int2char(int i); // 数符转换

using namespace std;
string sum2big(string& strLeft, string& strRight){
// flip
reverse(strLeft.begin(), strLeft.end());
reverse(strRight.begin(), strRight.end());

// length
size_t ll = strLeft.length();
size_t lr = strRight.length();
size_t loopMax = max(ll, lr);
size_t loopMin = min(ll, lr);
if (loopMin==0)
return "";

// 依次相加两数的各位的,存储至vector<int>中,注意符数转换。
bool llgreater = loopMax <= ll;
vector<int> sumPerPos;
int i = 0;
while (i<loopMin) {
sumPerPos.push_back(char2int(strLeft[i])+char2int(strRight[i]));
i++;
}

// 对于位数较长的直接挪过来
if (llgreater) {
while (i++<loopMax) {
sumPerPos.push_back(char2int(strLeft[i]));
}
} else {
while (i++<loopMax) {
sumPerPos.push_back(char2int(strRight[i]));
}
}


// 依次对vector<int>中每个不小于10的数,保留个位,进位1加到后一位置的数中,最终到容器尾部若还有进位,扩充一个位置。
bool append = false;
for (int j = 0; j < loopMax; j++) {
if (sumPerPos[j]>=10) {
sumPerPos[j] -= 10;
if (j+1 < loopMax) {
sumPerPos[j+1] += 1;
} else {
sumPerPos.push_back(1);
append = true;
}
}
}

// 将最终的vector<int>每位置数字经数传转换并存储到一个string中。
size_t newLen = append ? loopMax+1 : loopMax;
string newStr;
int k = 0;
while(k < newLen){
newStr.push_back(int2char(sumPerPos[k++]));
}

// 倒序后输出
reverse(newStr.begin(), newStr.end());
return newStr;
}

int char2int(char c){ return c - '0'; } // 符数转换
char int2char(int i){ return i + '0'; } // 数符转换


全部评论

(0) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

近期精华帖

热门推荐