AcWing791高精度加法

AcWing791高精度加法

题目：

题目大意：

? 高精度加法（数据很大）

数据范围：

如图所示

思路：

? 模拟加法过程，从低位开始相加，在每一位相加过程中，使用k = k + numa[i] + numb[i] (i,j不能越界，越界就不加了)来表示这一次加法的结果，然后这一位就是c[i] = k%10，则对下一位的进位为k/10。注意遍历完numa,numb后，可能存在一位进位，要加上。

代码：

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    public static List<Integer> add(List<Integer> numa, List<Integer> numb){
        List<Integer> c = new ArrayList<>();
        int k = 0;
        for (int i = 0; i < numa.size() || i < numb.size(); i ++ ){
            if (i < numa.size()) k += numa.get(i);
            if (i < numb.size()) k += numb.get(i);
            c.add(k % 10);
            k /= 10;
        }
        if (k == 1)
            c.add(1);
        return c;
    }

    public static void main(String[] args) {
        Scanner scanner =  new Scanner(System.in);
        String a = scanner.next();
        String b = scanner.next();
        List<Integer> numa = new ArrayList<>(), numb = new ArrayList<>();
        for (int i = a.length() - 1; i >= 0; i -- ){
            numa.add(a.charAt(i) - '0');
        }
        for (int i = b.length() - 1; i >= 0; i -- ){
            numb.add(b.charAt(i) - '0');
        }
        List<Integer> c = add(numa, numb);
        for (int i = c.size() - 1; i >= 0; i -- ){
            System.out.print(c.get(i));
        }
    }
}

时空复杂度分析等：

• 时间复杂度 : O(n)

• 空间复杂度 : O(n)

题目链接：

791. 高精度加法 - AcWing题库