[Swift]LeetCode949.给定数字能组成的最大时间|LargestTimeforGivenDigits ...

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

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

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

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

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

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

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 == 4
0 <= 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 == 4
0 <= 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 }