题解 | #高精度整数加法#

HJ57 高精度整数加法

题目描述

输入两个用字符串 str 表示的整数，求它们所表示的数之和。

方法一：数字转字符方法

解题思路

针对方法一，我们直接将所给的大数用字符数组进行存储，首先将字符串倒置，然后对应位相加，在没对齐的地方我们补上0即可。然后进行相加，对于满10进1，在这里不过多叙述其操作。

解题代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    string str1,str2;
    while(cin>>str1>>str2)
    {
        vector<char> res;//用于保存结果
        vector<char> num1;
        vector<char> num2;
        for(int i=str1.size()-1;i>=0;i--)
        {   //倒序存储字符
            num1.push_back(str1[i]);
        }
        for(int i=str2.size()-1;i>=0;i--)
        {   //倒序存储字符
            num2.push_back(str2[i]);
        }
        int len1=num1.size();
        int len2=num2.size();
        //将两个字符串统一长度，高位补0
        if(num1.size()>num2.size())
        {
            for(int i=0;i<len1-len2;i++)
            {
                num2.push_back('0');
            }
        }
        else
        {
            for(int i=0;i<len2-len1;i++)
            {
                num1.push_back('0');
            }
        }
        int in=0;//用于保存进位信息
        for(int i=0;i<num1.size();i++)
        {
            int temp=num1[i]-'0'+num2[i]-'0'+in;//当前位置为两个字符相加再加上进位
            res.push_back(temp%10+'0');
            in=temp/10;//保存进位记录
            
        }
        if(in)
        {//若最后还有进位，该进位也要输出
            res.push_back(in+'0');
        }
        reverse(res.begin(),res.end());//倒置vector，让高位位于vector的开头
        for(auto &i:res)
        {
            cout<<i;
        }
        cout<<endl;
    }
    return 0;
}

复杂度分析

时间复杂度：一层循环，时间复杂度为$O(N)O(N)$。

空间复杂度：使用vector，引入新的额外内存地址空间，因此空间复杂度为$O(N)O(N)$

方法二：Java大数解法

解题思路

基于方法一，我们直接使用Java给的大数类进行问题的解决。使用BigInteger类中的add()方法，具体参考一下代码。

解题代码

import java.math.BigInteger;
import java.util.Scanner;
public class Main{
    public static void main(String[] args)
    {
        Scanner in=new Scanner(System.in);
        while(in.hasNext())
        {
            String str1 = in.next();
            String str2 = in.next();
            BigInteger num1=new BigInteger(str1);//将字符串1转换为大整数
            BigInteger num2=new BigInteger(str2);//将字符串2转换为大整数
            System.out.println(num1.add(num2));//输出两个大整数相加的结果
        }
    }
}

复杂度分析

时间复杂度：对输入数据进行一层循环，时间复杂度为$O(N)O(N)$

空间复杂度：存储结果时申请额外的内存地址空间，因此空间复杂度为$O(N)O(N)$