leetcode43.Multiply Strings

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
10
Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.

Note:

 1. The length of both num1 and num2 is < 110. 
 2. Both num1 and num2 contains only digits 0-9.
 3. Both num1 and num2 does not contain any
    leading zero. 
 4. You must not use any built-in BigInteger library or
    convert the inputs to integer directly.

将两个String形式的数字相乘的结果用String的形式返回。不准使用Int（java）以外的形式来记录数字。

思路一：队列

通过队列存储每一轮计算的结果。进行下一轮计算的时候，将上一轮的值deque出来加到当前的值上。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
public String multiply(String num1, String num2) {
    if(num1.equals("0") || num2.equals("0")){
        return "0";
    }
    
    StringBuilder result = new StringBuilder();
    //使用链表的方式实现队列
    LinkedList<Integer> queue = new LinkedList<Integer>();
    int count = 0;
    //将队尾的0添加到结果值中，并消去结尾的结果值
    if(num1.endsWith("0")){
        for(int i = num1.length() - 1 ; i>=0 ; i--){
            if(num1.charAt(i) == '0'){
                count++;
                result.append("0");
            }else{
                break;
            }
        }
        num1 = num1.substring(0, num1.length()-count);
    }
    
    count = 0;
    if(num2.endsWith("0")){
        for(int i = num2.length() - 1 ; i>=0 ; i--){
            if(num2.charAt(i) == '0'){
                count++;
                result.append("0");
            }else{
                break;
            }
        }
        num2 = num2.substring(0, num2.length()-count);
    }
    
    
    for(int i = num1.length()-1 ; i>=0 ; i--){    
        //乘数的值，如果乘数为0，则直接将上一轮的值添加到结果值
        int number1 = num1.charAt(i) - '0';
        if(number1 == 0){
            result.append(queue.removeFirst());
            //补进位0
            queue.add(0);
            continue;
        }
        int carry = 0;
        for(int j = num2.length()-1 ; j>=0 ; j--){
            //被乘数的值
            int number2 = num2.charAt(j) - '0';
            //第一轮无需考虑上一轮的进位
            int currentVal = number1 * number2 + carry + (i==num1.length()-1?0:queue.removeFirst());
            //如果是这一轮的末尾，直接将值添加到结果值中
            if(j== num2.length()-1){
                result.append(currentVal % 10);
            }else{
                queue.add(currentVal % 10);
            }
            carry = currentVal/10;
        }
        queue.add(carry);
        carry = 0;
    }
    while(!queue.isEmpty() && queue.getLast() == 0){
        queue.removeLast();
    }
    //将队列中的非零开头的进位添加到结果中
    while(!queue.isEmpty()){
        result.append(queue.removeFirst());
    }
    return result.reverse().toString();
    
}

思路二：int数组存储

根据乘法计算的规则，我们可以判断两个值计算后应该填到哪一个位置上。假设num1[i]*num2[j]，则将结果的十位和个位分别放在数组下标为i+j和i+j+1的位置上。记得计算的时候要加上上一轮的进位。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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();
}

思路三：将计算和进位分开

这里将每一位的计算结果都先存储到当前位置上，不管是否进位。存储的位置等同于上一思路。然后再通过一轮遍历将进位处理一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public String multiply(String num1, String num2) {
   if(num1.isEmpty() || num2.isEmpty()) return "0";
    int m = num1.length(), n = num2.length();
    int[] ret = new int[m+n];
    
    for(int i = m-1; i >= 0; i--) {
        int n1 = num1.charAt(i)-'0';
        for(int j = n-1; j>=0; j--) {
            int n2 = num2.charAt(j)-'0';
            int mul = n1*n2;
            ret[i+j+1] += mul;
        }
    }
    
    int carryOver = 0;
    for(int i = ret.length-1; i>=0; i--) {
        ret[i]+=carryOver;
        carryOver = ret[i]/10;
        ret[i]%=10;
    }
    
    StringBuilder sb = new StringBuilder();
    for(int x : ret) {
        if(x == 0 && sb.length()==0) continue;
        sb.append(x);
    }
    return sb.length()==0?"0":sb.toString();
    
}