题解 | #大数加法#

题目：大数加法

描述：以字符串的形式读入两个数字，编写一个函数计算它们的和，以字符串形式返回。

（字符串长度不大于100000，保证字符串仅由'0'~'9'这10种字符组成）

示例1：输入："1","99"，返回值："100"，说明：1+99=100

解法一：

思路分析：首先通读题目，我们应该主要理解的是以字符串的形式读入数字，因为两个整数的相加可能会引发溢出的问题，所以用字符串的格式存储字符串s和t，同时判断字符串的长度，设置一个最大值maxlen表示可能的最大长度为多少，最终通过Ascil值的判断，不断相加，确定各位和进位之间的关系。

具体实例分析：输入："1","99"

具体C语言代码如下所示：

/**
 *代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *计算两个数之和
 * @param s string字符串 表示第一个整数
 * @param t string字符串 表示第二个整数
 * @return string字符串
 */
char* solve(char* s, char* t ) {
    //strlen字符串的长度
    int slen = strlen(s);
    int tlen = strlen(t);
    int maxlen = slen > tlen ? slen + 1: tlen + 1;  //判断s和t哪个最长
    char* res = (char *)calloc(maxlen + 1, sizeof(char));
    //calloc()分配所需的内存空间，并返回一个指向它的指针
    int i = 0,j = 0,k = 0;
    int temp = 0;
    for(i = slen - 1,j = tlen - 1,k = maxlen-1;k >= 0;i--,j--,k--){
        int stemp = 0;
        if(i >= 0){
            //for循环判断出所有的字符，然后利用s[]-'0'算出他们的差值
            stemp = s[i] - '0';
        }
        int sstemp = 0;
        if(j >= 0){
            sstemp = t[j] - '0';
        }
        temp += stemp + sstemp;
        res[k] = temp % 10 + '0';
        temp = temp / 10; //满十进一位
    }
    if(*res == '0'){
        return ++res;
    }
    return res;
}

因为只循环执行一次，故时间复杂度为O(N)，空间复杂度为O(N)。

解法二：

思路分析：我们可以直接使用java中的大数操作BigInteger，直接进行大数之间的运算，可以直接得到最终的结果。

资料显示：java中可以使用BigInteger操作大整数，也可以转换进制。如果在操作的时候一个整型数据已经超过了整数的最大类型长度long的话，则此数据就无法装入，所以，此时要使用BigInteger类进行操作。这些大数都会以字符串的形式传入。

其具体java代码如下所示：

import java.util.*;
import java.math.*;
 
public class Solution {
    /**
     *代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *计算两个数之和
     * @param s string字符串 表示第一个整数
     * @param t string字符串 表示第二个整数
     * @return string字符串
     */
    public String solve (String s, String t) {
        // write code here
        BigInteger biginteger1 = new BigInteger(s);
        BigInteger biginteger2 = new BigInteger(t);
        
        return biginteger1.add(biginteger2).toString();
    }
}

同时也可以使用python直接进行输出：

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

因为是直接调用的函数，所以其时间复杂度与空间复杂度均为O(1)。