题目:大数加法   描述:以字符串的形式读入两个数字,编写一个函数计算它们的和,以字符串形式返回。    (字符串长度不大于100000,保证字符串仅由'0'~'9'这10种字符组成)    示例1:输入:"1","99",返回值:"100",说明:1+99=100   解法一:     思路分析:首先通读题目,我们应该主要理解的是以字符串的形式读入数字,因为两个整数的相加可能会引发溢出的问题,所以用字符串的格式存储字符串s和t,同时判断字符串的长度,设置一个最大值maxlen表示可能的最大长度为多少,最终通过Ascil值的判断,不断相加,确定各位和进位之间的关系。   具体实例分析:输入:"1","99"                        数字                                                   “1”                         “99”                               首先设置slen和tlen表示具体长度,maxlen表示最大长度,设置连续的存储空间                               个位上的判断                         1 + 9 = 10,有进位,所以个位对10取余为0                               十位上的判断                         进位1 + 9 = 10,有进位,该位数字为0                               百位                         进位为1                               最后的返回值为“100”                     具体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)。 
点赞 18
评论 2
全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务