leetcode第43题

简介: 个位乘个位,得出一个数,然后个位乘十位,全部乘完以后,就再用十位乘以各个位。然后百位乘以各个位,最后将每次得出的数相加。十位的结果要补 1 个 0 ,百位的结果要补两个 0 。相加的话我们可以直接用之前的大数相加。直接看代码吧。

image.png

就是两个数相乘,输出结果,只不过数字很大很大,都是用 String 存储的。也就是传说中的大数相乘。

解法一

我们就模仿我们在纸上做乘法的过程写出一个算法。

image.png

个位乘个位,得出一个数,然后个位乘十位,全部乘完以后,就再用十位乘以各个位。然后百位乘以各个位,最后将每次得出的数相加。十位的结果要补 1 个 0 ,百位的结果要补两个 0 。相加的话我们可以直接用之前的大数相加。直接看代码吧。

publicStringmultiply(Stringnum1, Stringnum2) {
if (num1.equals("0") ||num2.equals("0")) {
return"0";
    }  
Stringans="0";
intindex=0; //记录当前是哪一位,便于后边补 0 for (inti=num2.length() -1; i>=0; i--) {
intcarry=0; //保存进位Stringans_part=""; //直接用字符串保存每位乘出来的数intm=num2.charAt(i) -'0';
//乘上每一位for (intj=num1.length() -1; j>=0; j--) {
intn=num1.charAt(j) -'0';
intmul=m*n+carry; 
ans_part=mul%10+""+ans_part;
carry=mul/10;
        }
if (carry>0) {
ans_part=carry+""+ans_part;
        }
//补 0 for (intk=0; k<index; k++) {
ans_part=ans_part+"0";
        }
index++;
//和之前的结果相加ans=sumString(ans, ans_part);
    }
returnans;
}
//大数相加privateStringsumString(Stringnum1, Stringnum2) {
intcarry=0;
intnum1_index=num1.length() -1;
intnum2_index=num2.length() -1;
Stringans="";
while (num1_index>=0||num2_index>=0) {
intn1=num1_index>=0?num1.charAt(num1_index) -'0' : 0;
intn2=num2_index>=0?num2.charAt(num2_index) -'0' : 0;
intsum=n1+n2+carry;
carry=sum/10;
ans=sum%10+""+ans;
num1_index--;
num2_index--;
    }
if (carry>0) {
ans=carry+""+ans;
    }
returnans;
}

时间复杂度:O(m * n)。m,n 是两个字符串的长度。

空间复杂度:O(1)。

如果按普通的思路写,这道题也不难。新的竖式的计算,让人眼前一亮,代码优雅了很多。

相关文章
|
1月前
【LeetCode 02】暴力法总结
【LeetCode 02】暴力法总结
15 1
|
3月前
|
算法
LeetCode第66题加一
LeetCode第66题"加一"的解题方法,通过遍历数组从后向前处理每一位的加法,并考虑进位情况,最终实现给定数字加一的功能。
LeetCode第66题加一
|
6月前
|
消息中间件 Kubernetes NoSQL
LeetCode 1359、1360
LeetCode 1359、1360
|
6月前
|
消息中间件 Kubernetes NoSQL
LeetCode 3、28、1351
LeetCode 3、28、1351
LeetCode 389. 找不同
给定两个字符串 s 和 t,它们只包含小写字母。
72 0
|
测试技术
一和零(LeetCode-474)
一和零(LeetCode-474)
136 0
一和零(LeetCode-474)
|
算法
LeetCode——944. 删列造序
LeetCode——944. 删列造序
108 0
leetcode第37题
从上到下,从左到右遍历每个空位置。在第一个位置,随便填一个可以填的数字,再在第二个位置填一个可以填的数字,一直执行下去直到最后一个位置。期间如果出现没有数字可以填的话,就回退到上一个位置,换一下数字,再向后进行下去。
leetcode第37题
leetcode第48题
将一个矩阵顺时针旋转 90 度,并且不使用额外的空间。大概属于找规律的题,没有什么一般的思路,观察就可以了。 解法一 可以先转置,然后把每列对称交换交换一下
leetcode第48题
leetcode第55题
当自己按照 45 题的思路写完的时候,看 Solution 的时候都懵逼了,这道题竟然这么复杂?不过 Solution 把问题抽象成动态规划的思想,以及优化的过程还是非常值得学习的。
leetcode第55题