LeetCode第43题字符串相乘

简介: LeetCode第43题"字符串相乘"的解题方法,通过使用数组存储乘积并处理进位,避免了字符串转换数字的复杂性,提高了算法效率。

继续打卡算法题,今天学习的是LeetCode第43题字符串相乘,这道题目是道中等题。算法题的一些解题思路和技巧真的非常巧妙,每天看一看算法题和解题思路,我相信对我们的编码思维和编码能力有一些提升。

image.png

分析一波题目

两数相乘本来是一个比较容易的题目,但是本题有要求,一是乘数是字符串表示结果也得用字符串表示,二是不能使用库函数将字符串转换成数字,这样题目难度就加大了。

我们看下最朴素的解法,我们按照乘法公式,相乘前需要补0,每一位相乘再依次将多个分结果累加。

image.png

上面这样计算得到的结果是从个位开始保存的,还需要反转才能得到结果。这样代码需要控制的点比较多。

有没有简单的,更加好理解的解法呢? 哈哈,确实是有的,下面图解就比较好理解了,我们使用一个新数组来记录每个乘数计算结果。数组长度是两个乘数长度之和,初始化值都是0。我们每次计算一个乘数之后就覆盖一下数组上的值,这里有个特点,每次乘数相乘计算填充的位置是i+j+1的位置上, 非常巧妙。

image.png

本题解题关键技巧

1、使用一个数组来存储每位计算的结果,每位计算结果刚刚存储在两位数字下标i+j+1的位置上

编码解决


class Solution {
   
   
    public String multiply(String num1, String num2) {
   
   

        // 乘数中任意一个有0的情况, 直接返回0
        if(num1.equals("0") || num2.equals("0")) return "0";
        int m = num1.length(), n = num2.length();
        // 乘法结果记录数组,乘积的最大长度为 m + n
        int[] resArr = new int[m + n];
        for (int i = m - 1; i >= 0; i--) {
   
   
            int a = num1.charAt(i) - '0';
            for (int j = n - 1; j >= 0; j--) {
   
   
                int b = num2.charAt(j) - '0';
                int temp = a * b;
                //累加
                resArr[i + j + 1] = temp + resArr[i + j + 1];

                //同时处理进位
                resArr[i + j] = resArr[i + j + 1] /10 + resArr[i + j];
                resArr[i + j + 1] = resArr[i + j + 1] % 10;
            }
        }

        //结果处理
        StringBuilder builder = new StringBuilder();
        //第一位可能是0,需要忽略
        int start = resArr[0] == 0 ? 1 : 0;
        while (start < m + n) {
   
   
            builder.append(resArr[start]);
            start++;
        }
        return builder.toString();
    }
}

总结

很多题目朴素解法也可以做出来,这道题也是这种情况,但是如果掌握一些小技巧,可以提高算法效率。

相关文章
|
14天前
|
JavaScript
力扣3333.找到初始输入字符串Ⅱ
【10月更文挑战第9天】力扣3333.找到初始输入字符串Ⅱ
30 1
|
28天前
|
C++
Leetcode第43题(字符串相乘)
本篇介绍了一种用C++实现的字符串表示的非负整数相乘的方法,通过逆向编号字符串,将乘法运算转化为二维数组的累加过程,最后处理进位并转换为字符串结果,解决了两个大数相乘的问题。
23 9
|
28天前
|
算法 C++
Leetcode第八题(字符串转换整数(atoi))
这篇文章介绍了LeetCode上第8题“字符串转换整数(atoi)”的解题思路和C++的实现方法,包括处理前导空格、正负号、连续数字字符以及整数溢出的情况。
15 0
|
28天前
【LeetCode 22】459.重复的子字符串
【LeetCode 22】459.重复的子字符串
27 0
|
28天前
【LeetCode 20】151.反转字符串里的单词
【LeetCode 20】151.反转字符串里的单词
17 0
|
28天前
【LeetCode 19】541.反转字符串II
【LeetCode 19】541.反转字符串II
19 0
|
28天前
【LeetCode 18】6.2.反转字符串
【LeetCode 18】6.2.反转字符串
14 0
|
3月前
|
算法 Java
LeetCode第28题找出字符串中第一个匹配项的下标
这篇文章介绍了LeetCode第28题"找出字符串中第一个匹配项的下标"的两种解法:暴力解法和KMP算法,并解释了KMP算法通过构建前缀表来提高字符串搜索的效率。
LeetCode第28题找出字符串中第一个匹配项的下标
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
3月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
106 2