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)。

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

相关文章
|
6月前
leetcode-1447:最简分数
leetcode-1447:最简分数
46 0
|
3月前
|
算法
LeetCode第66题加一
LeetCode第66题"加一"的解题方法,通过遍历数组从后向前处理每一位的加法,并考虑进位情况,最终实现给定数字加一的功能。
LeetCode第66题加一
|
6月前
leetcode-475:供暖器
leetcode-475:供暖器
46 0
|
6月前
|
Java
leetcode-474:一和零
leetcode-474:一和零
39 0
|
6月前
|
消息中间件 Kubernetes NoSQL
LeetCode 1359、1360
LeetCode 1359、1360
单链表反转 LeetCode 206
单链表反转 LeetCode 206
73 0
leetcode第53题
解法一和解法二的动态规划,只是在定义的时候一个表示以 i 开头的子数组,一个表示以 i 结尾的子数组,却造成了时间复杂度的差异。问题就是解法一中求出了太多的没必要的和,不如解法二直接,只保存最大的和。
leetcode第53题
leetcode第44题
时间复杂度:text 长度是 T,pattern 长度是 P,那么就是 O(TP)。 空间复杂度:O(TP)。 同样的,和第10题一样,可以优化空间复杂度。
leetcode第44题
|
存储 算法 Java
leetcode第29题
这道题看起来简单,却藏了不少坑。首先,我们用一次一次减造成了超时,然后我们用递归实现了加倍加倍的减,接着由于 int 表示的数的范围不是对称的,最小的负数并不能转换为对应的相反数,所以我们将之前的算法思路完全逆过来,正数边负数,大于变小于,还是蛮有意思的。
leetcode第29题