43、字符串乘法
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
示例 1:
输入: num1 = “2”, num2 = “3”
输出: “6”
示例 2:
输入: num1 = “123”, num2 = “456”
输出: “56088”
- 说明：
num1 和 num2 的长度小于110。
num1 和 num2 只包含数字 0-9。
num1 和 num2 均不以零开头，除非是数字 0 本身。
思路
- 模拟乘法的每一步
- 推导中间结果与最终结果的关系
- 第i位与第j位相乘，结果的第i+j加上结果的个位数，第i+j+1位存放进位
- 重复此步骤计算即可
- 低位在后面
t = a[i]*b[j] + result[i+j+1]迭代求i+j+1位的数字result[i+j+1] = t%10+'0'更新第i+j+1位的结果result[i+j] += t/10;更新进位
代码
class Solution {
public:
string multiply(string num1, string num2) {
int n1=num1.size();
int n2=num2.size();
string res(n1+n2,'0');
for(int i=n2-1;i>=0;i--){// 最小位在最后
for(int j=n1-1;j>=0;j--){// 最小位在最后
int temp=(res[i+j+1]-'0')+(num1[j]-'0')*(num2[i]-'0');// 迭代更新
res[i+j+1]=temp%10+'0';//当前位
res[i+j]+=temp/10; //前一位加上进位，res[i+j]已经初始化为'0'，加上int类型自动转化为char，所以此处不加'0'
}
}
//去除首位'0'
for(int i=0;i<n1+n2;i++){
if(res[i]!='0')
return res.substr(i);
}
return "0";
}
};
// 作者：carryzz
// 链接：https://leetcode-cn.com/problems/multiply-strings/solution/c-shu-shi-cheng-fa-dai-ma-jian-ji-you-ya-yi-dong-b/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
- Java版
class Solution {
public String multiply(String num1, String num2) {
// 模拟计算，用大整数加法完成计算
// 乘积为0的情况
if (num1.charAt(0) == '0' || num2.charAt(0) == '0') {
return "0";
}
int len1 = num1.length();
int len2 = num2.length();
char[] res = new char[len1+len2];
for (int i = 0;i < len1+len2;i++) {
res[i] = '0';
}
char[] a = num1.toCharArray();
char[] b = num2.toCharArray();
for (int i = len2 - 1;i >= 0;i--) {
for (int j = len1 - 1;j >= 0;j--) {
int t = (res[i+j+1] - '0') + (a[j] - '0')*(b[i] - '0');
res[i+j+1] = (char)(t%10 + '0');
res[i+j] += t/10;
}
}
StringBuilder ans = new StringBuilder("");
boolean first = true;
for (int i = 0;i < len1 + len2;i++) {
if (first){
if (res[i] != '0') {
first = false;
ans.append(res[i]);
}
}else {
ans.append(res[i]);
}
}
return ans.toString();
}
}
转换成整数数组求解
class Solution {
public static String multiply(String num1,String num2) {
StringBuilder sBuilder=new StringBuilder();
int []arr1=toInt(num1);
int []arr2=toInt(num2);
if((arr1.length==1&&arr1[0]==0)||(arr2.length==1&&arr2[0]==0)) {
return "0";
}
int []result=new int[arr1.length+arr2.length];
for(int i=0;i<arr1.length;i++) {
for(int j=0;j<arr2.length;j++) {
result[i+j+1]+=(arr1[i]*arr2[j]);
}
}
for(int k=result.length-1;k>0;k--) {
if(result[k]>=10) {
result[k-1]+=(result[k]/10);
result[k]=result[k]%10;
}
}
if(result[0]==0) {
for(int i=1;i<result.length;i++) {
sBuilder.append(result[i]);
}
}else {
for(int i=0;i<result.length;i++) {
sBuilder.append(result[i]);
}
}
return sBuilder.toString();
// System.arraycopy(result, 1, x, 0, result.length-1);
// return Arrays.toString(result);
}
public static int[] toInt(String str) {
int []arr=new int[str.length()];
for(int i=0;i<arr.length;i++) {
arr[i]=(str.charAt(i)-'0');
}
return arr;
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
