二哥的 LeetCode 刷题笔记：043.字符串相乘

作者：沉默王二
发布时间：2022-09-26T17:22:04.573+0800

---

本篇043.字符串相乘已收录在星球专栏《二哥的 LeetCode 刷题笔记》当中，希望给刷题的小伙伴们一点点帮助和启发。

043.字符串相乘

题意

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

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

1 <= num1.length , num2.length <= 200

难度

中等

示例

输入: num1 = "2", num2 = "3"

输入: num1 = "123", num2 = "456"输出: "56088"

分析

平常我们计算两个整数相乘，直接num1 * num2就可以了，但是现在存储类型变成了String，所以我们不能直接使用乘法进行计算。

来回忆一下我们是怎么做乘法运算的：

是的！就是列竖式，这是最朴素的计算方法，也是解这道题的 “灵丹妙药”。

但是有一个地方需要注意，列竖式不仅仅需要计算num1的每位和num2的每位相乘，还需要错位相加，而错位的 位 应该怎么去算呢？

我们来约定一下。下面例子的“位”均由第0位开始计算，而且中间过程——即738、615、492，按照它们最后 “贡献” 到最终答案56088的那一位来计算位数。

我们来看一下：

• 7 3 8的 第0位——8 是由123的 第0位——3 和456的 第0位——6 相乘并进位得到的；
• 7 3 8的 第1位——3 是由123的 第1位——2 和456的 第0位——6 相乘，再加上上一次的进位1，并进位得到的；
• 7 3 8的 第2位——7 是由123的 第2位——1 和456的 第0位——6 相乘，再加上上一次的进位1，并进位得到的；
• 6 1 5的 第1位——5 是由123的 第0位——3 和456的 第1位——5 相乘并进位得到的；
• 6 1 5的 第2位——1 是由123的 第1位——2 和456的 第1位——5 相乘并进位得到的；
• ...

经过分析，是不是能够看出点端倪了？

如果是由num1的第x位和num2的第y位相乘所得到的答案，最后都会贡献到ans的第x+y位上。

所以这道题便迎刃而解了，注意考虑一下因为我们字符串都是从头开始的，所以要先逆置一下字符串，才能从0位开始解这道题。

最后再统一加入到答案的String即可。

class Solution {

        StringBuilder temp = new StringBuilder(num1);        temp.reverse();        num1 = temp.toString();        temp = new StringBuilder(num2);        temp.reverse();        num2 = temp.toString();        int[] res = new int[num1.length() + num2.length() + 1];        for(int i = 0;i < num1.length();i++){            for(int j = 0;j < num2.length();j++){                res[i + j] += (num1.charAt(i) - '0') * (num2.charAt(j) - '0');            }        }        for(int i = 0;i < num1.length() + num2.length();i++){            if(res[i] >= 10){                res[i + 1] += res[i] / 10;                res[i] %= 10;            }        }        int beg = num1.length() + num2.length();        while(res[beg] == 0 && beg > 0){            beg--;        }        StringBuilder ans = new StringBuilder();        for(int i = beg;i >= 0;i--){            ans.append(res[i]);        }        return ans.toString();    }}

效率在Leetcode上面跑的也算不错。

这个算法的时间复杂度是，因为循环去计算了每个位置对应的乘积。

还有另外一种更快的方法可以解决这道题，但是会涉及到了 FFT——快速傅立叶变换 ，在面试中，极少会考察到这个算法，所以这里就不再详细展开了。

想要了解更多的小伙伴，可以参考我的这篇 FFT学习笔记 。

总结

本次我们利用列竖式解决了字符串相乘的问题，其实很多问题的解决思路都来源于日常生活当中，这类题目就是为了考察我们如何用计算机语言来复现日常生活中的过程，涉及到自然过程到编程语言的转换，虽然基础，但是却并不简单，因为我们要清楚自然的过程到底跟计算机中的过程的差别在什么地方，只有清楚了这个点，这类的题目就才不会很难闯关。

