[Swift]LeetCode949. 给定数字能组成的最大时间 | Largest Time for Given Digits
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
Given an array of 4 digits, return the largest 24 hour time that can be made.
The smallest 24 hour time is 00:00, and the largest is 23:59. Starting from 00:00, a time is larger if more time has elapsed since midnight.
Return the answer as a string of length 5. If no valid time can be made, return an empty string.
Example 1:
Input: [1,2,3,4] Output:
Example 2:
Input: [5,5,5,5] Output:
Note:
A.length == 40 <= A[i] <= 9
给定一个由 4 位数字组成的数组，返回可以设置的符合 24 小时制的最大时间。
最小的 24 小时制时间是 00:00，而最大的是 23:59。从 00:00 （午夜）开始算起，过得越久，时间越大。
以长度为 5 的字符串返回答案。如果不能确定有效时间，则返回空字符串。
示例 1：
输入：[1,2,3,4] 输出："23:41"
示例 2：
输入：[5,5,5,5] 输出：""
提示：
A.length == 40 <= A[i] <= 9
12ms
1 class Solution {
2 func largestTimeFromDigits(_ A: [Int]) -> String {
3 let a = [
4 [0, 1, 2, 3],
5 [0, 1, 3, 2],
6 [1, 0, 2, 3],
7 [1, 0, 3, 2],
8 [0, 2, 1, 3],
9 [0, 2, 3, 1],
10 [2, 0, 1, 3],
11 [2, 0, 3, 1],
12 [0, 3, 1, 2],
13 [0, 3, 2, 1],
14 [3, 0, 1, 2],
15 [3, 0, 2, 1],
16 [1, 2, 0, 3],
17 [1, 2, 3, 0],
18 [2, 1, 0, 3],
19 [2, 1, 3, 0],
20 [1, 3, 0, 2],
21 [1, 3, 2, 0],
22 [3, 1, 0, 2],
23 [3, 1, 2, 0],
24 [2, 3, 0, 1],
25 [2, 3, 1, 0],
26 [3, 2, 0, 1],
27 [3, 2, 1, 0]
28 ].compactMap { r -> String? in
29 let a = A[r[0]]
30 let b = A[r[1]]
31 let c = A[r[2]]
32 let d = A[r[3]]
33
34 let f1 = a * 10 + b
35 let f2 = c * 10 + d
36
37 if f1 < 24 && f2 < 60 {
38 return "\(a)\(b):\(c)\(d)"
39 } else {
40 return nil
41 }
42 }
43
44
45 return a.max() ?? ""
46 }
47 }16ms
1 class Solution {
2 func largestTimeFromDigits(_ A: [Int]) -> String {
3 var ans = -1
4
5 // Choose different indices i, j, k, l as a permutation of 0, 1, 2, 3
6 for i in 0..<4 {
7 for j in 0..<4 {
8 if j != i {
9 for k in 0..<4 {
10 if k != i && k != j {
11 let l = 6 - i - j - k
12 let hour = 10 * A[i] + A[j]
13 let min = 10 * A[k] + A[l]
14 if hour < 24 && min < 60 {
15 ans = max(ans, hour * 60 + min)
16 }
17 }
18 }
19 }
20 }
21 }
22
23 return ans >= 0 ? String.init(format: "%02d:%02d", ans / 60, ans % 60) : ""
24 }
25 }24ms
1 class Solution {
2 var result = -1
3 func largestTimeFromDigits(_ A: [Int]) -> String {
4 var isVisited = [Bool](repeating: false, count: 4)
5 var value = 0
6 dfs(A, &value, &isVisited)
7 return result == -1 ? "" : convertResultToString(result)
8 }
9
10 func dfs(_ A: [Int], _ value: inout Int, _ isVisited: inout [Bool]) {
11
12 if (isVisited.filter { $0 == true }.count == 4) {
13 if isValidTime(value) {
14 result = max(result, value)
15 }
16 return
17 }
18
19
20 for i in 0..<A.count {
21 guard !isVisited[i] else {
22 continue
23 }
24
25 value = value * 10 + A[i]
26 isVisited[i] = true
27 dfs(A, &value, &isVisited)
28 isVisited[i] = false
29 value = value / 10
30 }
31 }
32 func isValidTime(_ input: Int) -> Bool {
33 var input = input
34 guard input <= 2359 else {
35 return false
36 }
37
38 guard input % 100 <= 59 else {
39 return false
40 }
41 return true
42 }
43
44 func convertResultToString(_ input: Int) -> String {
45 var input = input
46 var convertedString = ""
47 for i in 0...3 {
48 if i == 2 {
49 convertedString = ":" + convertedString
50 }
51 convertedString = String(input % 10) + convertedString
52 input = input / 10
53 }
54 return convertedString
55 }
56 }28ms
1 class Solution {
2 func largestTimeFromDigits(_ A: [Int]) -> String {
3
4 // 1) Permutate digits and get largest valid time
5 var answer = permuteDigitsToStrings(A, "", "-1")
6
7 // 2) Convert to time format
8 if answer == "-1" {
9 return ""
10 }
11
12 answer.insert(":", at: answer.index(answer.startIndex, offsetBy: 2))
13 return answer
14 }
15
16 func permuteDigitsToStrings(_ A: [Int], _ currentDigits: String, _ max: String) -> String {
17
18 var currMax = max
19 guard A.count > 0 else {
20 currMax = max
21 if validateTime(currentDigits) && Int(max)! < Int(currentDigits)! {
22 currMax = currentDigits
23 }
24 return currMax
25 }
26
27 // Permutate
28 for num in A {
29 var remaining = A
30 // Choose
31 let digit = remaining.remove(at: remaining.firstIndex(of: num)!)
32 let curDigits = currentDigits + String(digit)
33
34 // Explore
35 currMax = permuteDigitsToStrings(remaining, curDigits, currMax)
36
37 }
38
39 return currMax
40 }
41
42 func validateTime(_ digits: String) -> Bool {
43 // Validate hours and minutes
44 let minuteStartIndex = digits.index(digits.startIndex, offsetBy: 2)
45 let minuteEndIndex = digits.index(digits.startIndex, offsetBy: 3)
46 guard
47 let hour = Int(String(digits[digits.startIndex...digits.index(digits.startIndex, offsetBy: 1)])),
48 let min = Int(String(digits[minuteStartIndex...minuteEndIndex]))
49 else { return false }
50
51 if hour >= 24 || min >= 60 {
52 return false
53 }
54
55 return true
56 }
57 }48ms
1 class Solution {
2 func permute<C: Collection>(items: C) -> [[C.Iterator.Element]] {
3 var scratch = Array(items) // This is a scratch space for Heap's algorithm
4 var result: [[C.Iterator.Element]] = [] // This will accumulate our result
5
6 // Heap's algorithm
7 func heap(_ n: Int) {
8 if n == 1 {
9 result.append(scratch)
10 return
11 }
12
13 for i in 0..<n-1 {
14 heap(n-1)
15 let j = (n%2 == 1) ? 0 : i
16 scratch.swapAt(j, n-1)
17 }
18 heap(n-1)
19 }
20
21 // Let's get started
22 heap(scratch.count)
23
24 // And return the result we built up
25 return result
26 }
27
28 func v(c: Character, i : Int) -> Bool {
29 return Int(String(c))! <= i
30 }
31
32 func largestTimeFromDigits(_ A: [Int]) -> String {
33
34 var options: [[Int]] = []
35
36 options = permute(items: A)
37
38
39 let nums = options.compactMap({String("\($0[0])\($0[1])\($0[2])\($0[3])")})
40
41 let num = nums.compactMap({Int($0)})
42
43
44 var valid: [String] = []
45
46 var max = -1
47 for n in nums {
48
49 let itms = Array(n)
50
51 let s = String("\(itms[0])\(itms[1])")
52 let it = Int(s)!
53
54 if it >= 24 {
55 continue
56 } else {
57
58 let oth = Int(String("\(itms[2])\(itms[3])"))!
59
60 if oth >= 60 {
61 continue
62 } else {
63 valid.append(n)
64 }
65
66 }
67
68 }
69
70 if valid.count == 0 {
71 return ""
72 }
73
74 let ss = valid.sorted(by: { (s1, s2) -> Bool in
75 s1 > s2
76 }).first!
77
78 let ssa = Array(ss)
79
80 return String("\(ssa[0])\(ssa[1]):\(ssa[2])\(ssa[3])")
81
82
83
84 return ""
85
86 }
87
88 }96ms
1 class Solution {
2 func largestTimeFromDigits(_ A: [Int]) -> String {
3 var f:[Int] = [Int](repeating:0,count:10)
4 for x in A
5 {
6 f[x] += 1
7 }
8 for h in (0...23).reversed()
9 {
10 for m in (0...59).reversed()
11 {
12 var g:[Int] = [Int](repeating:0,count:10)
13 var i:Int = h
14 for j in 0..<2
15 {
16 g[i%10] += 1
17 i /= 10
18 }
19 i = m
20 for j in 0..<2
21 {
22 g[i%10] += 1
23 i /= 10
24 }
25 if f == g
26 {
27 return String(format:"%02d:%02d", h, m)
28 }
29 }
30 }
31 return String()
32 }
33 }180ms
1 class Solution {
2 func largestTimeFromDigits(_ A: [Int]) -> String {
3 var sortA = A.sorted()
4
5 var time: [Int] = [2, 3, 5, 9]
6
7
8 while true {
9 if sortA == time.sorted() {
10 return "\(time[0])\(time[1]):\(time[2])\(time[3])"
11 }
12
13 if time[3] > 0 {
14 time[3] -= 1
15 } else if time[2] > 0 {
16 time[2] -= 1
17 time[3] = 9
18 } else if time[1] > 0 {
19 time[1] -= 1
20 time[3] = 9
21 time[2] = 5
22 } else if time[0] > 0 {
23 time[0] -= 1
24 time[1] = 9
25 time[3] = 9
26 time[2] = 5
27 } else {
28 return ""
29 }
30 }
31
32 return ""
33 }
34 }