leetcode解题: Binary Watch (401)

发表于 | 分类于

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”.

解法1：Backtracking/Recursion

好久没有写backtracking的题目了,搞了好久才搞出来。code也不一定简略但好歹是过了OA。
基本思路就是建立两个vector存储可能的时针值和分针值，然后记录已经用过的时针值和分针值。
要注意的是要去重，所以我用了一个unordered_set来记录当前所有的答案，如果有重复的则不插入。
另外要判断时针和分针的有效性。
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
47
48
49
50
51
52
53
54
55
class Solution {
public:
    vector<string> readBinaryWatch(int num) {
        if (num == 0) {
            return vector<string> {"0:00" };
        }
        vector<bool> hour_used(hours.size(), false);
        vector<bool> minute_used(minutes.size(), false);
        unordered_set<string> resSet;
        vector<string> res;
        helper(num, 0, 0, hour_used, minute_used, resSet);
        for (auto iter = resSet.begin(); iter != resSet.end(); ++iter) {
            res.emplace_back(*iter);
        }
        std::sort(res.begin(), res.end());
        return res;
    }
    void helper(int num, int hour, int minute, vector<bool>& hour_used, vector<bool>& minute_used, unordered_set<string>& res) {
        // Termination condition
        if (hour > 11 || minute > 59)
            return;
        if (num == 0) {
            string s;
            if (minute < 10) {
                s = to_string(hour) + ":0" + to_string(minute);
            } else {
                s = to_string(hour) + ":" + to_string(minute);
            }
            if (res.find(s) == res.end()) {
                res.emplace(s);    
            }
            return;
        }
        for (int i = 0; i < hours.size(); ++i) {
            if (!hour_used[i]) {
                hour_used[i] = true;
                helper(num - 1, hour + hours[i], minute, hour_used, minute_used, res);
                hour_used[i] = false;
            }
        }
        for (int i = 0; i < minutes.size(); ++i) {
            if (!minute_used[i]) {
                minute_used[i] = true;
                helper(num -1, hour, minute + minutes[i], hour_used, minute_used, res);    
                minute_used[i] = false;
            }
        }
    }
private:
    vector<int> hours {1,2,4,8};
    vector<int> minutes {1,2,4,8,16,32};
};

Java

1