![Uploading Paste_Image_697854.png . . .]
My code:
public class Solution {
public String multiply(String num1, String num2) {
if (num1 == null || num1.length() == 0 || num2 == null || num2.length() == 0)
return null;
int len = num1.length() + num2.length();
int[] carry = new int[len];
for (int i = num1.length() - 1; i >= 0; i--) {
int temp1 = num1.charAt(i) - 48;
for (int j = num2.length() - 1; j >= 0; j--) {
int temp2 = num2.charAt(j) - 48;
int mul = temp1 * temp2;
int baseI = num1.length() - i - 1;
int baseJ = num2.length() - j - 1;
carry[baseI + baseJ] += mul;
carry[baseI + baseJ + 1] += carry[baseI + baseJ] / 10;
carry[baseI + baseJ] = carry[baseI + baseJ] % 10;
}
}
if (carry[len - 2] >= 10) {
carry[len - 1] = carry[len - 2] / 10;
carry[len - 2] = carry[len - 2] % 10;
}
int resultLen = 0;
if (carry[len - 1] == 0)
resultLen = len - 1;
else
resultLen = len;
String str = "";
for (int i = resultLen - 1; i >= 0; i--)
str += (char) (carry[i] + 48);
for (int i = 0; i < resultLen; i++) {
if (str.charAt(0) == '0') {
if (i != resultLen - 1)
str = str.substring(1, str.length());
}
else
break;
}
return str;
}
public static void main(String[] args) {
Solution test = new Solution();
System.out.println(test.multiply("1234", "0"));
}
}
My test result:
这次作业思路不难，就是实现起来有点繁杂。具体如下。我的例子是
1 2 3 4 *
5 6 7
_________________________________
x x x x
x x x x
x x x x
-----------------------------
x x x x x x x
我设置了一个carry数组来记录每一次乘法后的结果。
比如第一次是， 1 2 3 4 *
7
-------------
8 6 3 8
那么 carry [7]---- 7 6 5 4 3 2 1 0
-> 0 0 0 0 8 6 3 8
然后第二轮相乘是， 1 2 3 4 *
6
-------------------------------
那么首先， 4 * 6 = 24； 再加上原先此位的carry[1] = 3; 即，
24 + 3 = 27； 将大于等于10的进位到前一位，
2 -> 进位到前一位， 即 carry[baseI + baseJ + 1] = carry[baseI + baseJ] / 10;
7 -> 保留在当前carry位。
于是，carry [7]---- 7 6 5 4 3 2 1 0
0 0 0 0 8 6 3 8
-> 0 0 0 0 8 8 7 8
然后接着进行 3 * 6 = 18;那么carry变化为：
carry [7] ---- 7 6 5 4 3 2 1 0
0 0 0 0 8 6 3 8
0 0 0 0 8 8 7 8
-> 0 0 0 0 10 6 7 8
2 * 6 = 12；
carry [7] ---- 7 6 5 4 3 2 1 0
0 0 0 0 8 6 3 8
0 0 0 0 8 8 7 8
0 0 0 0 10 6 7 8
-> 0 0 0 2 2 6 7 8
1 * 6 = 6；
carry [7] ---- 7 6 5 4 3 2 1 0
0 0 0 0 8 6 3 8
0 0 0 0 8 8 7 8
0 0 0 0 10 6 7 8
0 0 0 2 2 6 7 8
-> 0 0 0 8 2 6 7 8
这个结果就是 1234 * 67的
之后多了一个5，也是以此类推。
**
总结：这次题目还好了。
记住了， 数字0 到字符0， 相差dec(48)， OX30.
字符0 - 9 ： OX30 - OX39 0 - 9
字符A - Z ： OX41 - OX5A 65 - 90
字符a - z ： OX61 - OX7A 97 - 122
所以，字符A到a 相差：相差dec(32)， OX20.
**
Anyway, Good luck, Richardo!
My code:
public class Solution {
public String multiply(String num1, String num2) {
if (num1 == null || num1.length() == 0 || num2 == null || num2.length() == 0)
return null;
/** move insignificant digits to left, easy to be operated later */
StringBuilder num1StrB = new StringBuilder(num1).reverse();
StringBuilder num2StrB = new StringBuilder(num2).reverse();
int[] ret = new int[num1.length() + num2.length()];
/** calculate every multiplication, store results into every digit including carry */
for (int i = 0; i < num1StrB.length(); i++) {
for (int j = 0; j < num2StrB.length(); j++) {
ret[i + j] += (num1StrB.charAt(i) - '0') * (num2StrB.charAt(j) - '0');
}
}
StringBuilder sb = new StringBuilder();
/** deal with carry. separate carry and mod from each digit */
for (int i = 0; i < ret.length; i++) {
int mod = ret[i] % 10;
int carry = ret[i] / 10;
if (i < ret.length - 1)
ret[i + 1] += carry;
sb.insert(0, mod); // move insignificant digits to the right
}
/** delete meaningless 0 on the left */
while (sb.charAt(0) == '0' && sb.length() > 1) {
sb.deleteCharAt(0);
}
return sb.toString();
}
}
看了下之前自己写的，好复杂。
然后看了下网上的答案，自己写了下。这种题目还是看下答案。本身没多大意义。而且网上答案更加简洁易懂。
参考网址如下：
http://www.programcreek.com/2014/05/leetcode-multiply-strings-java/
就是先把每一位都乘一下，不进位，把每个结果都保存在相应的digit里面。
然后再统一处理进位。
最后，再除去左边多出来的一些0.
同时， StringBuilder sb.insert(0, mod);
就是在index = 0 处插入mod，如果已经有值了，就把现有值往右边移动。
deleteCharAt(0) 就是删除index = 0 处的值，然后不停地左移。
Anyway, Good luck, Richardo!
My code:
public class Solution {
public String multiply(String num1, String num2) {
if (num1 == null || num1.length() == 0 || num2 == null || num2.length() == 0) {
return "";
}
int m = num1.length();
int n = num2.length();
int[] pos = new int[m + n];
for (int i = m - 1; i >=0; i--) {
for (int j = n - 1; j >= 0; j--) {
int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
int p1 = i + j;
int p2 = i + j + 1;
int sum = mul + pos[p2];
pos[p1] += sum / 10;
pos[p2] = sum % 10;
}
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < pos.length; i++) {
if (!(sb.length() == 0 && pos[i] == 0)) {
sb.append(pos[i]);
}
}
if (sb.length() == 0) {
sb.append('0');
}
return sb.toString();
}
}
reference:
https://discuss.leetcode.com/topic/30508/easiest-java-solution-with-graph-explanation
直接看的答案。很简洁。
其实更像是找规律。
Anyway, Good luck, Richardo! -- 09/19/2016
