当前位置：首页 > news >正文

Leetcode 43. 字符串相乘

news 来源：原创 2024/9/25 9:32:50

1.题目基本信息

1.1.题目描述

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

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

1.2.题目地址

https://leetcode.cn/problems/multiply-strings/description

2.解题方法

2.1.解题思路

数组+数字

2.2.解题步骤

第一步，临界值处理。当num1或者num2为0时，乘积为0，直接返回

第二步，m位数乘以n位数，最终结果不会超过m+n位数，所以将结果用一个m+n长度的数组arr进行存储。同时num1[i]*num2[j]可以认为是arr[i+j+1]的未进位时的值的组成部分。所以让乘数num1[i]*num2[j]的值加到arr[i+j+1]上

第三步，第二步获取的是未进位的arr数值数组，在这一步，从后往前遍历，将数组中各个位进行进位操作

第四步，将数组各个位进行连接，并删除前面的0项，即为最终数字的字符串

3.解题代码

Python代码

class Solution:# 数组+数字def multiply(self, num1: str, num2: str) -> str:# 第一步，临界值处理。当num1或者num2为0时，乘积为0，直接返回if num1=="0" or num2=="0":return "0"# 第二步，m位数乘以n位数，最终结果不会超过m+n位数，所以将结果用一个m+n长度的数组arr进行存储。同时num1[i]*num2[j]可以认为是arr[i+j+1]的未进位时的值的组成部分。所以让乘数num1[i]*num2[j]的值加到arr[i+j+1]上length1,length2=len(num1),len(num2)arr=[0]*(length1+length2)for i in range(length1-1,-1,-1):x=int(num1[i])for j in range(length2-1,-1,-1):y=int(num2[j])arr[i+j+1]+=x*y# 第三步，第二步获取的是未进位的arr数值数组，在这一步，从后往前遍历，将数组中各个位进行进位操作extra=0for i in range(length1+length2-1,-1,-1):temp=(arr[i]+extra)%10extra=(arr[i]+extra)//10arr[i]=tempindex=0 if arr[0]!=0 else 1# 第四步，将数组各个位进行连接，并删除前面的0项，即为最终数字的字符串result="".join([str(i) for i in arr[index:]])# print(result)return result

C++代码

class Solution {
public:string multiply(string num1, string num2) {if(num1=="0" || num2=="0"){return "0";}int length1=num1.size(),length2=num2.size();vector<int> arr(length1+length2,0);for(int i=length1-1;i>=0;--i){int x=num1.at(i)-'0';for(int j=length2-1;j>=0;--j){int y=num2.at(j)-'0';arr[i+j+1]+=x*y;}}int extra=0;for(int i=length1+length2-1;i>=0;--i){int temp=arr[i]+extra;extra=temp/10;arr[i]=temp%10;}string result;int index=arr[0]==0 ? 1 : 0;while(index<length1+length2){cout << arr[index] << endl;result+=arr[index]+'0';index++;}return result;}
};