This is the 10th day of my participation in the August More Text Challenge. For details, see:August is more challenging

preface

Force 43 string multiplication as follows:

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"Copy the code

Example 2:

Num1 = "123", num2 = "456" output: "56088"Copy the code

A, thinking

The product of two non-negative integers represented as strings is represented as strings

They explicitly said you can’t use large numbers, so you can’t just multiply them. So since we’re trying to get a product, it’s not hard to think of using vertical to simulate multiplication.

There are two rules when two numbers are multiplied (neither of which is zero) :

  1. MAnd theNThe number of bits is multiplied, and the number of bits isM+N 或 M+N-1(There may be no carry, e.g999 x 10 is 9990, and the product is four bits)
  2. nums1[i] * nums2[j]As the result of theXY.XThe high order is the product with the subscript[i+j]The value of theYThe low order is the product with the subscript[i+j+1](the left is the highest in the string)

Tips: As shown in the figure below, 18 is the product of nums1[2] and nums[2]. So the position of low 8 in the product is 5, and the position of high 1 is 4

So we can easily take the product of the two, and turn that product into a string.

For example

Int [] ret: array of product results

In example 2, num1 = “123”, num2 = “456” as an example, the specific steps are as follows:

  1. I = 2, j = 2When,nums1[2] * nums2[2] = 18, therefore,ret[5]=8, ret[4]=1. As shown in the figure below:

  1. I = 2, j = 1When,nums1[2] * nums2[1] = 16(need to add the previous carry), soret[4]=6, ret[3]=1. As shown in the figure below:

  1. I = 2, j = 0When,nums1[2] * nums2[0] = 13(need to add the previous carry), soret[3]=3, ret[2]=1. As shown in the figure below:

  1. . , I =1 and I =0, the steps are the same, so omit.

  2. Get the final result: ret=[0, 5, 6, 0, 8, 8]

  3. So convert to the string bit “56088”

Second, the implementation

The implementation code

The implementation code is consistent with the idea

    public String multiply(String num1, String num2) {
        // Special case handling
        if ("0".equals(num1) || "0".equals(num2)) {
            return "0";
        }
        int[] ret = new int[num1.length() + num2.length()];
        // From low to high, that is, from right to left
        for (int i=num1.length()-1; i>-1; i--) {
            int n1 = (int)num1.charAt(i) - (int) ('0');
            for (int j=num2.length()-1; j>-1; j--) {
                int n2 = (int)num2.charAt(j) - (int) ('0');
                // Carry may occur
                int sum =  ret[i+j+1] + n1 * n2;
                / / low
                ret[i + j + 1] = sum % 10;
                / / high
                ret[i + j] += sum / 10;
            }
        }

        StringBuilder result = new StringBuilder();
        for (int i = 0; i < ret.length; i++) {
            / / to prevent
            if (i == 0 && ret[i] == 0) continue;
            result.append(ret[i]);
        }
        return result.toString();

    }
Copy the code

The test code

    public static void main(String[] args) {
        String ret = new Number43().multiply("123"."456");
        System.out.println(ret);
    }
Copy the code

The results of

Third, summary

Thank you for seeing the end, it is my great honor to help you ~♥