AcWing 791. 高精度加法

原题链接：https://www.acwing.com/problem/content/793/

模板代码

模板代码的思路是直接将两个数逆序存储，然后从低位向高位加。

// C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A, vector<int> &B)
{
    if (A.size() < B.size()) return add(B, A);

    vector<int> C;
    int t = 0;
    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(t);
    return C;
}

C++版本

自己实现的思路是，顺序存储，然后用两个指针，同时从后向前扫描。

#include <iostream>
#include <string>
#include <vector>


using namespace std;

string x, y;

void cal() {
    vector<int> res;
    int c = 0; // 进位
    int tmp;
    int i = x.length() - 1, j = y.length() - 1;

    for (; i >= 0 && j >= 0; --i, --j) {
        tmp = x[i] - '0' + y[j] - '0' + c;
        c = tmp / 10;
        res.push_back(tmp % 10);
    }

    while (i >= 0) {
        tmp = x[i--] - '0' + c;
        res.push_back(tmp % 10); 
        c = tmp / 10;
    }

    while (j >= 0) {
        tmp = y[j--] - '0' + c;
        res.push_back(tmp % 10);
        c = tmp / 10;
    }

    if (c > 0) res.push_back(c);

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

}

int main() {
    cin >> x;
    cin >> y;
    cal();
    return 0;
}

Java版本

import java.util.*;

class Main {

    public static String x, y;

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        x = s.nextLine();
        y = s.nextLine();
        cal();
    }

    public static void cal() {
        int i = x.length() - 1, j = y.length() - 1;
        int c = 0, tmp = 0;
        ArrayList<Integer> res = new ArrayList<>();
        while (i >= 0 && j >= 0) {
            tmp = x.charAt(i--) - '0' + y.charAt(j--) - '0' + c;
            res.add(tmp % 10);
            c = tmp / 10;
        }
        while (i >= 0) {
            tmp = x.charAt(i--) - '0' + c;
            res.add(tmp % 10);
            c = tmp / 10;
        }
        while (j >= 0) {
            tmp = y.charAt(j--) - '0' + c;
            res.add(tmp % 10);
            c = tmp / 10;
        }
        if (c > 0) res.add(c);

        for (int k = res.size() - 1; k >= 0; --k) {
            System.out.print(res.get(k));
        }
    }
}