43 Multiply String

发表于 | 分类于 | |

43. Multiply Strings

题目描述

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.

Note:

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

题目大意

大数乘法。

解题思路

模拟手算的过程，以数组 pos 储存结果，第一个字符串的第 i 位 和 第二个字符串的第 j 位相乘，一定是结果的的第 i + j 位，那么对当前结果进行取余就是 进位，即 i + j + 1 位。
最后剔除掉数组 pos 内所有前置位的 0 。

代码

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
class Solution {
    func multiply(_ num1: String, _ num2: String) -> String {
        let s1 = Array(num1.unicodeScalars.reversed())
        let s2 = Array(num2.unicodeScalars.reversed())
        var pos = Array(repeating: 0, count: num1.count + num2.count)
        for (i, char1) in s1.enumerated() {
            for (j, char2) in s2.enumerated() {
                let mult = Int((char1.value - 48) * (char2.value - 48))
                let p1 = num1.count + num2.count - i - j - 2, p2 = num1.count + num2.count - i - j - 2 + 1
                let sum = mult  + pos[p2]
                pos[p1] += sum / 10
                pos[p2] = sum % 10
            }
        }
        var index = pos.count - 1
        for (i, num) in pos.enumerated() {
            if num != 0 {
                index = i
                break
            }
        }
        let ans = pos[index..<pos.count].reduce("", { (res, num) -> String in
                    return res + "\(num)"
                })
        return ans.count == 0 ? "0" : ans
    }
}
0%