题目描述

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

样例

12
23

35

算法

(高精度进位加法)

说一些算法实现的注意点吧
1. 对于大整数，我们读入是用string来读入，然后将每一个字符存储到vector中，因为string中是字符，所以在存入vector中的时候一定要注意加上a[i] - '0'。(我每次都忘记加。。然后SE)
2. 存储的时候针对于字符串a b，要倒着来存储，最后输出也是一样的。
3. add()函数中，有一个进位t要考虑，最后如果t不为0，那么还要将它放入C中的，在add()函数中的计算，C是正序的。

时间复杂度

$O(n)$

C++ 代码

#include <iostream>
#include <vector>
#include <string.h>

using namespace std;

const int N = 100010;

vector<int> add(vector<int> &A, vector<int> &B)
{
    if(A.size() < B.size()) return add(B, A);

    int t = 0;
    vector<int> C;
    for(int i = 0; i < A.size(); i ++)
    {
        t += A[i];
        if(i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }

    if(t) C.push_back(1);  // **1

    return C;
}

int main()
{
    string a, b;
    vector<int> A, B;

    cin >> a >> b;

    /*
    for(int i = a.size() - 1; i >= 0; i ++) A.push_back(a[i]);
    for(int i = b.size() - 1; i >= 0; i ++) B.push_back(b[i]);
    */

    for(int i = a.size() - 1; i >= 0; i --) A.push_back(a[i] - '0');
    for(int i = b.size() - 1; i >= 0; i --) B.push_back(b[i] - '0');

    auto C = add(A, B);

    for(int i = C.size() - 1; i >= 0; i --) cout << C[i];

    return 0;
}

算法2

add()函数的另一种写法(其实没有什么本质区别)

C++ 代码

#include <iostream>
#include <vector>

using namespace std;

const int N = 1e5 + 10;

vector<int> add(vector<int> &A, vector<int> &B)
{
    vector<int> C;

    int t = 0;
    for(int i = 0; i < A.size() || i < B.size(); i ++)
    {
        if(i < A.size()) t += A[i];
        if(i < B.size()) t += B[i];

        C.push_back(t % 10);
        t /= 10;  // 看是否有进位
    }

    if(t) C.push_back(1);

    return C;
}

int main()
{
    string a, b;
    vector<int> A, B;

    cin >> a >> b;

    // for(int i = a.size() - 1; i >= 0; i --) A.push_back(a[i]);  // **1  
    // for(int j = b.size() - 1; j >= 0; j --) B.push_back(b[j]);  // **1

    for(int i = a.size() - 1; i >= 0; i --) A.push_back(a[i] - '0');
    for(int j = b.size() - 1; j >= 0; j --) B.push_back(b[j] - '0');

    auto C = add(A, B);

    for(int i = C.size() - 1; i >= 0; i --) printf("%d", C[i]);

    return 0;
}