两个大数相加

题目描述

给定两个正整数，计算它们的和。

输入格式
共两行，每行包含一个整数。

输出格式
共一行，包含所求的和。

数据范围
1≤整数长度≤100000

输入样例：

12
23

输出样例：

35

时间复杂度 O(n)

C++ 代码

#include <iostream>
#include <string>
#include <vector>
using namespace std;
typedef vector<int> vec;

vec add(const vec& a, const vec& b) {
    const int n = a.size(), m = b.size();
    if(n < m) return add(b, a);

    vec c; 
    // 数位和，两个加数对应的数位都加到 sum 上  
    // 0 <= sum <= 19
    int sum = 0;  
    for(int i = 0; i < n; i++) {
        sum += a[i];        
        if(i < m) sum += b[i];
        c.push_back(sum % 10); // 获取该数位的数字
        sum /= 10;             // 获取进位信息
    }
    if(sum) c.push_back(sum);  // 最高位的进位处理
    return c;
}

void init(vec& v, string& s) {
    cin >> s;
    const int n = s.size();
    // 字符串倒序保存，模拟加法运算
    // 加法运算从低数位到高数位处理
    for(int i = n - 1; i >= 0; i--) {
        v.push_back(s[i] - '0');
    }
}  

void show(const vec& v) {
    const int n = v.size();
    for(int i = n - 1; i >= 0; i--) {
        cout << v[i];
    }
    cout << endl;
}

int main() {
    string s1, s2;
    vec a, b, c;
    init(a, s1);
    init(b, s2);
    c = add(a, b);
    show(c);
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;
const int base = 1e9;

vector<int> add(vector<int>& x, vector<int>& y) {
    if (x.size() < y.size()) return add(y, x);

    vector<int> s;
    int t = 0;
    for(int i = 0; i < x.size(); i++) {
        t += x[i];
        if(i < y.size()) t += y[i];
        s.push_back(t % base);
        t /= base;
    }

    if(t) s.push_back(t);
    return s;
}

void init(vector<int>& v) {
    string s;
    cin >> s;
    for(int i = s.size() - 1, j = 0, k = 0, t = 1; i >= 0; i--) {
        k += (s[i] - '0') * t;  
        j++, t *= 10;            
        if(j == 9 || i == 0) {
            v.push_back(k);
            k = j = 0;
            t = 1;
        }
    }
}

int main() {
    vector<int> x, y;
    init(x), init(y); 

    auto s = add(x, y); 

    cout << s.back();    
    for(int i = s.size() - 2; i >= 0; i--) 
        printf("%09d", s[i]);
    cout << endl;

    return 0;
}