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.
以下文字描述来自这里:
- 直接乘会溢出,所以每次都要两个single digit相乘,最大81,不会溢出。
- 比如385 * 97, 就是个位=5 * 7,十位=8 * 7 + 5 * 9 ,百位=3 * 7 + 8 * 9 …可以每一位用一个int表示,存在一个int[]里面。
- 这个数组最大长度是num1.len + num2.len,比如99 * 99,最大不会超过10000,所以4位就够了。
- 这种个位在后面的,不好做(10的0次方,可惜对应位的数组index不是0而是n-1),所以干脆先把string reverse了代码就清晰好多。
- 最后结果前面的0要清掉。
// 2 3 4 // × 5 6 7 //------------------------ // 14 21 28 // 12 18 24 // + 10 15 20 //------------------------ // 10 27 52 45 28 //------------------------ // 1 3 2 6 7 8 public String multiply(String num1, String num2) { String n1 = new StringBuilder(num1).reverse().toString(); String n2 = new StringBuilder(num2).reverse().toString(); int[] m = new int[n1.length()+n2.length()]; for(int i=0; i<n1.length(); i++) { int a = n1.charAt(i)-'0'; for(int j=0; j<n2.length(); j++) { m[i+j] += a*(n2.charAt(j)-'0'); } } int carry = 0; StringBuilder sb = new StringBuilder(); for(int i=0; i<m.length; i++) { int sum = m[i]+carry; carry = sum / 10; int digit = sum % 10; sb.append(digit); } for(int i=sb.length()-1; i>0; i--) { if(sb.charAt(i) == '0') { sb.deleteCharAt(i); } else { break; } } return sb.reverse().toString(); }
另外一种写法,这种更好理解:
public String multiply(String num1, String num2) { int[] A = toDigits(num1); int[] B = toDigits(num2); int m = A.length, n = B.length; int[] C = new int[m+n]; for(int i=0; i<m; i++) { for(int j=0; j<n; j++) { C[i+j] += A[i] * B[j]; } } int carry = 0; int nonZeroIdx = 0; //最后一个非零元素的下标,也就是最高位的索引 for(int i=0; i<C.length; i++) { int sum = C[i] + carry; carry = sum / 10; C[i] = sum % 10; if(C[i] != 0) { nonZeroIdx = i; } } StringBuilder sb = new StringBuilder(); for(int i=nonZeroIdx; i>=0; i--) { sb.append(C[i]); } return sb.toString(); } private int[] toDigits(String num) { int n = num.length(); int[] digits = new int[n]; for(int i=0; i<n; i++) { digits[i] = num.charAt(n-i-1) - '0'; } return digits; }
相关推荐
《leetcode-solutions》,刷算法题,需要有一定的英文阅读能力。。。
Algorithm-LeetCode-Sol-Res.zip,干净,易懂的解决方案和资源,为leetcode在线判断算法问题。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
IDEA 插件,lettcode刷题,leetcode-editor7.4版本下载进行本地导入(直接将压缩包拖进IDEA即可)
Algorithm-leetcode-spider.zip,leetcode公司,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
在IDE中解决LeetCode问题,支持leetcode.com与leetcode-cn.com,满足基本的做题需求。 理论上支持: IntelliJ IDEA PhpStorm WebStorm PyCharm RubyMine AppCode CLion GoLand DataGrip Rider MPS Android Studio。
leetcode-cli-plugins leetcode-cli 的第 3 方插件。 什么是 如何使用 如何使用 插件 名称 描述 增强的命令 按公司或标签过滤问题 list 不要在同一台计算机上使 Chrome 的会话过期 login 不要在同一台计算机上使 ...
解题思路思路和LeetCode-python 503.下一个更大元素 II一致,只是这里求的是下标的距离,而不是数值倒序搜索,用到栈,栈里存储索引情况1:若栈为
leetcode-cheat 的发布 它是什么 ? 这是一个chrome 扩展,可以帮助您更高效地使用 leetcode。您可以从 重要: leetcode-cheat 现在只支持中文版。 也就是说不完全支持leetcode.com,但是你可以用leetcode-cn.com代替...
leetcode 答案解析 golang解答
leetcode-editor,在ide中做leetcode练习,支持leetcode.com和leetcode-cn.com,以满足练习的基本需求。理论上支持:intellij idea phpstorm webstorm pycharm rubymine appcode clion goland datagrip rider mps ...
~/.vscode/extensions/leetcode.vscode-leetcode-0.17.0/node_modules/vsc-leetcode-cli/bin/leetcode /usr/local/bin/leetcode 修改模板 open ~/.vscode/extensions/leetcode.vscode-leetcode-0.17.0/node_modules/...
leetcode-helper-1.7.1
然后进入到LeetCode-Spider目录中修改config.json,其中outputDir需要填写该工程的/docs/views文件夹路径 { "username": "aaa", "password": "bbb", "outputDir": "/Users/liuyao/Downloads/LeetCode-Blog-Test/docs...
leetcode-cli 注意:这个存储库是为了临时使用而分叉的。 注意:从 webbrowser 复制 cookie 并使用leetcode user -c可以临时修复不能。 一个享受 leetcode 的高效 cli 工具! 非常感谢 leetcode.com,一个非常棒的...
leetcode-tag-dynamic programming
leetcode-tag-Tree
leetcode-tag-Stack
leetcode-tag-array
Algorithm-LeetCode-Solution-From-GuaZiDou.zip,Leetcode解决方案Gitbook,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。