MultiplyStrings [source code]
public class MultiplyStrings {
static
/******************************************************************************/
class Solution {
public String multiply(String num1, String num2) {
if (num1.equals ("0") || num2.equals ("0"))
return "0";
char[] chs1 = num1.toCharArray (), chs2 = num2.toCharArray ();
int len1 = chs1.length, len2 = chs2.length;
char[] res = new char[len1 + len2];
Arrays.fill (res, '0');
for (int i = 0; i < len2; i++) {
// Main process: Multiply NUM1 by each digit of NUM2, and add to RES at the right offset
char[] prod = multiplyOneDigit (chs1, chs2[i]);
add (res, res.length - (len2 - i), prod);
}
StringBuilder sb = new StringBuilder ();
int i = 0;
while (i < res.length && res[i] == '0')
i++;
for (int j = i; j < res.length; j++)
sb.append (res[j]);
return sb.toString ();
}
// return the char array representation of the product of CHS and the single digit TIMES
char[] multiplyOneDigit (char[] chs, char times) {
char[] res = new char[chs.length + 1];
Arrays.fill (res, '0');
int times_int = times - '0';
for (int i = 0; i < times_int; i++)
add (res, res.length - 1, chs);
return res;
}
// add B to A, with the last digit of B starting backwards at A_END index of A
void add (char[] a, int a_end, char[] b) {
int carry = 0;
for (int i = 0; i <= a_end; i++) {
int digit_a = a[a_end - i] - '0', digit_b = i < b.length ? b[b.length - 1 - i] - '0' : 0;
int sum = digit_a + digit_b + carry;
carry = sum / 10;
a[a_end - i] = (char) (sum % 10 + '0');
}
}
}
/******************************************************************************/
public static void main(String[] args) {
MultiplyStrings.Solution tester = new MultiplyStrings.Solution();
String[] inputs = {
"123", "321", "39483",
"0", "0", "0",
"9", "9", "81",
"2925", "4787", "14001975",
};
for (int i = 0; i < inputs.length / 3; i++) {
String num1 = inputs[3 * i], num2 = inputs[3 * i + 1], ans = inputs[3 * i + 2];
System.out.println (Printer.separator ());
String output = tester.multiply (num1, num2);
System.out.printf ("%s X %s -> %s, expected: %s\n",
num1, num2, Printer.wrapColor (output, output.equals (ans) ? "green" : "red"), ans
);
}
}
}
动笔写一写, 感觉这题最后应该就是用我们正常的做乘法的方式去写; 比如123乘321, 可以转化为123 * 1, 123 * 2, 123 * 3, 然后移位求和就行了; 然后这里面的每一个小乘法, 可以用加法来完成; 之所以分解到这里就不继续往下分解了, 是因为我其实还不清楚这题到底规定的是哪些东西不给用, 比如直接3 * 2这种给不给用; 不过为了保险, 整个就不用乘法. 之前425的时候Prolog也学到了一点乘法的粗暴实现, 那么直接就用那个类似的方法, 用加法来模拟就行了;
另外我记得463当时第一节课好像稍微讲了一下乘法还有更快的实现方式, 不过那个是非常数学的实现方式, 懒得折腾了; 这个题目的downvote并不厉害, 所以最后的答案应该不是那么偏门;
最近做题的时候总是在设计方面纠结太长时间; 虽然说我现在确实可能犯设计错误, 加上一个错误的设计确实有可能导致后面代码越写越难写, 不过我觉得还是不要在这个事情上面太浪费时间; 脑子里大概构思出来一个差不多的设计, 就可以开始写了, 不要总是担心不是最佳方案;
debug了好久, 总算是做出来, 速度是31ms (33%). 讲真的这题思路确实不难, 写这么慢就是纯粹因为基本功不扎实;
做的过程中还是有很多的认识的, 一个一个的来讲;
首先, 在debug的过程当中, char[] res = new char[len1 + len2];这一行实际上一开始我后面还把长度多+10, 因为debug的时候各种出界问题; 实际上, 在你第一个AC之前, 是可以用这种方式来进行一个缓冲的, 等到AC了, 再考虑是不是可以调回去. 等到那个时候再来单独调这个地方, 也好调很多, 毕竟是唯一剩下的一个bug;
我的思路最后需要在最后的结果, 人工skip掉leading zero, 但是后来被test2给break掉: 那如果我要的就全部都是0呢? 这个bug一方面可以通过不停的challenge自己的assumption来进行发现(assumption写在代码旁边comment, 是一个好的习惯, 因为我发现我对于written出来的东西的敏感性, 远高于对于脑子里面的念头的敏感性). 另外一方面, 可以直接通过无脑增加base case这样的思路来完成: 本来乘0的case就可以单独handle;
另外, 也可以看到题目给你的一个小的烟雾弹, 给了你"no leading 0"这个信息, 这个时候就要注意, 可不是说没有0; 要养成这样一个条件反射: no leading 0 -> what about 0 itself?
写的过程中要完成一个比如直接让一个char的digit跟另外一个digit的char相加的操作(这个部分后来debug掉了), 这个不代表你可以直接用'0' + '3'这样的操作! 这样加出来的是乱码. 要实现char的arithmetic, 只能先提取出来offset, 然后offset计算, 然后最后加上base还回去到char;
不等长加法
这个算法最后调的最久的一个bug实际上就是这个加法的函数; 这里这个加法的一个问题是, 假如a和b长度不相等, 怎么处理? 我一开始是直接循环只走b的长度, 然后最后单独考虑carry, 类似收尾, 但是这个很难处理, 因为你一个carry加到a的最高位之后, 最高位可能继续进位, 所以这里还需要另外一个循环来单独处理, 这个处理有点类似之前看到的一个increment问题, 当然你可以再写一个加法循环, 那么为什么干脆不直接两个加法循环合并起来呢?
所以实际上, 不等长加法, 最好的办法就是应该走较长的那个数的长度, 另外一个较短的数, 用sentinel 0来控制一下array access就行了;
最后说一下, 这个题目还是要擅长自己的分析, 一个是题目到底考的是什么, 比如这里其实就是让你用digit来乘, 这样可以利用offset来规避倍数级别的运算量. 不然如果你直接整个数字来乘, 最后就浪费了很多无用的cycle;
另外, 我还是认为我这个算法更加的好, 因为是reduce到一个已知的问题;
没有editorial;
@yavinci said in Easiest JAVA Solution with Graph Explanation:
Remember how we do multiplication?
Start from right to left, perform multiplication on every pair of digits, and add them together. Let's draw the process! From the following draft, we can immediately conclude:
`num1[i] * num2[j]` will be placed at indices `[i + j`, `i + j + 1]`
Here is my solution. Hope it helps!
public String multiply(String num1, String num2) {
int m = num1.length(), 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, p2 = i + j + 1;
int sum = mul + pos[p2];
pos[p1] += sum / 10;
pos[p2] = (sum) % 10;
}
}
StringBuilder sb = new StringBuilder();
for(int p : pos) if(!(sb.length() == 0 && p == 0)) sb.append(p);
return sb.length() == 0 ? "0" : sb.toString();
}
算法本身还是跟我类似的移位加法, 但是他这里是直接自己找到一个规律, 而不是像我这样将题目reduce;
@marcusgao said in Easiest JAVA Solution with Graph Explanation:
I think it might be a problem in
pos[p1] += sum / 10; pos[p2] = (sum) % 10;what if pos[p1] == 9 and sum > 10 ?
这个问题我好像还真没有意识到, 不过重新看了一下代码, 其实不难理解, 看这里int sum = mul + pos[p2];: 这个配合上他循环写的顺序, 最后导致一个类似carry的操作; 这个设计还是挺聪明的;
@aCombray said in Easiest JAVA Solution with Graph Explanation:
@marcusgao This is the genius part of this algorithm. pos[p1] may be an integer greater than 10. But it will get the right digit , i.e. pos[p1] % 10 when the algorithm is working on i -1 - k, j + k in the following loop. The thing is it will always get corrected.
@ChiangKaiShrek said in Brief C++ solution using only strings and without reversal:
This is the standard manual multiplication algorithm. We use two nested for loops, working backward from the end of each input number. We pre-allocate our result and accumulate our partial result in there. One special case to note is when our carry requires us to write to our sum string outside of our for loop.
At the end, we trim any leading zeros, or return 0 if we computed nothing but zeros.
string multiply(string num1, string num2) {
string sum(num1.size() + num2.size(), '0');
for (int i = num1.size() - 1; 0 <= i; --i) {
int carry = 0;
for (int j = num2.size() - 1; 0 <= j; --j) {
int tmp = (sum[i + j + 1] - '0') + (num1[i] - '0') * (num2[j] - '0') + carry;
sum[i + j + 1] = tmp % 10 + '0';
carry = tmp / 10;
}
sum[i] += carry;
}
size_t startpos = sum.find_first_not_of("0");
if (string::npos != startpos) {
return sum.substr(startpos);
}
return "0";
}
类似上面那个算法, 不过区别在于, 他没有意识到可以直接把carry就地存放在i + j位置; 不过他这个算法背后的思想跟上面那个是类似的, 都很依赖这里这个循环的顺序, 不然这个carry其实也是没有意义的: 这个carry要保证最后我们在sum(最终结果)里面的位置始终是不回头的从右往左;
@huzhp said in Brief C++ solution using only strings and without reversal:
I didn't know why it is
sum[i] += carry, notsum[j]or any others?
这个大概自己trace一下就理解了; 不过这个方法, 包括之前那个解法, 我感觉都是很依赖于对index关系的高度观察和归纳; 能够当时看出来倒还好, 如果看不出来, 就很姜;
@lx223 said in AC solution in Java with explanation:
public class Solution {
public String multiply(String num1, String num2) {
int n1 = num1.length(), n2 = num2.length();
int[] products = new int[n1 + n2];
for (int i = n1 - 1; i >= 0; i--) {
for (int j = n2 - 1; j >= 0; j--) {
int d1 = num1.charAt(i) - '0';
int d2 = num2.charAt(j) - '0';
products[i + j + 1] += d1 * d2;
}
}
int carry = 0;
for (int i = products.length - 1; i >= 0; i--) {
int tmp = (products[i] + carry) % 10;
carry = (products[i] + carry) / 10;
products[i] = tmp;
}
StringBuilder sb = new StringBuilder();
for (int num : products) sb.append(num);
while (sb.length() != 0 && sb.charAt(0) == '0') sb.deleteCharAt(0);
return sb.length() == 0 ? "0" : sb.toString();
}
}
If we break it into steps, it will have the following steps. 1. compute products from each pair of digits from num1 and num2. 2. carry each element over. 3. output the solution.
Things to note:
The product of two numbers cannot exceed the sum of the two lengths. (e.g. 99 * 99 cannot be five digit)
int d1 = num1.charAt(i) - '0';
int d2 = num2.charAt(j) - '0';
products[i + j + 1] += d1 * d2;
在看第一个解法的时候, 当理解了那个OP对于carry的处理的时候, 其实我当时脑子里就在构思这个思路; 看来还真的就有人这么写了;
另一个改写:
public class Solution {
public String multiply(String num1, String num2) {
int[] arr = new int[num1.length()+num2.length()];
for(int i = num1.length()-1; i >= 0; i--) {
for(int j = num2.length()-1; j >= 0; j--) {
arr[i+j+1] += (num1.charAt(i)-'0') * (num2.charAt(j)-'0');
arr[i+j] += arr[i+j+1] / 10;
arr[i+j+1] %= 10;
}
}
StringBuilder builder = new StringBuilder();
int i = 0;
while(i < arr.length && arr[i] == 0) i++;
if(i >= arr.length) return "0";
for(int j = i; j < arr.length; j++) {
builder.append(arr[j]);
}
return builder.toString();
}
}
其实就跟第一个差不多了; 不过这个算法的速度其实好像也不快, 比我的还慢一点;
submission最优解: 22(99):
class Solution {
public String multiply(String num1, String num2) {
if (num1.equals("0") || num2.equals("0")) return "0";
int l1 = num1.length(), l2 = num2.length(), l = l1 + l2;
char[] ans = new char[l];
char[] c1 = num1.toCharArray();
char[] c2 = num2.toCharArray();
for (int i = l1 - 1; i >= 0; --i) {
int c = c1[i] - '0';
for (int j = l2 - 1; j >= 0; --j) {
ans[i + j + 1] += c * (c2[j] - '0');
}
}
for (int i = l - 1; i > 0; --i) {
if (ans[i] > 9) {
ans[i - 1] += ans[i] / 10;
ans[i] %= 10;
}
}
StringBuilder sb = new StringBuilder();
int i = 0;
for (; ; ++i) if (ans[i] != 0) break;
for (; i < ans.length; ++i) sb.append((char) (ans[i] + '0'));
return sb.toString();
}
}
好像就是那个最后单独处理carry的算法; 那个算法确实不错, 非常的intuitive, 而且好理解;
Problem Description
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.
Difficulty:Medium
Total Accepted:129K
Total Submissions:462.9K
Contributor:LeetCode
Companies
facebooktwitter
Related Topics
mathstring
Similar Questions
Add Two NumbersPlus OneAdd BinaryAdd Strings