Problem:
https://leetcode.com/problems/next-closest-time/description/
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.
Ads
Solution1: Brute force
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// Author: Huahua // Running time: 3 ms class Solution { public: string nextClosestTime(string time) { set<char> s(time.begin(), time.end()); int hour = stoi(time.substr(0, 2)); int min = stoi(time.substr(3, 2)); while (true) { if (++min == 60) { min = 0; (++hour) %= 24; } char buffer[5]; sprintf(buffer, "%02d:%02d", hour, min); set<char> s2(buffer, buffer + sizeof(buffer)); if (includes(s.begin(), s.end(), s2.begin(), s2.end())) return string(buffer); } return time; } }; |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// Author: Huahua // Running time: 85 ms 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; } } } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
""" Author: Huahua Running time: 65 ms """ class Solution: def nextClosestTime(self, time): s = set(time) hour = int(time[0:2]) minute = int(time[3:5]) while True: minute += 1 if minute == 60: minute = 0 hour = 0 if hour == 23 else hour + 1 time = "%02d:%02d" % (hour, minute) if set(time) <= s: return time return time |
Solution 2: DFS
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
// Author: Huahua // Running time: 3 ms class Solution { public: 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); } }; |
Solution 3: Brute force + Time library
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
""" Author: Huahua Running time: 292 ms """ from datetime import * class Solution: def nextClosestTime(self, time): s = set(time) while True: time = (datetime.strptime(time, '%H:%M') + timedelta(minutes=1)).strftime('%H:%M') if set(time) <= s: return time return time |