http://bookshadow.com/weblog/2017/09/24/leetcode-next-closest-time/
X. Videos
Google Coding Interview (2019) - Next Closest Time (LeetCode)
花花酱 LeetCode 681. Next Closest Time - 刷题找工作 EP70
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:
Example 2:
题目大意：
给定格式为HH:MM的时间time，根据其中的数字，组成距离当前时间最近的下一个时刻。
解题思路：
将time的数字取出并排序，记为stime，令X = stime[0]
从time的低位向高位枚举，将stime中恰好大于当前值的值进行替换，并将其后的所有值替换为X
若不存在这样的替换，则返回XX:XX
X.
http://hehejun.blogspot.com/2018/08/leetcodenext-closest-time.html
解法2：替换数字。先把出现的数字去重排序，然后从最低位的分钟开始替换，如果低位分钟上的数字已经是最大的数字，就把低位分钟上的数字换成最小的数字，否则就将低位分钟上的数字换成下一个较大的数字。高位分钟上的数字已经是最大的数字，或则下一个数字大于5，那么直接换成最小值，否则就将高位分钟上的数字换成下一个较大的数字。小时数字也是同理，小时低位上的数字情况比较复杂，当小时高位不为2的时候，低位可以是任意数字，而当高位为2时，低位需要小于等于3。对于小时高位，其必须要小于等于2。Time: O(4*10)，Space: O(10)
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);
}
找字典序大于当前时间最小时间，只需要从LSB(least significant bit)开始，对处于每一位的digit d，找到大于d的最小的合法的数字，如果找不到赋予当前位4个位当中的最小数即可。因为最小的数一定可以保证小于等于2(最左边的位)，所以只要输入是合法的，我们永远可以找到一个合法的解。常数时间和空间
public String nextClosestTime(String time) {
char[] res = time.toCharArray();
//找到所有可用的数，排序后存起来
char[] digits = new char[]{res[0], res[1], res[3], res[4]};
Arrays.sort(digits);
//从右到左对res进行操作，只要有当前最小单位时间的替换，返回替换后的时间
res[4] = findNext(digits, res[4], '9');
if (res[4] > time.charAt(4)) return String.valueOf(res);
res[3] = findNext(digits, res[3], '5');
if (res[3] > time.charAt(3)) return String.valueOf(res);
res[1] = res[0] == '2' ? findNext(digits, res[1], '3') : findNext(digits, res[1], '9');
if (res[1] > time.charAt(1)) return String.valueOf(res);
res[0] = findNext(digits, res[0], '2');
return String.valueOf(res);
}
private char findNext(char[] digits, char cur, char upper) {
if (cur == upper) return digits[0];
//找到cur的位置，然后加1得到下一个位置
int pos = Arrays.binarySearch(digits, cur)+1;
//如果下一个位置的数还是原来的数，或者超过了上限数，前进到再下一个
while (pos < 4 && (digits[pos] == cur || digits[pos] > upper)) pos++;
return pos == 4 ? digits[0] : digits[pos];
}
解法一：最优解法，时间复杂度为O(4*10)，空间复杂度为O(10)，思路：用一个伪哈希表来存给的时间的数字，然后从第四位开始，去哈希表里找有没有比给定的第四位大而且合法的数字，如果有则返回带有这个合法数字的新的string；如果没有，就把第四位设为哈希表里的最小值。依次类推，从第四位走到第一位，如果第一位还不存在一个比它大的合法值，则四位都设为最小值，然后返回，此时对应的情况就是example2里的情况，返回的是第二天的最小时间。此解法简单易懂，而且效率很高，beats 96%的leetcoder.
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);
}
X. DFS + Brute Force
解法3：找出这四个数字的所有可能的时间组合，然后和给定时间比较，maintain一个差值最小的，返回这个string。Time: O(4^4)，Space: O(4)。
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);
}
}
解法二：找出这四个数字的所有可能的时间组合，然后和给定时间比较，maintain一个差值最小的，返回这个string。时间复杂度O(4^4)，空间复杂度O(4)。
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);
}
}
string nextClosestTime(string time) { vector<int> d = { time[0] - '0', time[1] - '0', time[3] - '0', time[4] - '0' }; int h = d[0] * 10 + d[1]; int m = d[2] * 10 + d[3]; vector<int> curr(4, 0); int now = toTime(h, m); int best = now; dfs(0, d, curr, now, best); char buff[5]; sprintf(buff, "%02d:%02d", best / 60, best % 60); return string(buff); } private: void dfs(int dep, const vector<int>& digits, vector<int>& curr, int time, int& best) { if (dep == 4) { int curr_h = curr[0] * 10 + curr[1]; int curr_m = curr[2] * 10 + curr[3]; if (curr_h > 23 || curr_m > 59) return; int curr_time = toTime(curr_h, curr_m); if (timeDiff(time, curr_time) < timeDiff(time, best)) best = curr_time; return; } for (int digit : digits) { curr[dep] = digit; dfs(dep + 1, digits, curr, time, best); } } int toTime(int h, int m) { return h * 60 + m; } int timeDiff(int t1, int t2) { if (t1 == t2) return INT_MAX; return ((t2 - t1) + 24 * 60) % (24 * 60); }X. Limited set - Brute Force
下面这种方法的写法比较简洁，实际上用了暴力搜索，由于按分钟算的话，一天只有1440分钟，也就是1440个时间点，我们可以从当前时间点开始，遍历一天的时间，也就是接下来的1440个时间点，得到一个新的整型时间点后，我们按位来更新结果res，对于每个更新的数字字符，看其是否在原时间点字符中存在，如果不存在，直接break，然后开始遍历下一个时间点，如果四个数字都成功存在了，那么将当前时间点中间夹上冒号返回即可
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); }http://storypku.com/2017/09/leetcode-question-681-next-closest-time/
https://www.codetd.com/article/3422355
解法1：Brute fore， 由于给的时间只到分钟，一天中有1440个分钟，也就是1440个时间点，可以从当前时间点开始，遍历一天的1440个时间点，每到一个时间点，看其所有的数字是否在原时间点字符中存在，如果不存在，直接break，然后开始遍历下一个时间点，如果四个数字都存在，说明找到了，换算成题目的时间形式返回即可。
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; } }http://buttercola.blogspot.com/2019/03/leetcode-681-next-closest-time.html
One corner case to consider is if the time is 11:11, the next time should be 11:11 as it's for next day. But int the code since we check diff > 0, the ans will return 0. To handle this case, the initial value should be original time.
public String nextClosestTime(String time) { int original = getElapsedMinutes(time); int minDiff = Integer.MAX_VALUE; int ans = original; Set<Integer> set = new HashSet<>(); for (int i = 0; i < time.length(); i++) { if (time.charAt(i) != ':') { set.add(Character.getNumericValue(time.charAt(i))); } } for (int h1 : set) { for (int h2 : set) { if (h1 * 10 + h2 < 24) { for (int m1 : set) { for (int m2 : set) { if (m1 * 10 + m2 < 60) { int currTime = (h1 * 10 + h2) * 60 + (m1 * 10 + m2); int diff = Math.floorMod(currTime - original, 24 * 60); if (diff > 0 && diff < minDiff) { ans = currTime; minDiff = diff; } } } } } } } return String.format("%02d:%02d", ans / 60, ans % 60); } private int getElapsedMinutes(String time) { int hour = Character.getNumericValue(time.charAt(0)) * 10 + Character.getNumericValue(time.charAt(1)); int min = Character.getNumericValue(time.charAt(3)) * 10 + Character.getNumericValue(time.charAt(4)); return hour * 60 + min; }
X. Videos
Google Coding Interview (2019) - Next Closest Time (LeetCode)
花花酱 LeetCode 681. Next Closest Time - 刷题找工作 EP70
