[LeetCode] 681. Next Closest Time 下一个最近时间点

2021年09月15日 阅读数:3
这篇文章主要向大家介绍[LeetCode] 681. 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.html

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.java

Example 1:python

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:git

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.

给一个时间,只能用原时间里的数字,求能组成的最近的下一个时间点,当下个时间点超过零点时,就当次日的时间。post

解法1:Brute fore, 因为给的时间只到分钟,一天中有1440个分钟,也就是1440个时间点,能够从当前时间点开始,遍历一天的1440个时间点,每到一个时间点,看其全部的数字是否在原时间点字符中存在,若是不存在,直接break,而后开始遍历下一个时间点,若是四个数字都存在,说明找到了,换算成题目的时间形式返回便可。this

解法2:替换数字。先把出现的数字去重排序,而后从最低位的分钟开始替换,若是低位分钟上的数字已是最大的数字,就把低位分钟上的数字换成最小的数字,不然就将低位分钟上的数字换成下一个较大的数字。高位分钟上的数字已是最大的数字,或则下一个数字大于5,那么直接换成最小值,不然就将高位分钟上的数字换成下一个较大的数字。小时数字也是同理,小时低位上的数字状况比较复杂,当小时高位不为2的时候,低位能够是任意数字,而当高位为2时,低位须要小于等于3。对于小时高位,其必需要小于等于2。Time: O(4*10),Space: O(10)url

解法3:找出这四个数字的全部可能的时间组合,而后和给定时间比较,maintain一个差值最小的,返回这个string。Time: O(4^4),Space: O(4)。orm

Java: 1htm

class Solution {
    public String nextClosestTime(String time) {
        int hour = Integer.parseInt(time.substring(0, 2));
        int min = Integer.parseInt(time.substring(3, 5));
        while (true) {            
            if (++min == 60) {
                min = 0;
                ++hour;
                hour %= 24;
            }
            String curr = String.format("%02d:%02d", hour, min);
            Boolean valid = true;
            for (int i = 0; i < curr.length(); ++i)
                if (time.indexOf(curr.charAt(i)) < 0) {
                    valid = false;
                    break;
                }
            if (valid) return curr;
        }
    }
}  

Java: 2blog

public String nextClosestTime(String time) {
        char[] t = time.toCharArray(), result = new char[4];
        int[] list = new int[10];
        char min = '9';
        for (char c : t) {
            if (c == ':') continue;
            list[c - '0']++;
            if (c < min) {
                min = c;
            }
        }
        for (int i = t[4] - '0' + 1; i <= 9; i++) {
            if (list[i] != 0) {
                t[4] = (char)(i + '0');
                return new String(t);
            }
        }
        t[4] = min;
        for (int i = t[3] - '0' + 1; i <= 5; i++) {
            if (list[i] != 0) {
                t[3] = (char)(i + '0');
                return new String(t);
            }
        }
        t[3] = min;
        int stop = t[0] < '2' ? 9 : 3;
        for (int i = t[1] - '0' + 1; i <= stop; i++) {
            if (list[i] != 0) {
                t[1] = (char)(i + '0');
                return new String(t);
            }
        }
        t[1] = min;
        for (int i = t[0] - '0' + 1; i <= 2; i++) {
            if (list[i] != 0) {
                t[0] = (char)(i + '0');
                return new String(t);
            }
        }
        t[0] = min;
        return new String(t);
    }  

Java: 3

int diff = Integer.MAX_VALUE;
    String result = "";

    public String nextClosestTime(String time) {
        Set<Integer> set = new HashSet<>();
        set.add(Integer.parseInt(time.substring(0, 1)));
        set.add(Integer.parseInt(time.substring(1, 2)));
        set.add(Integer.parseInt(time.substring(3, 4)));
        set.add(Integer.parseInt(time.substring(4, 5)));

        if (set.size() == 1) return time;

        List<Integer> digits = new ArrayList<>(set);
        int minute = Integer.parseInt(time.substring(0, 2)) * 60 + Integer.parseInt(time.substring(3, 5));

        dfs(digits, "", 0, minute);

        return result;
    }

    private void dfs(List<Integer> digits, String cur, int pos, int target) {
        if (pos == 4) {
            int m = Integer.parseInt(cur.substring(0, 2)) * 60 + Integer.parseInt(cur.substring(2, 4));
            if (m == target) return;
            int d = m - target > 0 ? m - target : 1440 + m - target;
            if (d < diff) {
                diff = d;
                result = cur.substring(0, 2) + ":" + cur.substring(2, 4);
            }
            return;
        }

        for (int i = 0; i < digits.size(); i++) {
            if (pos == 0 && digits.get(i) > 2) continue;
            if (pos == 1 && Integer.parseInt(cur) * 10 + digits.get(i) > 23) continue;
            if (pos == 2 && digits.get(i) > 5) continue;
            if (pos == 3 && Integer.parseInt(cur.substring(2)) * 10 + digits.get(i) > 59) continue;
            dfs(digits, cur + digits.get(i), pos + 1, target);
        }
    } 

Python:

class Solution(object):
    def nextClosestTime(self, time):
        """
        :type time: str
        :rtype: str
        """
        h, m = time.split(":")
        curr = int(h) * 60 + int(m)
        result = None
        for i in xrange(curr+1, curr+1441):
            t = i % 1440
            h, m = t // 60, t % 60
            result = "%02d:%02d" % (h, m)
            if set(result) <= set(time):
                break
        return result

Python:

class Solution(object):
    def nextClosestTime(self, time):
        """
        :type time: str
        :rtype: str
        """
        time = time[:2] + time[3:]
        isValid = lambda t: int(t[:2]) < 24 and int(t[2:]) < 60
        stime = sorted(time)
        for x in (3, 2, 1, 0):
            for y in stime:
                if y <= time[x]: continue
                ntime = time[:x] + y + (stime[0] * (3 - x))
                if isValid(ntime): return ntime[:2] + ':' + ntime[2:]
        return stime[0] * 2 + ':' + stime[0] * 2  

C++:

class Solution {
public:
    string nextClosestTime(string time) {
        string res = "0000";
        vector<int> v{600, 60, 10, 1};
        int found = time.find(":");
        int cur = stoi(time.substr(0, found)) * 60 + stoi(time.substr(found + 1));
        for (int i = 1, d = 0; i <= 1440; ++i) {
            int next = (cur + i) % 1440;
            for (d = 0; d < 4; ++d) {
                res[d] = '0' + next / v[d]; 
                next %= v[d];
                if (time.find(res[d]) == string::npos) break;
            }
            if (d >= 4) break;
        }
        return res.substr(0, 2) + ":" + res.substr(2);
    }
};

C++:  

class Solution {
public:
    string nextClosestTime(string time) {
        string res = time;
        set<int> s{time[0], time[1], time[3], time[4]};
        string str(s.begin(), s.end());
        for (int i = res.size() - 1; i >= 0; --i) {
            if (res[i] == ':') continue;
            int pos = str.find(res[i]);
            if (pos == str.size() - 1) {
                res[i] = str[0];
            } else {
                char next = str[pos + 1];
                if (i == 4) {
                    res[i] = next;
                    return res;
                } else if (i == 3 && next <= '5') {
                    res[i] = next;
                    return res; 
                } else if (i == 1 && (res[0] != '2' || (res[0] == '2' && next <= '3'))) {
                    res[i] = next;
                    return res;
                } else if (i == 0 && next <= '2') {
                    res[i] = next;
                    return res;
                }
                res[i] = str[0];
            }
        }
        return res;
    }
};

  

  

 

All LeetCode Questions List 题目汇总