leetcode 43 Multiply Strings

cloud 发布于2019-08-19 10:42 / 2872人阅读

摘要：题目详情题目要求输入两个以字符串形式表示的正整数，要求我们求出它们的乘积，同样也是字符串形式表示。要求不能直接将字符串转换为整数进行乘法运算。想法这道题的思路就是将我们平时手算多位数乘法的计算方法，转换成程序语言。

题目详情

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.
Note:
-The length of both num1 and num2 is < 110.
-Both num1 and num2 contains only digits 0-9.
-Both num1 and num2 does not contain any leading zero.
-You must not use any built-in BigInteger library or convert the inputs to integer directly.题目要求输入两个以字符串形式表示的正整数，要求我们求出它们的乘积，同样也是字符串形式表示。要求不能直接将字符串转换为整数进行乘法运算。

想法

这道题的思路就是将我们平时手算多位数乘法的计算方法，转换成程序语言。

对于两个长度分别为m,n的字符串，乘法操作获得的字符串res长度为m+n(第一位可以是0)

首先我们看一下下面这张图

这个例子里我们的操作顺序是，用5分别乘以1，2，3；随后再用4分别乘以1，2，3.每次对位的乘法操作我们默认他会获得一个两位数(第一位可以是0)

如果进行乘法操作的两位在各自字符串中的位置为i和j，那么生成的两位数在结果字符串res中对应的位置应当是i+j和i+j+1

将乘法结果和对应位置上的已有数相加，再将结果放到对应位置。

解法

    public String multiply(String num1, String num2) {
        int m = num1.length();
        int 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;
                int 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();
    }

服务器托管私有云 Multiply strings Leetcod LeetCode

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

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

leetcode43 multiply strings

摘要：题目要求将两个形式的数字相乘的结果用的形式返回。不准使用以外的形式来记录数字。假设，则将结果的十位和个位分别放在数组下标为和的位置上。存储的位置等同于上一思路。然后再通过一轮遍历将进位处理一下。题目要求 Given two non-negative integers num1 and num2 represented as strings, return the product of...

Batkid 2019-08-16 10:38 评论0 收藏0
43. Multiply Strings

摘要：是最高位代表进位，表示本位。就是本位的乘积加上本位已有的值。进位就是除以的余数本位就是剩下的个位数。 43 Multiply Strings 关键词，进位。 public class Solution { public String multiply(String num1, String num2) { int m = num1.length(), n = n...

fsmStudy 2019-08-14 18:05 评论0 收藏0
[Leetcode] Multiply String and Big Interger 大数乘法加法

摘要：因为被乘数每一位数字和乘数相乘的结果是依次错开的，所以就没问题。判断两个数的大小的方法，是先判断其长度，如果长度不一样，则较长的较大，如果长度一样，则需要比较每一位。 Multiply Strings Given two numbers represented as strings, return multiplication of the numbers as a string. ...

keithxiaoy 2019-08-14 12:47 评论0 收藏0
leetcode 部分解答索引（持续更新～）

摘要：前言从开始写相关的博客到现在也蛮多篇了。而且当时也没有按顺序写现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言从开始写leetcode相关的博客到现在也蛮多篇了。而且当时也没有按顺序写～现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理 1~50 1...

leo108 2019-08-15 14:26 评论0 收藏0
LeetCode43.字符串相乘 JavaScript

摘要：给定两个以字符串形式表示的非负整数和，返回和的乘积，它们的乘积也表示为字符串形式。示例输入输出示例输入输出说明和的长度小于。和均不以零开头，除非是数字本身。不能使用任何标准库的大数类型比如或直接将输入转换为整数来处理。给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。示例 1: 输入: num1 = 2, ...

kk_miles 2019-08-23 18:07 评论0 收藏0