力扣(LeetCode)43

itvincent 发布于2019-08-16 15:57 / 1160人阅读

摘要：示例输入输出示例输入输出说明和的长度小于。和均不以零开头，除非是数字本身。举例说明这两个数的乘积的长度一定不会超过，分别是字符串的长度。第一轮第二轮至此该数组变为然后再从尾部处理进位。

题目地址：
https://leetcode-cn.com/probl...
题目描述：
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

示例 1:

输入: num1 = "2", num2 = "3"
输出: "6"
示例 2:

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

num1 和 num2 的长度小于110。
num1 和 num2 只包含数字 0-9。
num1 和 num2 均不以零开头，除非是数字 0 本身。
不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

解答：
如何使用计算机模仿大数想乘？
我们用手计算的时候，会边乘边计算进位，并且把进位加在前一位。
但是如果这里也这样处理，那么会无比麻烦，实际上我们可以把每一位的乘积加上，然后
最后再统一处理。
举例说明：
124 * 32
这两个数的乘积的长度一定不会超过m+n（m，n分别是字符串的长度。）
我们开一个m+n长度的数组val[m+n]。
第一轮：2*4 = 8,val[m+n-1] += 8,val[m+n-1] = 8

   2*2 = 4,val[m+n-2] += 4,val[m+n-2] = 4
   2*1 = 2,val[m+n-3] += 2,val[m+n-3] = 2

第二轮：3*4 = 12,val[m+n-2] += 12,val[m+n-2] = 16

   3*2 = 6,val[m+n-3] += 6,val[m+n-3] = 8 
   3*1 = 3,val[m+n-4] += 3,val[m+n-4] = 3

至此,该数组变为
val[0,3,8,16,8]

然后再从尾部处理进位。
比如最后一位8是没有进位的，往前处理，到了16，16 >= 10。
把该位变成16%10 = 6,并且获得进位16/10 = 1,再继续向前处理
8要加上进位变成9，然后再往前处理3不动。
最后数组变成val[0,3,9,6,8]
到此，绝大部分工作已经完成，只需要从左扫描数组找到第一个不为0的数，然后把后面的加入字符串即可。

java ac代码：

class Solution {
    
    public String multiply(String num1, String num2) {
        int[] val = new int[num1.length() + num2.length()];
        
        for(int i = num1.length()-1,round = 0;i >= 0;i--,round++){
            int k = val.length-1-round;
            for(int j = num2.length()-1;j >= 0;j--)
            {
                int temp = (num1.charAt(i)-"0")*(num2.charAt(j)-"0");
                val[k--] += temp;                
            }
        }
        int plus = 0;
        for(int i = val.length-1;i >= 0;i--)
        {
            int sum = val[i] + plus;
            val[i] = sum%10;
            plus = sum/10;
        }
        int loc = 0;
        String ans = "";
        while(loc < val.length && val[loc] == 0)loc++;
        if(loc == val.length)ans = "0";
        else
        for(int i = loc;i < val.length;i++)
            ans += val[i];
        return ans;
        
    }
}

更为详细的讲解可以参考这篇文章https://blog.csdn.net/afei__/...

服务器托管 GPU服务器力扣 LeetCode httpclient43 LeetCode_String

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/73798.html

13. 罗马数字转整数-----leetcode刷题（python解题）

摘要：题目罗马数字包含以下七种字符，，，，，和。字符数值例如，罗马数字写做，即为两个并列的。通常情况下，罗马数字中小的数字在大的数字的右边。同样地，数字表示为。给定一个罗马数字，将其转换成整数。 [TOC] 题目罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。字符数值 I 1 V 5 X ...

Gu_Yan 2019-07-31 10:38 评论0 收藏0
力扣(LeetCode)310

摘要：图因此可以成为树，在所有可能的树中，具有最小高度的树被称为最小高度树。给出这样的一个图，写出一个函数找到所有的最小高度树并返回他们的根节点。因此使用一个数组代表每个节点的入度，若入度为就是叶子节点。题目地址：https://leetcode-cn.com/probl...题目描述：对于一个具有树特征的无向图，我们可选择任何一个节点作为根。图因此可以成为树，在所有可能的树中，具有最小...

amuqiao 2019-08-16 16:13 评论0 收藏0
＜LeetCode天梯＞Day026 反转链表（递归法+（迭代法）双链表法） | 初级算法 | Py

摘要：关于递归这里提一两点递归基本有这几步递归的模板，终止条件，递归调用，逻辑处理。 ?作者简介：大家好，我是车神哥，府学路18号的车神? ?个人主页：应无所住而生...

imingyu 2021-11-17 09:33 评论0 收藏0
力扣(LeetCode)452

摘要：对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。可以射出的弓箭的数量没有限制。弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。解答这是一道区间覆盖问题，不太好说清楚，利用模板即可。题目地址：https://leetcode-cn.com/probl...题目描述：在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方...

fanux 2019-08-16 15:20 评论0 收藏0