43. Multiply Strings

Given two non-negative integersnum1andnum2represented as strings, return the product ofnum1andnum2.

Note:

The length of bothnum1andnum2is < 110.
Bothnum1andnum2contains only digits0-9.
Bothnum1andnum2does not contain any leading zero.
Youmust not use any built-in BigInteger libraryorconvert the inputs to integerdirectly.

题目含义：计算两个非负整数的乘法，并用string返回

思路：

num1[i] * num2[j]` will be placed at indices `[i + j`, `i + j + 1]`

 1     public String multiply(String num1, String num2) {
 2         int m=num1.length(),n=num2.length();
 3         int[] result = new int[m+n];
 4         for (int i=m-1;i>=0;i--)
 5         {
 6             for (int j=n-1;j>=0;j--)
 7             {
 8                 int mul = (num1.charAt(i)-'0') * (num2.charAt(j)-'0');
 9                 int p1 = i+j;
10                 int p2 = i + j +1;
11                 int sum = mul + result[p2];
12                 result[p1] += sum/10;
13                 result[p2] = sum%10;
14             }
15         }
16         StringBuilder sb = new StringBuilder();
17         for (int p:result)
18         {
19             if(!(sb.length() == 0 && p == 0))
20             {
21                 sb.append(p);
22             }
23         }
24         return sb.length()==0?"0":sb.toString();        
25     }

方法二：

计算两个字符串表示的非负大整数的乘积，结果仍然用字符串表示。

我们都熟悉笔算的整数乘积，按照被乘数逐位与乘数求积，保存进位；当被乘数换位时，结果递增一个数量级，与先前结果求和。

如上例所示，当我们计算字符串“123”*“456”时，采取与笔算相同的思想，按照从个位—>高位的计算思想，现将字符串翻转，计算完成后，翻转结果，返回。

 1  string multiply(string num1, string num2) {
 2         //如果有其中一个乘数的字符串表示为空，则返回空字符串
 3         if (num1.empty() || num2.empty())
 4             return string();
 5 
 6         if (num1 == "0" || num2 == "0")
 7             return "0";
 8 
 9         //按照整数从低位到高位计算，翻转两个乘数字符串
10         reverse(num1.begin(), num1.end());
11         reverse(num2.begin(), num2.end());
12         //求两个乘数字符串的长度
13         int len1 = strlen(num1.c_str()), len2 = strlen(num2.c_str());
14 
15         //定义乘法结果字符串
16         string ret = "";
17         //保存进位
18         int carry = 0; 
19 
20         for (int i = 0; i < len1; i++)
21         {
22             //乘数的处理起始位
23             size_t pos = i;
24             for (int j = 0; j < len2; j++)
25             {
26                 int temp = (num1[i] - '0') * (num2[j] - '0') + carry;
27 
28                 //向当前位加入结果
29                 if (pos < ret.length())
30                 {
31                     temp = temp + (ret[pos] - '0');
32                     ret[pos] = temp % 10 + '0';
33                 }//if
34                 else{
35                     ret.append(1, temp % 10 + '0');
36                 }//else
37                 //计算下一个进位
38                 carry = temp / 10;
39                 //处理乘数的下一位
40                 pos++;
41             }//for
42             if (carry > 0)
43                 ret.append(1, carry + '0');
44             carry = 0;
45         }//for
46 
47         //翻转整个结果字符串
48         reverse(ret.begin(), ret.end());
49         return ret;
50 
51     }

方法三：

我们以289*785为例

首先我们把每一位相乘，得到一个没有进位的临时结果，如图中中间的一行红色数字就是临时结果，然后把临时结果从低位起依次进位。对于一个m位整数乘以n位整数的结果，最多只有m+n位。

    String multiply(String num1, String num2) {
        int n1 = num1.length(), n2 = num2.length();
        int[] tmpres =  new int[n1+n2];
        int k = n1 + n2 - 2;
        for(int i = 0; i < n1; i++)
            for(int j = 0; j < n2; j++)
                tmpres[k-i-j] += (num1.charAt(i)-'0')*(num2.charAt(j)-'0');
        int carryBit = 0;
        for(int i = 0; i < n1+n2; i++)//处理进位
        {
            tmpres[i] += carryBit;
            carryBit = tmpres[i] / 10;
            tmpres[i] %= 10;
        }
        int i = k+1;
        while(tmpres[i] == 0)i--;//去掉乘积的前导0
        if(i < 0)return "0"; //注意乘积为0的特殊情况
        StringBuilder res = new StringBuilder();
        for(; i >= 0; i--)
            res.insert(0,tmpres[i]);
        return res.toString();
    }

附录：

 1 String str1="111";  
 2 String str2="222";  
 3 BigDecimal num1 = new BigDecimal(str1);  
 4 BigDecimal num2 = new BigDecimal(str2);  
 5 然后通过BigDecimal的加减乘除方法，进行运算：  
 6 加法：  
 7 BigDecimal result = num1.add(num2);  
 8 减法：  
 9 result = num1.subtract(num2);  
10 除法：  
11 result = num1.divide(num2);  
12 乘法：  
13 result = num1.multiply(num2);

优质内容筛选与推荐>>
1、215. Kth Largest Element in an Array
2、【网络空间安全】SQL Injection_SQL 注入..
3、苹果内购支付的一些问题截屏
4、jQuery选择器
5、面试必备【含答案】Java面试题系列(二

0 │ 收藏 │ 举报

朋友将在看一看看到

分享想法到看一看