【MEDIUM】Next Closest Time

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

问题

原题链接:https://leetcode.com/problems/next-closest-time/

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
    • 按这样的顺序扫描,扫描时检查是不是所有的数字都在集合中,如果是就直接输出。

解决方法

class Solution {
    // 输入的字符串提取小时和分钟
    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 nextClosestTime(_ time: String) -> String {
        // 假设输入的都是合法的
        
        // 数字提取出来放入集合
        var digSet = Set<Character>()
        for c in time {
            if c != ":" {
                digSet.insert(c)
            }
        }
        // 取得输入时间的小时和分钟
        let (h, m) = strToTime(timeStr: time)
        
        // 以下分成四种情况进行暴力扫描
        
        // 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()
    }
}

Thanks for reading.

All the best wishes for you! 💕