Jamzen的技术博客
0%

LeetCode.字符串相乘

发表于 分类于 Valine：

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

  • 示例 1:
    输入: num1 = “2”, num2 = “3”
    输出: “6”
  • 示例 2:
    输入: num1 = “123”, num2 = “456”
    输出: “56088”

说明：

  1. num1 和 num2 的长度小于110。
  2. num1 和 num2 只包含数字 0-9。
  3. num1 和 num2 均不以零开头，除非是数字 0 本身。
  4. 不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

解法：

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
object Multiply {
     def main(args: Array[String]): Unit = {
          println(multiply("123", "0"))
          println(multiply("9723", "116"))
          println(multiply("9723", "1"))
     }

     def multiply(num1: String, num2: String): String = {
          if (num1.length == 1 && num1.charAt(0) == '0') return num1
          if (num2.length == 1 && num2.charAt(0) == '0') return num2

          var up = num1
          var down = num2

          if (up.length < down.length) {
               val tmp = up
               up = down
               down = tmp
          }

          val res = new Array[Array[Int]](down.length)

          for (i <- down.length - 1 to 0 by -1) {
               val arr = new Array[Int](up.length + down.length)
               for (j <- up.length - 1 to 0 by -1) {
                    val tmp = down.charAt(i).toString.toInt * up.charAt(j).toString.toInt
                    val divider = tmp / 10
                    val target = tmp % 10
                    arr(j + 1 + i) = arr(j + 1 + i) + target
                    arr(j + i) = arr(j + i) + divider
               }
               res(i) = arr
          }

          val finalArr = new Array[Int](up.length + down.length + 1)
          var divider = 0
          for (i <- up.length + down.length - 1 to 0 by -1) {
               var t = divider
               for (j <- 0 until res.length) {
                    t += res(j)(i)
               }
               divider = t / 10
               finalArr(i + 1) = t % 10
          }

          var result = ""
          var find = false
          finalArr.foreach(a => {
               if (find) {
                    result = result + a
               } else {
                    if (a != 0) {
                         find = true
                         result = result + a
                    }
               }
          })
          result
     }
}