题目描述:
给定两个以字符串形式表示的非负整数 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)或直接将输入转换为整数来处理。
题目难度:中等
分析:
在题目的限制下,可以使用传统的数学思维解答这题。就是小学的那种竖式计算,应该不用解释原理了吧。。。(还有更好的办法,不过意义不大)。
代码如下:
class Solution { public String multiply(String num1, String num2) { // 如果其中一个是0的话,就返回0即可 if ("0".equals(num1) || "0".equals(num2)) { return "0"; } // 这里就是分别把num1与num2的所有位数相乘,结果保存在List集合中 List<String> resList = new ArrayList<>(); for (int i = num2.length() - 1; i >= 0; i--) { int temp2 = num2.charAt(i) - '0'; int carry = 0; StringBuilder sb = new StringBuilder(); for (int j = num1.length() - 1; j >= 0; j--) { int temp1 = num1.charAt(j) - '0'; int n = temp1 * temp2 + carry; carry = n / 10; sb.append(n % 10); } if (carry > 0) { sb.append(carry); } resList.add(sb.toString()); } // 经过循环运算以后就会得出几组数字,竖式需要错位相加 StringBuilder sb = new StringBuilder(); sb.append(resList.get(0)); for (int i = 1; i < resList.size(); i++) { String s1 = sb.toString(); String s2 = resList.get(i); sb.delete(0, sb.length()); int carry = 0; for (int j = 0; j < Math.max(s1.length(), s2.length() + i); j++) { int n1; // 这里判断charAt是否会越界,越界补0 try { n1 = s1.charAt(j) - '0'; } catch (StringIndexOutOfBoundsException e) { n1 = 0; } int n2 = 0; if (j >= i) { try { n2 = s2.charAt(j - i) - '0'; } catch (StringIndexOutOfBoundsException ignored) { } } int sum = n1 + n2 + carry; carry = sum / 10; sb.append(sum % 10); } if (carry > 0) { sb.append(carry); } } // 此时的s就是最终答案,不过是反着的,因为都是从个位开始相加,结果却保存在前面,所以需要倒序输出 String s = sb.toString(); sb.delete(0, sb.length()); for (int i = s.length() - 1; i >= 0; i--) { sb.append(s.charAt(i)); } return sb.toString(); } }
总结:
利用数学思维也可解答,虽然方法比较笨,但是小学生都能明白为什么这么计算,比较好理解,所以放出来给大家参考,当然也可以采用其他同学的高效率方法。