In August, I will do at least one problem in Leetcode every day. Since September, I have been a little slack. I hope I can keep it up. Only by learning and making progress every day can the sense of smell be maintained. In the application scenarios of the algorithm, the sense of smell will be a little more sensitive. It can be used when there are appropriate scenarios.

Today’s problem is leetcode 43, the topic is relatively water, there is no idea of algorithm, as to practice the basic programming.

The title

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, whose product is also represented as strings.

Example 1: Input: num1 = “2”, num2 = “3” Output: “6”

Example 2: Input: num1 = “123”, num2 = “456” Output: “56088”

Note: The length of num1 and num2 is less than 110. Num1 and num2 contain only the numbers 0-9. Num1 and num2 do not begin with zero, except in the case of the number 0 itself. You cannot process it using any of the standard library large number types (such as BigInteger) or by converting the input directly to an integer.

Train of thought

I almost laughed when I saw the last one in the instructions. Actually, I did this in school many years ago, and one of my classmates did it with Java BigDecimal. Of course, this is meaningless, but let’s look at the general solution.

Back in elementary school, multiplying multiple digits means taking one number apart bit by bit, multiplying it with another number, and then adding the sum. So we’re going from multiplying multiple digits to multiplying one digit by multiple digits; And then it simplifies even further to one digit times one digit plus.

We now use the program to solve, is to simulate the process, as shown in the following figure

Of course, there are some points to pay attention to when doing this problem: Is multiplied by 1, pay attention to the zero padding, bit by bit, high to do multiplication, followed by zero padding, as shown in the above vertical 2, Numbers can be long, intermediate results also expressed in the array, use the integer may overflow finished 3, although the original string traversal, but there may be up from low carry array, don’t lost

So, we also need an implicit function, which is the addition of two string numbers, which is leetCode 415, string addition

Java version code

class Solution { public String multiply(String num1, String num2) { String ans = "0"; if ("0".equals(num1) || "0".equals(num2)) { return ans; } int len1 = num1.length(); int len2 = num2.length(); for (int i = len2 - 1; i >= 0; i--) { int adddition = 0; int n2 = num2.charAt(i) - '0'; StringBuilder temp = new StringBuilder(); Int need = len2-1-i; int need = len2-1-i; while (need-- > 0) { temp.append("0"); } for (int j = len1 - 1; j >= 0; j--) { int n1 = num1.charAt(j) - '0'; int num = n2 * n1 + adddition; temp.append(num % 10); adddition = num / 10; } if (adddition > 0) { temp.append(adddition); } ans = addStrings(ans, temp.reverse().toString()); } return ans; } public static String addStrings(String num1, String num2) { int i = num1.length() - 1; int j = num2.length() - 1; // carry int addedition = 0; StringBuilder ans = new StringBuilder(); while (i >=0 || j >=0 || adddition > 0) { int temp = 0; if (i >= 0) { temp += num1.charAt(i) - '0'; i--; } if (j >= 0) { temp += num2.charAt(j) - '0'; j--; } if (adddition > 0) { temp += adddition; } ans.append(temp % 10); adddition = temp / 10; } return ans.reverse().toString(); }}Copy the code