43. Multiply Strings P1的进位问题

这道题有个疑惑点，先贴看到的答案吧

public String multiply(String num1, String num2) {
        if(num1 == null || nums2 == null) return '0';
        int[] digits = new int[num1.length + num2.length];

        for(int i = num1.length - 1; i >= 0; i--) {
            for(int j = num2.length - 1; j >=0; j--) {
                int product = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                int p1 = i + j;
                int p2 = i + j + 1;
                int sum = digits[p2] + product;
                digits[p1] += sum/10;
                digits[p2] = sum%10;
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < digits.length; i++) {
            if(!(digits[i] == 0 && sb.length == 0)) {
                sb.append(digits[i]);
            }
        }
        return sb.length == 0 ? '0' : sb.toString();
    }

有个情况就是如果digits[p1] 之前刚好等于9， 然后万一sum/10等于个1， 9 + 1不就等于10了嘛， 这样digits[p1]就等于10了，这难道不需要进个位嘛？

digits的中间状态可以超过9，但是for循环是从低位往高位走的，所以上一次超过9的部分在下一次循环中会进位

你在内部for循环的最后加一些输出就可以看出来过程了，比如这样：

1. import java.util.Arrays;
   
2. 
   
3. public class Main {
   
4.   public String multiply(String num1, String num2) {
   
5.     if (num1 == null || num2 == null) {
   
6.       return "0";
   
7.     }
   
8.     int[] digits = new int[num1.length() + num2.length()];
   
9. 
   
10.     for (int i = num1.length() - 1; i >= 0; i--) {
    
11.       for (int j = num2.length() - 1; j >= 0; j--) {
    
12.         int product = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
    
13.         int p1 = i + j;
    
14.         int p2 = i + j + 1;
    
15.         int sum = digits[p2] + product;
    
16.         digits[p1] += sum / 10;
    
17.         digits[p2] = sum % 10;
    
18.         System.out.println("i = " + i + ", j = " + j +
    
19.                            ", p1 = " + p1 + ", p2 = " + p2 +
    
20.                            ", digits = " + Arrays.toString(digits));
    
21.         System.out.println("--");
    
22.       }
    
23.     }
    
24. 
    
25.     StringBuilder sb = new StringBuilder();
    
26.     for (int i = 0; i < digits.length; i++) {
    
27.       if (!(digits[i] == 0 && sb.length() == 0)) {
    
28.         sb.append(digits[i]);
    
29.       }
    
30.     }
    
31.     return sb.length() == 0 ? "0" : sb.toString();
    
32.   }
    
33.   
    
34.   public static void main(String[] args) {
    
35.     System.out.println("Result = " + new Main().multiply("999", "99"));
    
36.   }
    
37. }
    

复制代码

输出：

1. i = 2, j = 1, p1 = 3, p2 = 4, digits = [0, 0, 0, 8, 1]
   
2. --
   
3. i = 2, j = 0, p1 = 2, p2 = 3, digits = [0, 0, 8, 9, 1]
   
4. --
   
5. i = 1, j = 1, p1 = 2, p2 = 3, digits = [0, 0, 17, 0, 1]
   
6. --
   
7. i = 1, j = 0, p1 = 1, p2 = 2, digits = [0, 9, 8, 0, 1]
   
8. --
   
9. i = 0, j = 1, p1 = 1, p2 = 2, digits = [0, 17, 9, 0, 1]
   
10. --
    
11. i = 0, j = 0, p1 = 0, p2 = 1, digits = [9, 8, 9, 0, 1]
    
12. --
    
13. Result = 98901
    

复制代码

可以看出循环过程中digits中至多有一个slot可能>=10，但下一次那个slot就会进位

magicsets 发表于 2020-2-6 12:35
digits的中间状态可以超过9，但是for循环是从低位往高位走的，所以上一次超过9的部分在下一次循环中会进位
...

秒懂了，谢谢层主！