forked from haoel/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathBinaryWatch.cpp
More file actions
111 lines (99 loc) · 3.36 KB
/
BinaryWatch.cpp
File metadata and controls
111 lines (99 loc) · 3.36 KB
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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
// Source : https://leetcode.com/problems/binary-watch/
// Author : Hao Chen
// Date : 2016-11-05
/***************************************************************************************
*
* 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 = 1Return: ["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".
***************************************************************************************/
class Solution {
private:
void combination(int nLED, int nLight, int max, bool zero,
int start, int k, int solution,
vector<vector<string>>& result) {
if (solution > max){
return;
}
if (k == 0) {
char tmp[5] = "";
if (zero) {
sprintf(tmp, "%02d", solution);
}else{
sprintf(tmp, "%d", solution);
}
result[nLight].push_back(tmp);
return;
}
for (int i=start; i<=nLED-k; i++) {
solution += pow(2, i);
combination(nLED, nLight, max, zero, i+1, k-1, solution, result);
solution -= pow(2, i);
}
}
void generate_combination(int nLED, int max, bool zero, vector<vector<string>>& result) {
for (int i=0; i<nLED; i++) {
combination(nLED, i, max, zero, 0, i, 0, result);
}
}
void print(vector<vector<string>>& vv) {
for(auto v : vv) {
cout << "[ ";
for (auto i : v) {
cout << i << " ";
}
cout << "]" << endl;
}
}
private:
vector<vector<string>> hour;
vector<vector<string>> mins;
public:
Solution():hour(4, vector<string>()), mins(6, vector<string>()){
generate_combination(4, 11, false, hour);
//print(hour);
//[ 0 ]
//[ 1 2 4 8 ]
//[ 3 5 9 6 10 ]
//[ 7 11 ]
generate_combination(6, 59, true, mins);
//print(mins);
//[ 00 ]
//[ 01 02 04 08 16 32 ]
//[ 03 05 09 17 33 06 10 18 34 12 20 36 24 40 48 ]
//[ 07 11 19 35 13 21 37 25 41 49 14 22 38 26 42 50 28 44 52 56 ]
//[ 15 23 39 27 43 51 29 45 53 57 30 46 54 58 ]
//[ 31 47 55 59 ]
}
vector<string> readBinaryWatch(int num) {
vector<string> result;
for (int i = 0; i <= 3 && i <= num; i++) {
if (num - i > 5) {
continue;
}
for (auto h : hour[i]) {
for (auto m : mins[num - i]) {
result.push_back( h + ":" + m );
}
}
}
return result;
}
};