LeetCode-Problem 43：大数相乘

￡神魔★判官ぃ 2022-05-27 04:09 176阅读 0赞

### **算法问题** ###

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

### **算法实现** ###

**以下是大神的算法，膜拜大神**：

首先，长度位m的数乘以长度为n的数的结果不超过m+n。

接下来，我们来看下两数相乘的计算过程，从右向左，将数2中的每一位的数与数1相乘，最后将结果相加。下图演示的是两数相乘的整个过程，从下图中，我们可以得到，对于num\[i\] \*num\[j\]（数1中的第i位数字与数2中的第j位数字相乘的结果只会存放在第【i+j】和【i+j+1】这两位上）

![这里写图片描述][70]

因此，我们实现算法如下：

public static String multiply(String num1, String num2) {
            int m = num1.length(), n = num2.length();
            int[] pos = new int[m + n];
    
            for (int i = m - 1; i >= 0; i--) {
                for (int j = n - 1; j >= 0; j--) {
                    int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                    int p1 = i + j, p2 = i + j + 1;
                    int sum = mul + pos[p2];
    
                    pos[p1] += sum / 10;
                    pos[p2] = (sum) % 10;
                }
            }
            StringBuilder sb = new StringBuilder();
            for (int p : pos) {
                if (!(sb.length() == 0 && p == 0)) {
                    sb.append(p);
                }
            }
            return sb.length() == 0 ? "0" : sb.toString();
        }

另外，常见的大数相乘算法还有：

*  **[Karatsuba算法][Karatsuba]**
 *  [**FFT快速傅里叶变换算法**][FFT]

[70]: /images/20220527/858a062747874e2d979e7a9ce60fb8cf.png
[Karatsuba]: https://en.wikipedia.org/wiki/Karatsuba_algorithm
[FFT]: https://en.wikipedia.org/wiki/Fast_Fourier_transform

发表评论取消回复

表情：

评论列表（有 0 条评论，176人围观）

还没有评论，来说两句吧...

相关阅读

相关 43. 字符串相乘(大数相乘模拟)

就是模拟乘法的一个过程,这里我们不按正常的乘法做法来做:我们在每一位相乘后不进行进位,而是保留相乘得到的结果,到最后相加的时候再去进行进位。如下图所示: ![waterm

叁歲伎倆/ 2022年10月30日 02:26/ 0 赞/ 177 阅读

相关大数相乘

一、背景最近在看算法的时候发现了一个问题，我们都知道方法的形参是要指定类型的，假如有以下方法 public int example(int a,int b){

傷城~/ 2022年09月30日 13:55/ 0 赞/ 208 阅读

相关大数相乘

无意中看到一个华为面试题，使用代码计算[1234567891011121314151617181920\2019181716151413121110987654321][123

系统管理员/ 2022年08月11日 20:29/ 0 赞/ 193 阅读

相关大数相乘

题目：请使用代码计算1234567891011121314151617181920\2019181716151413121110987654321。答： ![复制代码][

Bertha 。/ 2022年08月05日 08:54/ 0 赞/ 205 阅读

相关大数相乘

在这之前我们先来了解一下Java 中每种基本数据类型所占存储空间的大小。其中 1Byte = 8bit。 <table> <tbody> <tr> <th>

朱雀/ 2022年06月02日 02:36/ 0 赞/ 250 阅读

相关大数相乘

设X和Y是n位的二进制整数，现在要计算X\Y的结果将a和b分为两段，每段长均为总长的1/2， ![20180329214901958][]

拼搏现实的明天。/ 2022年05月28日 05:06/ 0 赞/ 214 阅读

相关 LeetCode-Problem 43：大数相乘

算法问题给定两个以字符串表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积。算法实现以下是大神的算法，膜拜大神：首先，长度位m

￡神魔★判官ぃ/ 2022年05月27日 04:09/ 0 赞/ 177 阅读

相关大数相乘

题目编写两个任意位数的大数相乘的程序，给出计算结果。比如： > 题目描述：输出两个不超过100位的大整数的乘积。 > 输入：输入两个大整数，如1234567

今天药忘吃喽~/ 2022年05月23日 11:23/ 0 赞/ 335 阅读

相关大数相乘

def fun(num1,num2): num1 type str num2 type str a = map(int,

落日映苍穹つ/ 2021年10月24日 01:48/ 0 赞/ 329 阅读

相关 LeetCode: 43. Multiply Strings 大数相乘

试题： Given two non-negative integers num1 and num2 represented as strings, return the p

末蓝、/ 2021年09月18日 15:28/ 0 赞/ 278 阅读