Leetcode(401) Binary Watch

发表于 | 更新于 | 分类于

Description:

A binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6 LEDs on the bottom represent the minutes (0-59). Each LED represents a zero or one, with the least significant bit on the right. For example, the above binary watch reads “3:25”. Given a non-negative integer _n_ which represents the number of LEDs that are currently on, return all possible times the watch could represent. Example:

Input: n = 1
Return: [“1:00”, “2:00”, “4:00”, “8:00”, “0:01”, “0:02”, “0:04”, “0:08”, “0:16”, “0:32”]

Note:

  • The order of output does not matter.
  • The hour must not contain a leading zero, for example “01:00” is not valid, it should be “1:00”.
  • The minute must be consist of two digits and may contain a leading zero, for example “10:2” is not valid, it should be “10:02”.

解法：

这是我在Easy上花的时间最久的一道题。解法采用回溯法，即深度优先搜索，设计一个数组模拟10个小灯泡，初始为全0的状态，每次从头到尾找一个为0的点，置1点亮，继续进行下一层的搜索，搜索终止条件为需要点亮的灯泡数为0。注意回溯的精髓在于在搜索完成或失败的回退处理，具体来说，就是在递归调用之后需将状态还原。实现过程中还利用对称性进行了剪枝。具体代码如下：

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
class Solution {
    List<String> result = new ArrayList<String>();

    public List<String> readBinaryWatch(int num) {
        int[] led = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
        if (num <= 5) {
            dfs(num, led);
            List<String> tmpresult = new ArrayList<String>();
            for (String s :
                    result) {
                String[] tmp = s.split(":");
                int hours = Integer.parseInt(tmp[0]);
                int minute = Integer.parseInt(tmp[1]);
                if (minute >= 60 || hours >= 12) {
                    continue;
                }
                String h = Integer.toString(hours);
                String m = Integer.toString(minute);
                if (minute < 10) {
                    m = '0' + m;
                }
                if (!tmpresult.contains(h + ":" + m)) {
                    tmpresult.add(h + ":" + m);
                }
            }
            result = tmpresult;
        } else {
            dfs(10 - num, led);
            List<String> tmpresult = new ArrayList<String>();
            for (String s :
                    result) {
                String[] tmp = s.split(":");
                int hours = Integer.parseInt(tmp[0]);
                int minute = Integer.parseInt(tmp[1]);
                hours = 15 - hours;
                minute = 63 - minute;
                if (minute >= 60 || hours >= 12) {
                    continue;
                }
                String h = Integer.toString(hours);
                String m = Integer.toString(minute);
                if (minute < 10) {
                    m = '0' + m;
                }
                if (!tmpresult.contains(h + ":" + m)) {
                    tmpresult.add(h + ":" + m);
                }
            }
            result = tmpresult;
        }

        return result;
    }

    void dfs(int num, int[] led) {
        if (num == 0) {
            int hour = 0;
            int minute = 0;
            for (int i = 0; i < 10; i++) {
                if (i < 4) {
                    hour = (int) (hour + led[i] * Math.pow(2, i));
                } else {
                    minute = (int) (minute + led[i] * Math.pow(2, i - 4));
                }
            }
            String h = Integer.toString(hour);
            String m = Integer.toString(minute);
            if (minute < 10) {
                m = '0' + m;
            }
            if (!result.contains(h + ":" + m)) {
                result.add(h + ":" + m);
            }
            return;
        }
        for (int i = 0; i < 10; i++) {
            if (led[i] == 0) {
                led[i] = 1;
                dfs(num - 1, led);
                led[i] = 0;
            }
        }
    }
}