LeetCode算法入门- Multiply Strings -day18

题目介绍

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

Example 1:

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

Example 2:

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

Note:

The length of both num1 and num2 is < 110.
Both num1 and num2 contain only digits 0-9.
Both num1 and num2 do not contain any leading zero, except the number 0 itself.
You must not use any built-in BigInteger library or convert the inputs to integer directly.

题目分析
解题思想在于这个图：

通过上述的推导我们可以发现num1[i] * num2[j]的结果将被保存到 [i + j, i + j + 1] 这两个索引的位置。其中它们的个位数保存在（i + j + 1）的位置，十位数保存在（i + j）的位置。所以我们可以定义一个数组 pos[m + n] ，它的长度为两个数组的长度。只是它们的计算不需要把它们给反转过来。每次我们有num1[i] * num2[j]的时候先取得 pos1 = i + j, pos2 = i + j + 1。这样得到的值是
sum = num1[i] * num2[j] + pos[pos2]。按照前面的计算规则，。pos[pos1] = pos[pos1] + sum/10; pos[pos2] = sum % 10;

Java实现

class Solution {
    public String multiply(String num1, String num2) {
        int m = num1.length();
        int n = num2.length();
        //定义这个数组来存储最后结果的每一位
        int[] pos = new int[m+n];
        
        //从最右边开始，所以是m-1
        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] = pos[p1] + sum/10;
                pos[p2] = sum % 10;
                
            }
        }
        StringBuilder sb = new StringBuilder();
        for(int p : pos){
            //排除高位数为0的情况
            if(sb.length() == 0 && p == 0){
                continue;
            }
            else{
                sb.append(p);
            }
        }
        //排除长度为0的情况
        if(sb.length() == 0)
            return "0";
        else{
            return sb.toString();
        }
    }
}

LeetCode算法入门- Multiply Strings -day18

相关推荐