05 August 2008
给定以“HH:MM”格式表示的时间，通过重用当前数字形成下一个最接近的时间。一个数字可以重复使用多少次是没有限制的。
您可以假设给定的输入字符串始终有效。例如，“01:34”、“12:09”都是有效的。 “1:34”、“12:9”都是无效的。
Input: time = “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.
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
47
class Solution {
/*
总共有四位，那共有4 * 4 * 4 * 4 = 256个时间可以选择，用DFS全部尝试一下
*/
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);
}
}
}