681 Next Closest Time

681. Next Closest Time​
1. Question
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:
1
Input: "19:34"
2
​
3
Output: "19:39"
4
​
5
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
6
, because this occurs 23 hours and 59 minutes later.
Copied!
Example 2:
1
Input: "23:59"
2
​
3
Output: "22:22"
4
​
5
Explanation: The next closest time choosing from digits 2, 3, 5, 9, is 22:22
6
. It may be assumed that the returned time is next day's time since it is smaller than the input time numerically.
Copied!
2. Implementation
(1) DFS (Enumeration)
思路: 用DFS枚举所有可能的time，尝试对time的每个digit变为可用digit，比较谁离原来的time最近
1
class Solution {
2
    int hour;
3
    int min;
4
    int diff = Integer.MAX_VALUE;
5
​
6
    public String nextClosestTime(String time) {
7
        if (time == null || time.length() == 0) {
8
            return time;
9
        }
10
​
11
        int[] digit = new int[4];
12
        String[] val = time.split(":");
13
        hour = Integer.parseInt(val[0]);
14
        min = Integer.parseInt(val[1]);
15
​
16
        digit[0] = hour / 10;
17
        digit[1] = hour % 10;
18
        digit[2] = min / 10;
19
        digit[3] = min % 10;
20
​
21
        String[] res = new String[1];
22
​
23
        getNextClosestTime(digit, 0, new int[4], res);
24
        return res[0];
25
    }
26
​
27
    public void getNextClosestTime(int[] digit, int index, int[] temp, String[] res) {
28
        if (index == 4) {
29
            int curHour = 10 * temp[0] + temp[1];
30
            int curMin = 10 * temp[2] + temp[3];
31
            if (curHour >= 0 && curHour <= 23 && curMin >= 0 && curMin <= 59) {
32
                int curDiff = getDiff(curHour, curMin);
33
​
34
                if (curDiff < diff) {
35
                    diff = curDiff;
36
                    res[0] = formatTime(curHour) + ":" + formatTime(curMin);
37
                }
38
            }
39
        }
40
        else {
41
            for (int i = 0; i < 4; i++) {
42
                temp[index] = digit[i];
43
                getNextClosestTime(digit, index + 1, temp, res);
44
            }
45
        }
46
    }
47
​
48
    public int getDiff(int curHour, int curMin) {
49
        int diff1 = 3600 - (60 * hour + min);
50
        int diff2 = 3600 - (60 * curHour + curMin);
51
        return diff2 < diff1 ? diff1 - diff2 : diff1 - diff2 + 3600;
52
    }
53
​
54
    public String formatTime(int time) {
55
        if (time >= 0 && time <= 9) {
56
            return "0" + time;
57
        }
58
        return "" + time;
59
    }
60
}
Copied!
3. Time & Space Complexity
DFS: 时间复杂度O(1), 总共只有4 * 4 * 4 * 4 = 256种情况, 空间复杂度O(1), 深度为time的digit的个数为4

158 Read N Characters Given Read4 II - Call multiple times

317 Shortest Distance from All Buildings

Last modified 2yr ago

Copy link

Contents

681. Next Closest Time

1. Question

2. Implementation

3. Time & Space Complexity

681. Next Closest Time​

1. Question

2. Implementation

3. Time & Space Complexity

681. Next Closest Time