leetcode: Multiply Strings

问题描述：

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note:

• The numbers can be arbitrarily large and are non-negative.
• Converting the input string to integer is NOT allowed.
• You should NOT use internal library such as BigInteger

原问题链接：https://leetcode.com/problems/multiply-strings/

 

问题分析

　　这个问题的限制在于不能直接将给定的两个字符串转换成整数，另外数字也可能足够大，所以用直接的运算可能会导致溢出，也限制了使用BigInteger。所以基本上就限定了要用数组的方式来模拟乘法运算的过程。我们针对这几种情况来具体的分析一下。

 

方法一

　　在之前的文章里有讨论过对于比较大的整数的乘法模拟运算。在这种方法里，我们定义两个整型数组，分别表示两个字符串对应的数字。数组里每个元素对应一个字符所表示的数字。因为通常的字符串表示的数字比如"12345"，它的最高位在最前面。我们在转换的时候需要将它们倒过来保存以方便后续的运算。

　　在得到两个整型数组之后，我们需要进行模拟的乘法运算。这里是按照人工手工运算的方式来计算。我们知道，对于两个长度分别为m, n的数字来说，它们的乘积数字最大长度为m + n。所以需要声明一个m + n长度的数组来保存结果。

　　在乘法的过程中，我们从一个数组中按照从最低位到最高位，每次取该位的数字和另外一个数组里的每个元素逐位相乘，得到的结果再依次移位相加。比如有数字123 x 456的时候，我们首先去456中间最低位6和123相乘，得到数值732，我们将这个值放到一个中间值数组里。然后这个数组和最后结果的result数组从最后一位开始依次相加。然后下一位的计算再求5乘以123。得到的数字是615，不过这个时候这个数字需要向前移动一位，再和result数组里面每一位对应相加。这样，按照这种方式，我们得到一个最终的数组。

　　这里还有一个细节就是我们分配的数组是按照最大的情况考虑的，如果实际上得到的数字没有那么大呢？那么就可能出现最高位的数字是０的情况。我们还需要把这种情况给跳过去。所以根据上述的讨论，可以得到如下的代码：

 

public class Solution {
    public String multiply(String num1, String num2) {
        if(num1.equals("0") || num2.equals("0"))
            return "0";
        int[] nu1 = toArray(num1);
        int[] nu2 = toArray(num2);
        int[] result = multiply(nu1, nu2);
        StringBuilder builder = new StringBuilder();
        if(result[result.length - 1] == 0) {
            for(int i = result.length - 2; i >= 0; i--)
                builder.append(result[i]);   
        } else {
            for(int i = result.length - 1; i >= 0; i--)
                builder.append(result[i]);
        }
        return builder.toString();
    }
    
    private int[] multiply(int[] a, int[] b) {
        int la = a.length, lb = b.length;
        int[] result = new int[la + lb];
        for(int i = 0; i < la; i++) {
            int[] medium = new int[lb + 1];
            int carry = 0;
            int j = 0;
            for(j = 0; j < lb; j++) {
                medium[j] = (a[i] * b[j] + carry) % 10;
                carry = (a[i] * b[j] + carry) / 10;
            }
            medium[j] = carry;
            
            carry = 0;
            for(int k = 0; k < lb + 1; k++) {
                int sum = medium[k] + result[i + k] + carry;
                result[i + k] = sum % 10;
                carry = sum / 10;
            }
        }
        
        return result;
    }
    
    
    private int[] toArray(String s) {
        int len = s.length();
        int[] list = new int[len];
        for(int i = 0; i < len; i++) {
            list[len - i - 1] = Character.digit(s.charAt(i), 10);
        }
        
        return list;
    }
}

 

改进方法

　　上述的方法模拟的计算确实能得到正确的结果，不过总体来说显得有点复杂了。一方面它需要不断分配数组来作为中间结果，而且还需要将这些结果移位相加。这样还比较容易出错。那么有没有更好的方法呢？

　　在参考了一个讨论的分析之后，我们其实有一个办法可以执行的效率更高。我们都知道，对于整数乘法来说，它们都是每次取一个位的值和另外一个数的所有位相乘。然后每次对应一个不同的位是要相应进位。然后再将它们都加起来。

　　假设有数组num1[], num2[]，它们对应的索引分别是i, j。那么它们的乘积的运算关系如下图所示：

 

　　通过上述的推导我们可以发现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] = sum / 10，pos[pos2] = sum % 10。

    按照上述的讨论可以得到如下的代码：

 

public class Solution {
    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();
    }
}

 　　和前面的方法比起来，这里根据它们运算的过程推导出num1[i] * num2[j]对应到i + j, i + j + 1两个位置的值。然后每次都将乘积结果和对应的值相加再来确定最终的值。这种方式也节省了中间值数组的申请。所以显得简洁高效很多。

 

参考材料

https://leetcode.com/discuss/71593/easiest-java-solution-with-graph-explanation

http://shmilyaw-hotmail-com.iteye.com/blog/1769034