问题描述:
Given two numbers represented as strings, return multiplication of the numbers as a string.
Note:
- The numbers can be arbitrarily large and are non-negative.
- Converting the input string to integer is NOT allowed.
- You should NOT use internal library such as BigInteger
原问题链接:https://leetcode.com/problems/multiply-strings/
问题分析
这个问题的限制在于不能直接将给定的两个字符串转换成整数,另外数字也可能足够大,所以用直接的运算可能会导致溢出,也限制了使用BigInteger。所以基本上就限定了要用数组的方式来模拟乘法运算的过程。我们针对这几种情况来具体的分析一下。
方法一
在之前的文章里有讨论过对于比较大的整数的乘法模拟运算。在这种方法里,我们定义两个整型数组,分别表示两个字符串对应的数字。数组里每个元素对应一个字符所表示的数字。因为通常的字符串表示的数字比如"12345",它的最高位在最前面。我们在转换的时候需要将它们倒过来保存以方便后续的运算。
在得到两个整型数组之后,我们需要进行模拟的乘法运算。这里是按照人工手工运算的方式来计算。我们知道,对于两个长度分别为m, n的数字来说,它们的乘积数字最大长度为m + n。所以需要声明一个m + n长度的数组来保存结果。
在乘法的过程中,我们从一个数组中按照从最低位到最高位,每次取该位的数字和另外一个数组里的每个元素逐位相乘,得到的结果再依次移位相加。比如有数字123 x 456的时候,我们首先去456中间最低位6和123相乘,得到数值732,我们将这个值放到一个中间值数组里。然后这个数组和最后结果的result数组从最后一位开始依次相加。然后下一位的计算再求5乘以123。得到的数字是615,不过这个时候这个数字需要向前移动一位,再和result数组里面每一位对应相加。这样,按照这种方式,我们得到一个最终的数组。
这里还有一个细节就是我们分配的数组是按照最大的情况考虑的,如果实际上得到的数字没有那么大呢?那么就可能出现最高位的数字是0的情况。我们还需要把这种情况给跳过去。所以根据上述的讨论,可以得到如下的代码:
public class Solution { public String multiply(String num1, String num2) { if(num1.equals("0") || num2.equals("0")) return "0"; int[] nu1 = toArray(num1); int[] nu2 = toArray(num2); int[] result = multiply(nu1, nu2); StringBuilder builder = new StringBuilder(); if(result[result.length - 1] == 0) { for(int i = result.length - 2; i >= 0; i--) builder.append(result[i]); } else { for(int i = result.length - 1; i >= 0; i--) builder.append(result[i]); } return builder.toString(); } private int[] multiply(int[] a, int[] b) { int la = a.length, lb = b.length; int[] result = new int[la + lb]; for(int i = 0; i < la; i++) { int[] medium = new int[lb + 1]; int carry = 0; int j = 0; for(j = 0; j < lb; j++) { medium[j] = (a[i] * b[j] + carry) % 10; carry = (a[i] * b[j] + carry) / 10; } medium[j] = carry; carry = 0; for(int k = 0; k < lb + 1; k++) { int sum = medium[k] + result[i + k] + carry; result[i + k] = sum % 10; carry = sum / 10; } } return result; } private int[] toArray(String s) { int len = s.length(); int[] list = new int[len]; for(int i = 0; i < len; i++) { list[len - i - 1] = Character.digit(s.charAt(i), 10); } return list; } }
改进方法
上述的方法模拟的计算确实能得到正确的结果,不过总体来说显得有点复杂了。一方面它需要不断分配数组来作为中间结果,而且还需要将这些结果移位相加。这样还比较容易出错。那么有没有更好的方法呢?
在参考了一个讨论的分析之后,我们其实有一个办法可以执行的效率更高。我们都知道,对于整数乘法来说,它们都是每次取一个位的值和另外一个数的所有位相乘。然后每次对应一个不同的位是要相应进位。然后再将它们都加起来。
假设有数组num1[], num2[],它们对应的索引分别是i, j。那么它们的乘积的运算关系如下图所示:
通过上述的推导我们可以发现num1[i] * num2[j]的结果将被保存到[i + j, i + j + 1]这两个索引的位置。其中它们的个位数保存在i + j + 1的位置,十位数保存在i + j的位置。所以我们可以定义一个数组pos[m + n],它的长度为两个数组的长度。只是它们的计算不需要把它们给反转过来。每次我们有num1[i] * num2[j]的时候先取得pos1 = i + j, pos2 = i + j + 1。这样得到的值是sum = num1[i] * num2[j] + pos[pos2]。按照前面的计算规则,pos[pos1] = sum / 10,pos[pos2] = sum % 10。
按照上述的讨论可以得到如下的代码:
public class Solution { public 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(); } }
和前面的方法比起来,这里根据它们运算的过程推导出num1[i] * num2[j]对应到i + j, i + j + 1两个位置的值。然后每次都将乘积结果和对应的值相加再来确定最终的值。这种方式也节省了中间值数组的申请。所以显得简洁高效很多。
参考材料
https://leetcode.com/discuss/71593/easiest-java-solution-with-graph-explanation
http://shmilyaw-hotmail-com.iteye.com/blog/1769034
相关推荐
正确的姿势,学习的态度来刷 LeetCode:高效的代码、简洁的注释、精炼的总结。
leetcode 非官方顺序leetcode题解,主要代码为Python和C++。 leetcode 第1题: leetcode 第2题: leetcode 第3题: leetcode 第4题: leetcode 第5题: leetcode 第6题: leetcode 第7题: leetcode 第9题: ...
leetcode11 top 1. 位运算 LeetCode191 : 二进制位1的个数 LeetCode338 : 比特位运算 2. 字典树 LeetCode209 : 实现一个Trie结构 LeetCode79 : 单词搜索(判断单词是否出现在给定的网格中) LeetCode212 : 单词搜索II...
LeetCode::laptop:LeetCode解决方案
leetcode 答案 leetCode :keyboard:我的 Leetcode 解题答案
lru缓存leetcode 力码 涵盖了 Geeks for Geeks 和 Leet Code 的各种问题。 LeetCode 1 : 二和 (46_Easy) LeetCode 2 : 两个数字相加 (96_Medium) LeetCode 3 : 无重复字符的最长子串 (214_Medium) LeetCode 4 : 两个...
LeetCode 在LeetCode和其他编码平台上解决的问题的集合
leetcode :ice_cream: LeetCode Kindem 的个人 LeetCode 题解仓库,欢迎交流学习。 下面的目录中 $number 题号代表经典 LeetCode 题目,$number.$number 题号表示 LeetCode 面试题。 :receipt: 目录 统计 值 AC 的...
leetcode 分类 LeetCode :bouquet::bouquet::bouquet: 介绍 leetcode 题解,Issues 会记录 leetcode 解题之路,并使用 label 进行了分类。 目录 链表
Leetcode:Leetcode提交
:fire: Leetcode :fire: 实践使完美 :party_popper: 开玩笑的单元测试 :sparkles: 简单的代码 :artist_palette: 可读代码 入门指南 git clone https: //github.com/tangweikun/leetcode.git cd leetcode npm ...
idea中leetcode插件Rust 中的 LeetCode 解决方案 怎么跑?...,所有解决方案代码都在leetcode::leetcode::editor::en并重用于leetcode 。 它有一个全局结构Solution ,所有解决方案条目都在其中实现。
LeetCode 101:和你一起你轻松刷题(C++)
leetcode:leetcode刷题
Leetcode:LeetCode解题代码
LeetCode:LeetCode的代码
LeetCode:LeetCode的注释
加油站问题leetcode LeetCode LeetCode-JS分类列表: :smiling_face_with_smiling_eyes: :flushed_face: :winking_face: :face_with_tongue: :face_with_open_mouth: :beaming_face_with_smiling_...
leetcode:LeetCode问题
leetcode:LeetCode题解