LeetCode刷题记录-43

 1  public static String multiply(String num1, String num2) {
 2         //记录相乘的结果，最大位数不过二者长度之和
 3         int[] res = new int[num1.length() + num2.length()];
 4         //将每一步相乘的结果填入res对应的位置:index
 5         int index;
 6         //辅助index
 7         int cnt = 0;
 8         for (int i = num2.length() - 1; i >= 0; i--) {
 9             //乘数x
10             int x = num2.charAt(i) - ‘0‘;
11             index = res.length - 1 - cnt;
12             for (int j = num1.length() - 1; j >= 0; j--) {
13                 //被乘数y
14                 int y = num1.charAt(j) - ‘0‘;
15                 int tmpRes = x * y;
16                 res[index] = res[index] + tmpRes % 10;
17                 //检查res[index]的元素是否进位，并且处理进位
18                 check(res, index);
19                 index--;
20                 res[index] = res[index] + tmpRes / 10;
21                 check(res, index);
22             }
23             cnt++;
24         }
25         //将数组形式保存的结果以字符串形式拼接
26         StringBuilder sb = new StringBuilder();
27         //用来定位第一个非零元素下标
28         index = 0;
29         //是否找到第一个非零元素
30         boolean flag=false;
31         for (int i = 0; i < res.length; i++) {
32             if (res[i] != 0) {
33                 index = i;
34                 flag=true;
35                 break;
36             }
37         }
38         //没找到第一个非零元素，说明结果全部都是0，自然返回"0"
39         if (flag==false){
40             return "0";
41         }
42         for (int i = index; i < res.length; i++) {
43             sb.append(res[i]);
44         }
45         return sb.toString();
46     }
47 
48     private static void check(int[] res, int index) {
49         if (res[index] >= 10) {
50             res[index - 1] += res[index] / 10;
51             res[index] = res[index] % 10;
52         }
53     }