主要收获
证实了String的拼接开销很大。就算用了StringBuilder也是一样。换做Arrays#copyOf()和Arrays.copyOfRange()会快很多。这题快了6倍。
题目
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.
0~9的乘法，然后进位
加法和乘法都是一个模式，1024 * 25，每一位都拎出来乘。每次都是两个0~9的数字相乘，每次都记上进位。
00120 //进位
1024
5 *
----------
5120
加法也是一样，
110 //进位
99
99 +
--------
198
代码
public class Solution {
public String multiply(String num1, String num2) {
String res = "0";
for (int i = num1.length()-1; i >= 0; i--) {
int multi1 = num1.charAt(i) - '0';
StringBuilder sb = new StringBuilder();
int carry = 0;
for (int j = num2.length()-1; j >= 0; j--) {
int multi2 = num2.charAt(j) - '0';
int product = multi1 * multi2 + carry;
sb.insert(0,product % 10);
carry = product / 10;
}
if (carry > 0) { sb.insert(0,carry); }
if (sb.charAt(0) != '0') {
for (int k = 0; k < num1.length()-1-i; k++) {
sb.append("0");
}
res = plus(res,sb.toString());
}
}
return res;
}
public String plus(String first, String second) {
StringBuilder sb = new StringBuilder();
int carry = 0;
for (int i = first.length() - 1, j = second.length() - 1; i >= 0 || j >= 0; i--,j--) {
int num1 = 0, num2 = 0;
if (i >= 0) { num1 = first.charAt(i) - '0'; }
if (j >= 0) { num2 = second.charAt(j) - '0'; }
int sum = num1 + num2 + carry;
sb.insert(0,(sum%10));
carry = sum / 10;
}
if (carry == 1) { sb.insert(0,"1"); }
System.out.println(first + " + " + second + " = " + sb.toString());
return sb.toString();
}
}
结果
对是对，但不够好，算法层面没找到好方法。银弹的速度是我的5，6倍。
缓存9*9乘法表
想法是用二维数组缓存9*9乘法表，用table[num1][num2]数组随机访问来代替num1 * num2的乘法操作。
代码
public class Solution {
int[][] table = new int[][] { // 9*9乘法表
{0,0,0,0,0,0,0,0,0,0},
{0,1,2,3,4,5,6,7,8,9},
{0,2,4,6,8,10,12,14,16,18},
{0,3,6,9,12,15,18,21,24,27},
{0,4,8,12,16,20,24,28,32,36},
{0,5,10,15,20,25,30,35,40,45},
{0,6,12,18,24,30,36,42,48,54},
{0,7,14,21,28,35,42,49,56,63},
{0,8,16,24,32,40,48,56,64,72},
{0,9,18,27,36,45,54,63,72,81}
};
public String multiply(String num1, String num2) {
String res = "0";
for (int i = num1.length()-1; i >= 0; i--) {
int multi1 = num1.charAt(i) - '0';
StringBuilder sb = new StringBuilder();
int carry = 0;
for (int j = num2.length()-1; j >= 0; j--) {
int multi2 = num2.charAt(j) - '0';
int product = table[multi1][multi2]+ carry;
sb.insert(0,product % 10);
carry = product / 10;
}
if (carry > 0) { sb.insert(0,carry); }
if (sb.charAt(0) != '0') {
for (int k = 0; k < num1.length()-1-i; k++) {
sb.append("0");
}
res = plus(res,sb.toString());
}
}
return res;
}
public String plus(String first, String second) {
StringBuilder sb = new StringBuilder();
int carry = 0;
for (int i = first.length() - 1, j = second.length() - 1; i >= 0 || j >= 0; i--,j--) {
int num1 = 0, num2 = 0;
if (i >= 0) { num1 = first.charAt(i) - '0'; }
if (j >= 0) { num2 = second.charAt(j) - '0'; }
int sum = num1 + num2 + carry;
sb.insert(0,(sum%10));
carry = sum / 10;
}
if (carry == 1) { sb.insert(0,"1"); }
System.out.println(first + " + " + second + " = " + sb.toString());
return sb.toString();
}
}
结果
没什么效果，看来问题不在这儿。
不用StringBuilder拼接，直接操作char[]，快了6倍
接下来，猜测会不会是String操作，以及StringBuilder的拼接开销太大。毕竟刚开始使用StringBuilder拼接，是为了让代码保持简洁，自己也更专注于算法逻辑。
所以，下面的代码，一上来就把String转成char[]，后面都直接操作char[]，参数也直接传char[]。
代码
public class Solution {
public String multiply(String num1, String num2) {
char[] chars1 = num1.toCharArray();
char[] chars2 = num2.toCharArray();
char[] res = new char[]{'0'};
for (int i = chars2.length-1; i >= 0; i--) {
char[] temp = multi(chars1,chars2[i],chars2.length-1-i);
res = plus(res,temp);
}
return new String(res);
}
public char[] multi(char[] num1, char num2, int zero) {
if (num1[0] == '0' || num2 == '0') { return new char[]{'0'}; }
char[] res = new char[num1.length+1+zero];
for (int i = 0; i < zero; i++) {
res[num1.length+1+i] = '0';
}
int carry = 0;
int int2 = num2 - '0';
for (int i = num1.length-1; i >=0; i--) {
int product = (num1[i]-'0') * int2 + carry;
res[i+1] = (char)((product % 10) + '0');
carry = product / 10;
}
res[0] = (char)(carry + '0');
return (carry == 0)? Arrays.copyOfRange(res,1,res.length):res;
}
public char[] plus(char[] first, char[] second) {
int length = Math.max(first.length, second.length);
char[] res = new char[length+1];
int carry = 0;
for (int i = first.length - 1, j = second.length - 1; i >= 0 || j >= 0; i--,j--) {
int num1 = 0, num2 = 0;
if (i >= 0) { num1 = (first[i] - '0'); }
if (j >= 0) { num2 = (second[j] - '0'); }
int sum = num1 + num2 + carry;
res[length--] = (char)((sum % 10) + '0');
carry = sum / 10;
}
res[0] = (char)(carry + '0');
return (carry == 0)? Arrays.copyOfRange(res,1,res.length):res;
}
}
结果
足足快了6倍。证明StringBuilder的拼接，以及和String之间的转换开销非常大。并不一定说遇到String就要用char[]代替，但 遇到要拼接字符串，用Arrays#copyOf()和Arrays#copyOfRange()会快很多。
数学过程更好的抽象
i位数和j位数相乘，最多只有i+j位数。如下图所示，乘法过程可以抽象成下面这个在i+j位上累加的过程，
这样，可以更好地把操作集中到一个char[]上。
代码
public class Solution {
public String multiply(String num1, String num2) {
char[] c1 = num1.toCharArray();
char[] c2 = num2.toCharArray();
if (c1[0] == '0' || c2[0] == '0') { return "0"; }
int[] result = new int[c1.length+c2.length];
for (int i = 0; i < c1.length; i++) {
for (int j = 0; j < c2.length; j++) {
int product = (c1[i] - '0') * (c2[j] - '0');
result[i+j] += product / 10;
result[i+j+1] += product % 10;
}
}
int carry = 0;
for (int i = result.length-1; i >= 0; i--) {
int val = result[i] + carry;
result[i] = val % 10;
carry = val / 10;
}
StringBuilder sb = new StringBuilder();
for (int i = (result[0] == 0)? 1:0; i < result.length; i++) {
sb.append(result[i]);
}
return sb.toString();
}
}
结果
真银弹！
