[Swift]LeetCode753. 破解保险箱 | Cracking the Safe

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

There is a box protected by a password. The password is n digits, where each letter can be one of the first k digits 0, 1, ..., k-1.

You can keep inputting the password, the password will automatically be matched against the last n digits entered.

For example, assuming the password is "345", I can open it when I type "012345", but I enter a total of 6 digits.

Please return any string of minimum length that is guaranteed to open the box after the entire string is inputted.

Example 1:

Input: n = 1, k = 2 Output: "01" Note: "10" will be accepted too. 

Example 2:

Input: n = 2, k = 2 Output: "00110" Note: "01100", "10011", "11001" will be accepted too. 

Note:

n will be in the range [1, 4].k will be in the range [1, 10].k^n will be at most 4096.

---

有一个需要密码才能打开的保险箱。密码是 n 位数, 密码的每一位是 k 位序列 0, 1, ..., k-1 中的一个 。

你可以随意输入密码，保险箱会自动记住最后 n 位输入，如果匹配，则能够打开保险箱。

举个例子，假设密码是 "345"，你可以输入 "012345" 来打开它，只是你输入了 6 个字符.

请返回一个能打开保险箱的最短字符串。 

示例1:

输入: n = 1, k = 2 输出: "01" 说明: "10"也可以打开保险箱。 

示例2:

输入: n = 2, k = 2 输出: "00110" 说明: "01100", "10011", "11001" 也能打开保险箱。 

提示：

n 的范围是 [1, 4]。k 的范围是 [1, 10]。k^n 最大可能为 4096。

---

12ms

1 func deBruijnSequence<Alphabets: RandomAccessCollection>(of alphabets:Alphabets, length: Int) -> [Alphabets.Element] { 2 typealias Alphabet = Alphabets.Element 3 4 let alphabetCount = alphabets.count 5 let cycleCount = repeatElement(alphabetCount, count: length - 1).reduce(1, *) 6 let debruijnLength = cycleCount * alphabetCount 7 8 var used = Array(repeating: false, count: debruijnLength) 9 var result: [Alphabet] = [] 10 result.reserveCapacity(debruijnLength) 11 12 for index in 0..<debruijnLength { 13 var current = index 14 while !used[current] { 15 used[current] = true 16 17 let elementIndex = current / cycleCount 18 current = (current % cycleCount) * alphabetCount + elementIndex 19 result.append(alphabets[alphabets.index(alphabets.startIndex, offsetBy: elementIndex)]) 20 } 21 assert(current == index) 22 } 23 24 assert(result.count == debruijnLength) 25 return result 26 } 27 28 class Solution { 29 func crackSafe(_ n: Int, _ k: Int) -> String { 30 let result = deBruijnSequence(of: (0..<k).map(String.init), length: n) 31 return (result + repeatElement("0", count: n - 1)).joined() 32 } 33 }

---

36ms

1 class Solution { 2 func crackSafe(_ n: Int, _ k: Int) -> String { 3 let total = Int(pow(Double(k), Double(n))) 4 var current = [Int](repeating: 0, count: n) 5 var used = Set<String>() 6 used.insert(current.reduce("") { $0 + String($1) }) 7 dfs(n, k, total, &used, &current) 8 return current.reduce("") { $0 + String($1) } 9 } 10 11 private func dfs(_ n: Int, _ k: Int, _ total: Int, _ used: inout Set<String>, _ current: inout [Int]) -> Bool { 12 guard used.count < total else { 13 return true 14 } 15 var prefix = Array(current[(current.count - n + 1)...]).reduce("") { $0 + String($1) } 16 for num in 0..<k { 17 let currentSegment = prefix + String(num) 18 guard !used.contains(currentSegment) else { 19 continue 20 } 21 used.insert(currentSegment) 22 current.append(num) 23 if dfs(n, k, total, &used, &current) { 24 return true 25 } 26 current.removeLast() 27 used.remove(currentSegment) 28 } 29 return false 30 } 31 }

---

152ms

1 class Solution { 2 func dfs(_ n: Int, _ k: Int, _ len: Int, _ data: inout Set<String>, _ res:inout String) -> Bool { 3 if (res.count == len) { return true; } 4 let suf = res.suffix(n-1) 5 for c in 0..<k { 6 if !data.contains(suf + "\(c)") { 7 data.insert(suf + "\(c)") 8 res += "\(c)" 9 if (dfs(n, k, len, &data, &res)) { 10 return true 11 } 12 data.remove(suf + "\(c)") 13 res.removeLast() 14 } 15 } 16 return false 17 } 18 func crackSafe(_ n: Int, _ k: Int) -> String { 19 let len = Int(pow(Double(k), Double(n))) + n - 1 20 var res = String((0..<n).map{_ in Character("0")}) 21 var data = Set([res]) 22 dfs(n, k, len, &data, &res) 23 return res 24 } 25 }

---

Runtime: 320 ms Memory Usage: 22.2 MB 1 class Solution { 2 func crackSafe(_ n: Int, _ k: Int) -> String { 3 var res:String = "0".repeatString(n - 1) 4 var visited:Set<String> = [res] 5 var num:Int = Int(pow(Double(k), Double(n))) 6 helper(n, k,num, &visited, &res) 7 return res 8 } 9 10 func helper(_ n:Int,_ k:Int,_ total:Int,_ visited:inout Set<String>,_ res:inout String) 11 { 12 if visited.count == total 13 { 14 return 15 } 16 var pre:String = res.subString(res.count - n + 1, n - 1) 17 for i in stride(from:k - 1,through:0,by:-1) 18 { 19 var cur:String = pre + String(i) 20 if visited.contains(cur) {continue} 21 visited.insert(cur) 22 res += String(i) 23 helper(n, k, total, &visited, &res) 24 } 25 } 26 } 27 28 extension String { 29 //获取重复指定次数的字符串 30 func repeatString(_ times: Int ) -> String 31 { 32 var result = String() 33 for i in 0...times { 34 result += self 35 } 36 return result 37 } 38 39 // 截取字符串：指定索引和字符数 40 // - begin: 开始截取处索引 41 // - count: 截取的字符数量 42 func subString(_ begin:Int,_ count:Int) -> String { 43 let start = self.index(self.startIndex, offsetBy: max(0, begin)) 44 let end = self.index(self.startIndex, offsetBy: min(self.count, begin + count)) 45 return String(self[start..<end]) 46 } 47 }

 

 

转载于:https://www.cnblogs.com/strengthen/p/10529735.html

相关资源：数据结构—成绩单生成器