[Swift]LeetCode43.字符串相乘|MultiplyStrings

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/9907355.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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

Example 1:

Input: num1 = "2", num2 = "3"
Output: "6"

Example 2:

Input: num1 = "123", num2 = "456"
Output: "56088"

Note:

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

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

示例 1:

输入: num1 = "2", num2 = "3"
输出: "6"

示例 2:

输入: num1 = "123", num2 = "456"
输出: "56088"

说明：

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

56ms

 1 class Solution {
 2   func integerArray(text: String) -> [Int] {
 3     let characterArray = Array(text)
 4     var integerArray = [Int]()
 5     for character in characterArray {
 6       let unitScalar = character.unicodeScalars.first!.value - Unicode.Scalar("0")!.value
 7       integerArray.append(Int(unitScalar))
 8     }
 9 
10     return integerArray
11   }
12 
13 
14   func multiply(_ num1: String, _ num2: String) -> String {
15     if num1 == "0" || num2 == "0" {
16         return "0"
17     }
18     let num1Array = integerArray(text: num1)
19     let num2Array = integerArray(text: num2)
20     let maxCount = num1Array.count + num2Array.count - 1
21     var productArray = [Int](repeating: 0, count: maxCount)
22     var i = 0
23     for number1 in num1Array {
24       var j = i
25       for number2 in num2Array {
26         productArray[j] += number1 * number2
27         j += 1
28       }
29       i += 1
30     }
31 
32     var characterArray = [Character]()
33     let lastIndex = productArray.count - 1
34     var carry = 0
35     for k in 0...lastIndex {
36       let l = lastIndex - k
37       var value = productArray[l] + carry
38       if value >= 10 {
39         carry = value / 10
40         value = value % 10
41       } else {
42         carry = 0
43       }
44 
45       let character: Character = Character(String(value))
46       characterArray.insert(character, at: 0)
47     }
48     if carry > 0 {
49       let character: Character = Character(String(carry))
50       characterArray.insert(character, at: 0)
51     }
52 
53     return String(characterArray)
54   }
55 }

72ms

 1 class Solution {
 2     func multiply(_ num1: String, _ num2: String) -> String {
 3         if num1 == "0" || num2 == "0" {
 4             return "0"
 5         }
 6         
 7         var result = String()
 8         
 9         var num1Arr = Array(num1), num2Arr = Array(num2)
10         let n1 = num1.count, n2 = num2.count
11         var k = n1 + n2 - 2, carry = 0
12         var v = [Int](repeating: 0, count: n1 + n2)
13         let zeroValue = Int("0".unicodeScalars.first!.value)
14         for i in 0..<n1 {
15             for j in 0..<n2 {
16                 let num1Value = Int(num1Arr[i].unicodeScalars.first!.value)
17                 let num2Value = Int(num2Arr[j].unicodeScalars.first!.value)
18                 v[k - i - j] += (num1Value - zeroValue) * (num2Value - zeroValue)
19             }
20         }
21         
22         for i in 0..<n1 + n2 {
23             v[i] += carry
24             carry = v[i] / 10
25             v[i] %= 10
26         }
27         var i = n1 + n2 - 1
28         while v[i] == 0 {
29             i -= 1
30         }
31         if i < 0 {
32             return "0"
33         }
34         while i >= 0 {
35             let c = Character(UnicodeScalar(zeroValue + v[i])!)
36             result.append(String(c))
37             i -= 1
38         }
39         
40         return result
41     }
42 }

88ms

 1 class Solution {
 2     func multiply(_ num1: String, _ num2: String) -> String {
 3         let left = num1.map({ Int(String($0))! })
 4         let right = num2.map({ Int(String($0))! })
 5 
 6         let m = left.count
 7         let n = right.count
 8         var result = [Int](repeating: 0, count: m + n)
 9 
10         for i in (0..<m).reversed() {
11             for j in (0..<n).reversed() {
12                 let mul = left[i] * right[j]
13                 let pos1 = i + j
14                 let pos2 = i + j + 1
15                 let sum = mul + result[pos2]
16 
17                 result[pos1] += sum / 10
18                 result[pos2] = sum % 10
19             }
20         }
21 
22         var answer = ""
23         for i in result {
24             if answer.count == 0 && i == 0 {
25                 continue
26             }
27 
28             answer += "\(i)"
29         }
30         
31         if answer.count == 0 {
32             return "0"
33         }
34 
35         return answer
36     }
37 }

