Next Closest Time
https://leetcode.com/problems/next-closest-time/description/
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
Thoughts
有两种比较直观的解法, 一种是不断+1分钟, 判断新时间是否存在. O(1440). 还有就是搜索, 把所有可能的组合写出来依次判断是否差的最小, O(256).
Code
class Solution {
public String nextClosestTime(String time) {
int start = Integer.parseInt(time.substring(0, 2)) * 60 + Integer.parseInt(time.substring(3));
int[] nums = new int[4], res = new int[4];
for (int i = 0, j = 0; i < time.length(); ++i) {
if (time.charAt(i) == ':') {
continue;
}
nums[j++] = time.charAt(i) - '0';
}
int m = Integer.MAX_VALUE;
for (int i = 0; i < 4; ++i) {
for (int j = 0; j < 4; ++j) {
int hour = nums[i] * 10 + nums[j];
if (hour > 23) {
continue;
}
for (int p = 0; p < 4; ++p) {
for (int q = 0; q < 4; ++q) {
int min = nums[p] * 10 + nums[q];
if (min > 59) {
continue;
}
int now = hour * 60 + min;
int diff = now > start ? now - start : now + 24 * 60 - start;
if (diff < m) {
m = diff;
res[0] = nums[i];
res[1] = nums[j];
res[2] = nums[p];
res[3] = nums[q];
}
}
}
}
}
return res[0] + "" + res[1] + ":" + res[2] + "" + res[3];
}
}
Analysis
时间复杂度O(4^4).
Last updated
Was this helpful?