题解 | #大数乘法#

题目：大数乘法

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

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

示例1：输入："11","99"，返回值："1089"

说明：11*99=1089

解法一：
思路分析：我们首先分析，在正常进行的乘数运算过程中是这样运算的，例如11 * 99，首先用11的个位1去乘99，再加上11的十位10去乘99，具体为：

11*99

99 + 990 = 1089

我们可以使用暴力法去解决问题，所以在具体的运算过程中首先做的基本工作有，设置两个基本指针变量i和j，将字符串s和t的size()大小计算出来，设置一个string类型的res变量，刚开始设置为s和t字符串大小的总和，首先定义为全部是0，依次循环，判断各位与进位之间的关系，最后运算得出结果，当res刚开始有0的话，就将0去掉，最终输出res的字符串类型。

实例分析：输入："11","99"，返回值："1089"

具体C++代码为：

class Solution {
public:
    /**
     *代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param s string字符串 第一个整数
     * @param t string字符串 第二个整数
     * @return string字符串
     */
    string solve(string s, string t) {
        // write code here
        if(s.empty() == true || t.size()== true)
            return "0";
        int len1 = s.size();
        int len2 = t.size();
        string res(len1 + len2,'0');//设置初始变量"0000"
        for(int i = len1 - 1; i >= 0; i--){//从最后一位开始乘
            for(int j = len2 - 1; j >= 0; j--){
                int temp = (s[i] - '0') * (t[j] - '0') + (res[i+j+1] - '0');//计算两个数乘之后加进位的运算
                res[i+j+1] = temp % 10 + '0';//对10取余
                res[i+j] = res[i+j] + temp/10;//进位
            }
        }
        for(int i = 0;i < res.size();i++){ 
            if(res[i] != '0') 
                return res.substr(i);//从指定位置开始，并具有指定的长度。 
        } 
    return res; 
    } 
};

在该算法中，有两个指针变量，故时间复杂度为O(N^2)，空间复杂度为O(1)。

解法二：

思路分析：在java中也有很多库函数用于大数之间的运算，比如BigInteger()函数，BigInteger(byte[] val)：

这个构造函数用于转换一个字节数组包含BigInteger的二进制补码，以二进制表示成一个BigInteger。

BigInteger(int signum, byte[] magnitude)：

此构造函数用于将BigInteger的符号大小表示法转换成一个BigInteger值。

BigInteger(int bitLength, int certainty, Random rnd)

此构造函数用于构造一个随机生成正BigInteger的可能是以指定的bitLength的素数。

该函数Multiply()，Math类的multipleFull(int x，int y)方法用于返回两个参数的精确数学乘积。在参数中，提供了两个整数值，并且此方法以长型表示两个数字的乘积。

具体java代码如下所示：

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

直接调用库函数进行输出，其时间复杂度为O(1)，空间复杂度为O(1)。