题目：
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.
分析：
任意长度非负整数乘法。
基本思路就是模拟用竖式手算乘法的过程。
注意处理进位和乘0的情况。
代码：
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
public class Solution { public String multiply(String num1, String num2) { // Mind the case of multiplication with 0 if(num1.equals("0") || num2.equals("0")) return "0"; StringBuilder sb = new StringBuilder(); int[][] temp = new int[num2.length()][num1.length() + num2.length()]; for(int i = num2.length() - 1; i >= 0; i--){ int d2 = num2.charAt(i) - '0'; int carry = 0; for(int j = num1.length() - 1; j >= 0; j--){ int d1 = num1.charAt(j) - '0'; int product = d1 * d2 + carry; temp[i][j + i + 1] = product % 10; carry = product / 10; } temp[i][i] = carry; } int carry = 0; for(int j = num1.length() + num2.length() - 1; j >= 0; j--){ int sum = 0; for(int i = 0; i < num2.length(); i++){ sum += temp[i][j]; } sum += carry; sb.append(sum % 10); carry = sum / 10; } if(sb.charAt(sb.length() - 1) == '0') sb.deleteCharAt(sb.length() - 1); return sb.reverse().toString(); } } |