Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.
Example 1:
Input: num1 = "2", num2 = "3" Output: "6"Example 2:
Input: num1 = "123", num2 = "456" Output: "56088"Note:
The length of both num1 and num2 is < 110.Both num1 and num2 contain only digits 0-9.Both num1 and num2 do not contain any leading zero, except the number 0 itself.You must not use any built-in BigInteger library or convert the inputs to integer directly.
题意：
高精度乘法。
Solution1： Math
Do the simulation like how computer will do multiplication operation
1一个char对应1个digit，
digit相乘后，注意其乘积结果可能需要进位
code
1 /* 2 Time: O(n^2). We use nested 2 for loop 3 Space: O(n). We use int[] to save intermedia infor 4 */ 5 6 class Solution { 7 public String multiply(String num1, String num2) { 8 if(num1.length()==0 || num2.length()==0) return "0"; 9 int len1 = num1.length(); 10 int len2 = num2.length(); 11 int [] result = new int [len1+len2]; 12 13 for(int i = len1-1; i>=0; i--){ 14 for(int j = len2-1; j>=0;j--){ 15 int mul = (num1.charAt(i)-'0')*(num2.charAt(j)-'0'); 16 int idx = i+j+1; 17 // 可能会进位 18 int carryIdx = i+j; 19 mul = mul + result[idx]; 20 result[idx] = mul % 10; 21 result[carryIdx] = result[carryIdx] + mul/10; 22 } 23 } 24 StringBuilder sb = new StringBuilder(); 25 for(int res: result){ 26 if(sb.length()!=0 || res!=0) sb.append(res); 27 } 28 return (sb.length() == 0)? "0" : sb.toString(); 29 } 30 }
转载于:https://www.cnblogs.com/liuliu5151/p/10708512.html