力扣链接：https://leetcode.cn/problems/multiply-strings/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 850 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

本篇043.字符串相乘已收录在星球专栏《二哥的 LeetCode 刷题笔记》当中，希望给刷题的小伙伴们一点点帮助和启发。

043.字符串相乘

题意

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

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

1 <= num1.length , num2.length <= 200

难度

中等

示例

输入: num1 = "2", num2 = "3"

输入: num1 = "123", num2 = "456"输出: "56088"

分析

平常我们计算两个整数相乘，直接num1 * num2就可以了，但是现在存储类型变成了String，所以我们不能直接使用乘法进行计算。

来回忆一下我们是怎么做乘法运算的：

是的！就是列竖式，这是最朴素的计算方法，也是解这道题的 “灵丹妙药”。

但是有一个地方需要注意，列竖式不仅仅需要计算num1的每位和num2的每位相乘，还需要错位相加，而错位的 位 应该怎么去算呢？

我们来约定一下。下面例子的“位”均由第0位开始计算，而且中间过程——即738、615、492，按照它们最后 “贡献” 到最终答案56088的那一位来计算位数。

我们来看一下：

• 7 3 8的 第0位——8 是由123的 第0位——3 和456的 第0位——6 相乘并进位得到的；
• 7 3 8的 第1位——3 是由123的 第1位——2 和456的 第0位——6 相乘，再加上上一次的进位1，并进位得到的；
• 7 3 8的 第2位——7 是由123的 第2位——1 和456的 第0位——6 相乘，再加上上一次的进位1，并进位得到的；
• 6 1 5的 第1位——5 是由123的 第0位——3 和456的 第1位——5 相乘并进位得到的；
• 6 1 5的 第2位——1 是由123的 第1位——2 和456的 第1位——5 相乘并进位得到的；
• ...

经过分析，是不是能够看出点端倪了？

如果是由num1的第x位和num2的第y位相乘所得到的答案，最后都会贡献到ans的第x+y位上。

所以这道题便迎刃而解了，注意考虑一下因为我们字符串都是从头开始的，所以要先逆置一下字符串，才能从0位开始解这道题。

最后再统一加入到答案的String即可。

class Solution {

        StringBuilder temp = new StringBuilder(num1);        temp.reverse();        num1 = temp.toString();        temp = new StringBuilder(num2);        temp.reverse();        num2 = temp.toString();        int[] res = new int[num1.length() + num2.length() + 1];        for(int i = 0;i < num1.length();i++){            for(int j = 0;j < num2.length();j++){                res[i + j] += (num1.charAt(i) - '0') * (num2.charAt(j) - '0');            }        }        for(int i = 0;i < num1.length() + num2.length();i++){            if(res[i] >= 10){                res[i + 1] += res[i] / 10;                res[i] %= 10;            }        }        int beg = num1.length() + num2.length();        while(res[beg] == 0 && beg > 0){            beg--;        }        StringBuilder ans = new StringBuilder();        for(int i = beg;i >= 0;i--){            ans.append(res[i]);        }        return ans.toString();    }}

效率在Leetcode上面跑的也算不错。

这个算法的时间复杂度是，因为循环去计算了每个位置对应的乘积。

还有另外一种更快的方法可以解决这道题，但是会涉及到了 FFT——快速傅立叶变换 ，在面试中，极少会考察到这个算法，所以这里就不再详细展开了。

想要了解更多的小伙伴，可以参考我的这篇 FFT学习笔记 。

总结

本次我们利用列竖式解决了字符串相乘的问题，其实很多问题的解决思路都来源于日常生活当中，这类题目就是为了考察我们如何用计算机语言来复现日常生活中的过程，涉及到自然过程到编程语言的转换，虽然基础，但是却并不简单，因为我们要清楚自然的过程到底跟计算机中的过程的差别在什么地方，只有清楚了这个点，这类的题目就才不会很难闯关。

力扣链接：https://leetcode.cn/problems/multiply-strings/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 850 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

