![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:
這次作業(yè)思路不難，就是實(shí)現(xiàn)起來(lái)有點(diǎn)繁雜。具體如下秃殉。我的例子是
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
我設(shè)置了一個(gè)carry數(shù)組來(lái)記錄每一次乘法后的結(jié)果。
比如第一次是郭脂， 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的進(jìn)位到前一位，
2 -> 進(jìn)位到前一位蟋恬， 即 carry[baseI + baseJ + 1] = carry[baseI + baseJ] / 10;
7 -> 保留在當(dāng)前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
然后接著進(jìn)行 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
這個(gè)結(jié)果就是 1234 * 67的
之后多了一個(gè)5，也是以此類推矾飞。
**
總結(jié)：這次題目還好了一膨。
記住了， 數(shù)字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();
}
}
看了下之前自己寫(xiě)的瞒津，好復(fù)雜。
然后看了下網(wǎng)上的答案括尸，自己寫(xiě)了下巷蚪。這種題目還是看下答案。本身沒(méi)多大意義濒翻。而且網(wǎng)上答案更加簡(jiǎn)潔易懂屁柏。
參考網(wǎng)址如下：
http://www.programcreek.com/2014/05/leetcode-multiply-strings-java/
就是先把每一位都乘一下，不進(jìn)位有送，把每個(gè)結(jié)果都保存在相應(yīng)的digit里面淌喻。
然后再統(tǒng)一處理進(jìn)位。
最后雀摘，再除去左邊多出來(lái)的一些0.
同時(shí)裸删， StringBuilder sb.insert(0, mod);
就是在index = 0 處插入mod，如果已經(jīng)有值了阵赠，就把現(xiàn)有值往右邊移動(dòng)涯塔。
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
直接看的答案伤塌。很簡(jiǎn)潔。
其實(shí)更像是找規(guī)律轧铁。
Anyway, Good luck, Richardo! -- 09/19/2016
