刷
July-15-2019
乘法，不同的是，不能一位一位的算了，比如:
9 8 1 4
4 3 2
-------------
1 9 6 2 8
2 9 5 4 2
3 9 2 5 6
M位乘以N位，结果最多是M + N位，所以定义个int[M + N]记录中间解
public String multiply(String num1, String num2) {
int[] res = new int[num1.length() + num2.length()];
if (num1.charAt(0) == '0' || num2.charAt(0) == '0') return "0";
int carry = 0;
for (int i = num1.length() - 1; i >= 0; i --) {
carry = 0;
for (int j = num2.length() - 1; j >= 0; j --) {
int tempTotal = (num1.charAt(i) - '0') * (num2.charAt(j) - '0') + carry + res[i + j + 1];
res[i + j + 1] = tempTotal % 10;
carry = tempTotal / 10;
}
res[i] = carry;
}
StringBuilder sb = new StringBuilder(res[0] == 0 ? "" : Integer.toString(res[0]));
for (int i = 1; i < res.length; i ++) {
sb.append(res[i]);
}
return sb.toString();
}
二刷。
还有印象。
回头看一刷是有问题的，数组定义应该是m+n就可以了，我写了个m*n+1也不知道为毛。。
乘法写竖式是用一个数的每一位去乘另一个数的每一位，最后所有结果加起来。
这里可以确定长为M和N的两个数，最终结果的长度不会超过M+N。
一个数的第i位乘以另一个数的第j位，他们的结果最终会影响i+j位和i+j+1位（如果进位），题里是i+j+1和i+j，因为是反过来的。。。
这样以来就模拟乘法的算法，2个loop分别用num1的每位去乘num2的每位，中间的过程和string1 + string2如出一辙。 2个数组相加是a+b+carry,这里除了这3个还有这一位原来的值，也就是在上一轮计算中可能进位的地方，a + b + carry + res[i + j + 1].
然后是corner cases，其中1个数是0，最后的结果要消除leading Os..
Time Complexity: O(n^2)
Space: O(n)
public class Solution {
public String multiply(String num1, String num2) {
if (num1.length() == 0 || num2.length() == 0) return "";
if (num1.length() == 1 && num1.charAt(0) == '0') return "0";
if (num2.length() == 1 && num2.charAt(0) == '0') return "0";
int[] res = new int[num1.length() + num2.length()];
for (int i = num1.length() - 1; i >= 0; i--) {
int carry = 0;
for (int j = num2.length() - 1; j >= 0; j--) {
int val = (num1.charAt(i) - '0') * (num2.charAt(j) - '0') + carry + res[i + j + 1];
carry = val / 10;
res[i + j + 1] = val % 10;
}
res[i] = carry; // which is actually res[i + j + 1].
}
StringBuilder sb = new StringBuilder();
int i = 0;
while (i < res.length && res[i] == 0) i++;
while (i < res.length) sb.append(res[i++]);
return sb.toString();
}
}
没面试，惨，今年这么难找，找不到我该怎么办。。
不想就这么回去见父母呀。。好压抑。