【MEDIUM】Next Closest Time

发布于: 2019-01-07 22:41
阅读: 9
评论: 0
喜欢: 0

问题

Given a time represented in the format "HH:MM", form the next closest time by reusing the current digits. There is no limit on how many times a digit can be reused.

You may assume the given input string is always valid. For example, "01:34", "12:09" are all valid. "1:34", "12:9" are all invalid.

Example 1:

Input: "19:34"
Output: "19:39"
Explanation: The next closest time choosing from digits 1, 9, 3, 4, is 19:39, which occurs 5 minutes later.  It is not 19:33, because this occurs 23 hours and 59 minutes later.
Example 2:

Input: "23:59"
Output: "22:22"
Explanation: The next closest time choosing from digits 2, 3, 5, 9, is 22:22. It may be assumed that the returned time is next day's time since it is smaller than the input time numerically.

分析过程

  • 输入:一个时间值
  • 输出:不产生新的数字来组成下一个时间点
  • 思路:
    • 一天有 1440 分钟,因此可以暴力扫描。把输入字符串拆分以后放入集合,根据输入的时间把整天的时间切成四段分别扫描。假设输入的是 12:34,四段分别扫描的区间为:
    • 12:35 ~ 12:59
    • 13:00 ~ 23:59
    • 00:00 ~ 11:59
    • 12:00 ~ 12:35
    • 按这样的顺序扫描,扫描时检查是不是所有的数字都在集合中,如果是就直接输出。

解决方法

// 输入的字符串提取小时和分钟
func strToTime(timeStr: String) -> (Int, Int) {
    // 这里不检查合法性,假设输入的都是合法的
    let strs = timeStr.components(separatedBy: ":")
    return (Int(strs[0])!, Int(strs[1])!)
}

// 检查整数的所有数字是不是包含在集合以内
func check(value: Int, inSet set: Set<Character>) -> Bool {
    for c in String.init(format: "%02d", value) {
        if !set.contains(c) {
            return false
        }
    }
    return true
}

func nextTime(timeStr: String) -> String {
    // 假设输入的都是合法的
    
    // 数字提取出来放入集合
    var digSet = Set<Character>()
    for c in timeStr {
        if c != ":" {
            digSet.insert(c)
        }
    }
    // 取得输入时间的小时和分钟
    let (h, m) = strToTime(timeStr: timeStr)
    
    // 以下分成四种情况进行暴力扫描
    
    // h:m ~ h:59
    if m < 59 {
        for newM in (m + 1)...59 {
            if check(value: newM, inSet: digSet) {
                return String.init(format: "%02d:%02d", h, newM)
            }
        }
    }
    
    // h+1:00 ~ 23:59
    if h < 23 {
        for newH in (h + 1)...23 {
            guard check(value: newH, inSet: digSet) else {
                continue
            }
            for newM in 0...59 {
                if check(value: newM, inSet: digSet) {
                    return String.init(format: "%02d:%02d", newH, newM)
                }
            }
        }
    }
    
    // 00:00 ~ h-1:59
    if h > 0 {
        for newH in 0...(h - 1) {
            guard check(value: newH, inSet: digSet) else {
                continue
            }
            for newM in 0...59 {
                if check(value: newM, inSet: digSet) {
                    return String.init(format: "%02d:%02d", newH, newM)
                }
            }
        }
    }
    
    // h:00 ~ h:m
    for newM in 0...m {
        if check(value: newM, inSet: digSet) {
            return String.init(format: "%02d:%02d", h, newM)
        }
    }
    
    // 理论上不存在走到这里的可能
    fatalError()
}


print(nextTime(timeStr: "19:34"))
print(nextTime(timeStr: "23:59"))
print(nextTime(timeStr: "00:00"))
print(nextTime(timeStr: "00:01"))
print(nextTime(timeStr: "00:59"))
print(nextTime(timeStr: "11:11"))

Thanks for reading.

All the best wishes for you! 💕