算法leetcode｜43. 字符串相乘（rust重拳出击）

文章目录

43. 字符串相乘：

给定两个以字符串形式表示的非负整数

num1

和

num2

，返回

num1

和

num2

的乘积，它们的乘积也表示为字符串形式。

注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

样例 1：

输入: 
    num1 = "2", num2 = "3"
    
输出: 
    "6"

样例 2：

输入: 
    num1 = "123", num2 = "456"
    
输出: 
    "56088"

提示：

• 1 <= num1.length, num2.length <= 200
• num1 和 num2 只能由数字组成。
• num1 和 num2 都不包含任何前导零，除了数字0本身。

分析：

• 面对这道算法题目，二当家的陷入了沉思。
• 看了题意就是不允许我们直接将输入的两个数转成数字，然后直接用乘法API，那我们就模拟大数乘法就可以了。
• 想起了小学做数学乘法，先学9*9乘法表，之后的乘法都是“分治”为个位数的乘法，再把结果加起来。

题解：

rust

implSolution{pubfnmultiply(num1:String, num2:String)->String{if num1 =="0"|| num2 =="0"{return"0".to_owned();}let(m, n)=(num1.len(), num2.len());letmut ans_arr =vec![0; m + n -1];
        num1.as_bytes().iter().enumerate().for_each(|(i1,&c1)|{
            num2.as_bytes().iter().enumerate().for_each(|(i2,&c2)|{
                ans_arr[i1 + i2]+=((c1 -b'0')*(c2 -b'0'))asu16;});});letmut carry =0;letmut ans =Vec::with_capacity(m + n);
        ans_arr.iter().rev().for_each(|&c|{letmut b = c + carry;
            carry = b /10;
            b %=10;
            ans.push(b asu8+b'0');});if carry >0{
            ans.push(carry asu8+b'0');}
        ans.reverse();String::from_utf8(ans).unwrap()}}

go

funcmultiply(num1 string, num2 string)string{if num1 =="0"|| num2 =="0"{return"0"}
    m, n :=len(num1),len(num2)
    ansArr :=make([]int, m+n)for i1, c1 :=range num1 {for i2, c2 :=range num2 {
            ansArr[i1+i2+1]+=int(c1-'0')*int(c2-'0')}}for i := m + n -1; i >0; i--{
        ansArr[i-1]+= ansArr[i]/10
        ansArr[i]%=10}
    ans :=""
    idx :=0if ansArr[0]==0{
        idx =1}for; idx < m+n; idx++{
        ans += strconv.Itoa(ansArr[idx])}return ans
}

c++

classSolution{public:
    string multiply(string num1, string num2){if(num1 =="0"|| num2 =="0"){return"0";}int m = num1.size(), n = num2.size();auto ansArr =vector<int>(m + n);for(int i = m -1; i >=0;--i){int x = num1.at(i)-'0';for(int j = n -1; j >=0;--j){int y = num2.at(j)-'0';
                ansArr[i + j +1]+= x * y;}}for(int i = m + n -1; i >0;--i){
            ansArr[i -1]+= ansArr[i]/10;
            ansArr[i]%=10;}int index = ansArr[0]==0?1:0;
        string ans;while(index < m + n){
            ans.push_back(ansArr[index]+'0');
            index++;}return ans;}};

c

char*multiply(char* num1,char* num2){int m =strlen(num1), n =strlen(num2);char*ans =malloc(sizeof(char)*(m + n +3));memset(ans,0,sizeof(char)*(m + n +3));if((m ==1&& num1[0]=='0')||(n ==1&& num2[0]=='0')){
        ans[0]='0', ans[1]=0;return ans;}int*ansArr =malloc(sizeof(int)*(m + n +3));memset(ansArr,0,sizeof(int)*(m + n +3));for(int i = m -1; i >=0;--i){int x = num1[i]-'0';for(int j = n -1; j >=0;--j){int y = num2[j]-'0';
            ansArr[i + j +1]+= x * y;}}for(int i = m + n -1; i >0;--i){
        ansArr[i -1]+= ansArr[i]/10;
        ansArr[i]%=10;}int index = ansArr[0]==0?1:0;int ansLen =0;while(index < m + n){
        ans[ansLen++]= ansArr[index]+'0';++index;}return ans;}

python

classSolution:defmultiply(self, num1:str, num2:str)->str:if num1 =="0"or num2 =="0":return"0"

        m, n =len(num1),len(num2)
        ans_arr =[0]*(m + n)for i inrange(m -1,-1,-1):
            x =int(num1[i])for j inrange(n -1,-1,-1):
                ans_arr[i + j +1]+= x *int(num2[j])for i inrange(m + n -1,0,-1):
            ans_arr[i -1]+= ans_arr[i]//10
            ans_arr[i]%=10

        index =1if ans_arr[0]==0else0
        ans ="".join(str(x)for x in ans_arr[index:])return ans

java

classSolution{publicStringmultiply(String num1,String num2){if("0".equals(num1)||"0".equals(num2)){return"0";}int   m      = num1.length(), n = num2.length();int[] ansArr =newint[m + n -1];for(int i = m -1; i >=0;--i){int x = num1.charAt(i)-'0';for(int j = n -1; j >=0;--j){int y = num2.charAt(j)-'0';
                ansArr[i + j]+= x * y;}}StringBuilder ans   =newStringBuilder();int           carry =0;for(int i = m + n -2; i >=0;--i){int b = ansArr[i]+ carry;
            carry = b /10;
            b %=10;
            ans.append(b);}if(carry >0){
            ans.append(carry);}return ans.reverse().toString();}}

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~