NC1 题解 | #大数加法#

题意分析

• 这个题目让我们求出两个很大很大的数的和。

思路分析

思路一 用Python

• 我们知道，目前对于大多数高级语言，都存在着对高精度的处理。所以我们直接使用Python就行了。

• 代码如下**

  • 需要遍历字符串a和b的每个字符，时间复杂度为O(lena+lenb)
  • 需要存储a和b字符串，空间复杂度为O(lena+lenb)

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
# 计算两个数之和
# @param s string字符串 表示第一个整数
# @param t string字符串 表示第二个整数
# @return string字符串
#
class Solution:
    def solve(self , s , t ):
        # write code here
        return int(s)+int(t);

思路二 模拟加法运算

• 如下图
  

• 我们仿照我们小学的时候进行的加法运算的操作，我们先将两个数的数位进行对齐，然后，我们从低位开始进行加法运算，不断得更新进位位，同时余数作为当前的位置上面的数字。最后值得注意的是需要验证最后的进位位是否不为0。

• 代码如下

  • 由于可能需要遍历每一个数字，所以时间复杂度为O(lena+lenb)
  • 需要存储每个字符串，空间复杂度为O(lena+lenb)

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算两个数之和
     * @param s string字符串 表示第一个整数
     * @param t string字符串 表示第二个整数
     * @return string字符串
     */
    string solve(string s, string t) {
        // write code here
        int len1=s.size();
        int len2=t.size();
        // 首先要保证两个数的位数要保持一致
        while(len1<len2){
            s="0"+s;
            len1++;
        }
        while(len1>len2){
            t="0"+t;
            len2++;
        }
        string ans;
        int carry=0;  // 定义一个变量作为进位位
        for(int i=len1-1;i>=0;i--){
            int tmp=(s[i]-'0'+t[i]-'0'+carry);
            ans+=char(tmp%10+'0');
            carry=tmp/10;  // 不断更新进位位
        }
        // 最后还需要特判进位位
        if(carry){
            ans+=(carry+'0');
        }
        reverse(ans.begin(),ans.end());
        return ans;
    }
};