43. Multiply Strings

43. Multiply Strings

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.

class Solution { public String multiply(String num1, String num2) { int m = num1.length(), n = num2.length(); int[] pos = new int[m + n]; // 0是最高位 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'); // p1代表进位， p2表示本位。 int p1 = i + j, p2 = i + j + 1; // sum 就是本位的乘积加上本位已有的值。 int sum = mul + pos[p2]; // 进位就是除以10的余数 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(); }}

class Solution { public String multiply(String num1, String num2) { int firstLength = num1.length(); int secondLength = num2.length(); StringBuilder sb = new StringBuilder(); int[] resArr = new int[firstLength + secondLength]; for(int i= firstLength-1; i>=0; i-- ){ for(int j= secondLength-1; j>=0; j-- ){ int temp = (num1.charAt(i)-'0')*(num2.charAt(j)-'0'); temp += resArr[i+j+1]; resArr[i+j+1] = temp%10; resArr[i+j] += temp/10; } } boolean nonZeroFound = false; for(int i : resArr){ if(i != 0) nonZeroFound = true; if(nonZeroFound) sb.append(i); } if(!nonZeroFound) sb.append("0"); return sb.toString(); }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。