本篇043.字符串相乘已收录在星球专栏《二哥的 LeetCode 刷题笔记》当中，希望给刷题的小伙伴们一点点帮助和启发。

043.字符串相乘

题意

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

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

1 <= num1.length , num2.length <= 200

难度

中等

示例

输入: num1 = "2", num2 = "3"

输入: num1 = "123", num2 = "456"输出: "56088"

分析

平常我们计算两个整数相乘，直接num1 * num2就可以了，但是现在存储类型变成了String，所以我们不能直接使用乘法进行计算。

来回忆一下我们是怎么做乘法运算的：

是的！就是列竖式，这是最朴素的计算方法，也是解这道题的 “灵丹妙药”。

但是有一个地方需要注意，列竖式不仅仅需要计算num1的每位和num2的每位相乘，还需要错位相加，而错位的 位 应该怎么去算呢？

我们来约定一下。下面例子的“位”均由第0位开始计算，而且中间过程——即738、615、492，按照它们最后 “贡献” 到最终答案56088的那一位来计算位数。

我们来看一下：

• 7 3 8的 第0位——8 是由123的 第0位——3 和456的 第0位——6 相乘并进位得到的；
• 7 3 8的 第1位——3 是由123的 第1位——2 和456的 第0位——6 相乘，再加上上一次的进位1，并进位得到的；
• 7 3 8的 第2位——7 是由123的 第2位——1 和456的 第0位——6 相乘，再加上上一次的进位1，并进位得到的；
• 6 1 5的 第1位——5 是由123的 第0位——3 和456的 第1位——5 相乘并进位得到的；
• 6 1 5的 第2位——1 是由123的 第1位——2 和456的 第1位——5 相乘并进位得到的；
• ...

经过分析，是不是能够看出点端倪了？

如果是由num1的第x位和num2的第y位相乘所得到的答案，最后都会贡献到ans的第x+y位上。

所以这道题便迎刃而解了，注意考虑一下因为我们字符串都是从头开始的，所以要先逆置一下字符串，才能从0位开始解这道题。

最后再统一加入到答案的String即可。

class Solution {

        StringBuilder temp = new StringBuilder(num1);        temp.reverse();        num1 = temp.toString();        temp = new StringBuilder(num2);        temp.reverse();        num2 = temp.toString();        int[] res = new int[num1.length() + num2.length() + 1];        for(int i = 0;i < num1.length();i++){            for(int j = 0;j < num2.length();j++){                res[i + j] += (num1.charAt(i) - '0') * (num2.charAt(j) - '0');            }        }        for(int i = 0;i < num1.length() + num2.length();i++){            if(res[i] >= 10){                res[i + 1] += res[i] / 10;                res[i] %= 10;            }        }        int beg = num1.length() + num2.length();        while(res[beg] == 0 && beg > 0){            beg--;        }        StringBuilder ans = new StringBuilder();        for(int i = beg;i >= 0;i--){            ans.append(res[i]);        }        return ans.toString();    }}

效率在Leetcode上面跑的也算不错。

这个算法的时间复杂度是，因为循环去计算了每个位置对应的乘积。

还有另外一种更快的方法可以解决这道题，但是会涉及到了 FFT——快速傅立叶变换 ，在面试中，极少会考察到这个算法，所以这里就不再详细展开了。

想要了解更多的小伙伴，可以参考我的这篇 FFT学习笔记 。

总结

本次我们利用列竖式解决了字符串相乘的问题，其实很多问题的解决思路都来源于日常生活当中，这类题目就是为了考察我们如何用计算机语言来复现日常生活中的过程，涉及到自然过程到编程语言的转换，虽然基础，但是却并不简单，因为我们要清楚自然的过程到底跟计算机中的过程的差别在什么地方，只有清楚了这个点，这类的题目就才不会很难闯关。

力扣链接：https://leetcode.cn/problems/multiply-strings/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 850 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

            知识星球
            
    
    
        
        扫码加入星球
        查看更多优质内容
    
    https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412