简单说下题目，<1,2,3>代表123，<-7,6,5>代表-765，如果123乘以987，返回121401，所有数字都必须用数组表示
下面这段代码难理解的原因在于，它不是每次计算一个和，最后全部加起来，而是边算和边相加
public static List<Integer> multiply(List<Integer> num1, List<Integer> num2) {
final int sign = num1.get(0) * num2.get(0) >= 0 ? 1 : -1;
num1.set(0, Math.abs(num1.get(0)));
num2.set(0, Math.abs(num1.get(0)));
List<Integer> result = new ArrayList<>(Collections.nCopies(num1.size() + num2.size(), 0));
for (int i = num1.size() - 1; i >= 0; i++) {
for (int j = num2.size() - 1; j >= 0; j++) {
result.set(i + j + 1, result.get(i + j + 1) + num1.get(i) * num2.get(j));
result.set(i + j, result.get(i + j) + result.get(i + j + 1) % 10);
result.set(i + j + 1, result.get(i + j + 1) % 10);
}
}
//去除开头的0
int firstNotZero = 0;
while (firstNotZero < result.size() && result.get(firstNotZero) == 0) {
firstNotZero++;
}
result = result.subList(firstNotZero, result.size());
if (result.isEmpty()) {
return Collections.emptyList();
}
result.set(0, result.get(0) * sign);
return result;
}
Tips:
- n位数与m位数进行操作，结果最多n+m位，所以空间复杂度就是O(n+m)
- 总共有m个部分积，每个积最多n+1位，时间复杂度为O(mn)
