首页 > 代码库 > LeetCode: Multiply Strings 解题报告
LeetCode: Multiply Strings 解题报告
Multiply Strings
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.
SOLUTION 1:
参考自http://blog.csdn.net/fightforyourdream/article/details/17370495
相当优雅的算法，主页君稍微改进，把翻转String这一步拿掉了。比起一般的做法，这个算法很容易就BUG FREE.
思路：
1 建立数组，双层循环遍历两个string，把单位的乘积累加到数组相应的位置
2 处理进位并输出
3 注意前导零的corner case
1 public class Solution { 2 public String multiply(String num1, String num2) { 3 if (num1 == null || num2 == null) { 4 return null; 5 } 6 7 int len1 = num1.length(); 8 int len2 = num2.length(); 9 10 int[] product = new int[len1 + len2];11 12 // 计算相应位置的product.13 for (int i = 0; i < len1; i++) {14 for (int j = 0; j < len2; j++) {15 // 注意，这里要使用+=以不断累加乘积16 product[i + j] += (num1.charAt(len1 - 1 - i) - ‘0‘) * (num2.charAt(len2 - 1 - j) - ‘0‘);17 }18 }19 20 StringBuilder ret = new StringBuilder();21 22 int carry = 0;23 // 计算进位24 for (int i = 0; i < len1 + len2; i++) {25 product[i] = product[i] + carry;26 int digit = product[i] % 10;27 carry = product[i] / 10;28 ret.insert(0, digit);29 }30 31 // 去掉前导032 while (ret.length() > 1 && ret.charAt(0) == ‘0‘) {33 ret.deleteCharAt(0);34 }35 36 return ret.toString();37 }38 }
请至主页群GITHUB:
https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/string/Multiply.java
LeetCode: Multiply Strings 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。