100ms

 1 class Solution {
 2     func multiply(_ num1: String, _ num2: String) -> String {
 3         let num1Array = Array(num1).map {Int(String($0))}
 4         let num2Array = Array(num2).map {Int(String($0))}
 5         var ansArray = Array(repeatElement(0,count:num1Array.count+num2Array.count))
 6         var step = 0
 7         for index1 in stride(from:num1Array.count-1, through:0, by:-1) {
 8             for index2 in stride(from:num2Array.count-1, through:0, by:-1) {
 9                 let value = num1Array[index1]! * num2Array[index2]!
10                 ansArray[step+num2Array.count-1-index2] = ansArray[step+num2Array.count-1-index2] + value
11                 var carrier = ansArray[step+num2Array.count-1-index2] / 10
12                 ansArray[step+num2Array.count-1-index2] = ansArray[step+num2Array.count-1-index2] - (carrier*10)
13                 ansArray[step+num2Array.count-1-index2+1] = ansArray[step+num2Array.count-1-index2+1] + carrier
14             }
15             step = step + 1
16         }
17         
18         ansArray.reverse()
19         var lastNonZeroIndex = 0
20         for value in ansArray {
21             if value==0 {
22                 lastNonZeroIndex = lastNonZeroIndex + 1
23             } else {
24                 break
25             }
26         }
27 
28         for count in stride(from:lastNonZeroIndex, to:0, by:-1) {
29             ansArray.removeFirst()
30         }
31 
32         if ansArray.count == 0 {
33             return "0"
34         }
35         return (ansArray.map {String($0)}).joined(separator: "")
36     }
37 }

168ms

 1 class Solution {
 2     
 3     private let charToInt : [Character : Int] = 
 4     [
 5         "0" : 0, "1" : 1, "2" : 2, "3" : 3, "4" : 4,
 6         "5" : 5, "6" : 6, "7" : 7, "8" : 8, "9" : 9
 7     ]
 8     
 9     func multiply(_ num1: String, _ num2: String) -> String {
10         let chars1 = Array(num1.characters)
11         let chars2 = Array(num2.characters)
12         
13         var num1Count = num1.count - 1
14         var num2Count = num2.count - 1
15         var multiply = 0
16         let size = num2.count + num1.count
17         var result = [Int](repeating: 0, count: size)
18         
19         for i in stride(from: num1Count, to: -1, by: -1) {
20             for j in stride(from: num2Count, to: -1, by: -1) {
21                 var n1 = i >= 0 ? charToInt[chars1[i]] : 0
22                 var n2 = j >= 0 ? charToInt[chars2[j]] : 0
23 
24                 let pos1 = i+j+1
25                 let pos2 = i+j
26                 multiply = n1! * n2! + result[pos1]
27                 
28                 result[pos1] =  multiply%10
29                 result[pos2] = result[pos2] + (multiply/10)
30             }
31         }
32 
33         var resultString = ""
34         var removeZero = false
35         for num in result {
36             if num != 0 {
37                 removeZero = true
38             }
39             if removeZero {
40                 resultString = resultString + String(num)
41             }
42         }
43         if resultString == "" {
44             return "0"
45         }
46         
47         return resultString
48 
49     }
50 }

228ms

 1 class Solution {
 2     func multiply(_ num1: String, _ num2: String) -> String {
 3         let m = num1.count
 4         let n = num2.count
 5         let zero = Character("0").ascii
 6         var pos = [Int](repeating: 0, count: m + n)
 7         var res = [String]()
 8 
 9         for i in (0..<m).reversed() {
10             for j in (0..<n).reversed() {
11                 let mul = (num1[i].ascii - zero) * (num2[j].ascii - zero)
12                 let p1 = i + j
13                 let p2 = i + j + 1
14                 let sum = mul + pos[p2]
15                 pos[p1] += sum / 10
16                 pos[p2] = sum % 10
17             }
18         }
19 
20         for p in pos {
21             if !(res.count == 0 && p == 0) {
22                 res.append(String(p))
23             }
24         }
25 
26         return res.count == 0 ? "0" : res.joined()
27     }
28 }
29 
30 extension Character {
31     var ascii: Int {
32         get {
33             let s = String(self).unicodeScalars
34             return Int(s[s.startIndex].value)
35         }
36     }
37     
38     func isDigit() -> Bool {
39         return self >= "0" && self <= "9"
40     }
41 }
42 
43 extension String {
44     subscript (i: Int) -> Character {
45         return self[index(startIndex, offsetBy: i)]
46     }
47 }