首页 > 代码库 > 401. Binary Watch
401. Binary Watch
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, thee 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".
Even if this is a "easy" question, there are still several points that is worth to mention.
1. how to use bitset in c++,
there are two articles that are very useful and straightforward:
http://en.cppreference.com/w/cpp/utility/bitset/bitset
http://www.geeksforgeeks.org/c-bitset-and-its-application/
Two most important diff in bitset, that need to keep in mind:
(1). a limitation of bitset is, N must be known at compile time, i.e., a constant (this limitation is not there with vector and dynamic array)
(2). Remember bitset starts its indexing backward that is for 10110, 0 are at 0th and 3rd indices whereas 1 are at 1st 2nd and 4th indices.
These two are very count-intuitive.
2. no need to use bit operation and backtracking for this problem because there is only a small fraction of data.
For small data, use clean code! The is true for many problems, even for hard problems.
1 vector<string> readBinaryWatch(int num) { 2 vector<string> rs; 3 for (int h = 0; h < 12; h++) 4 for (int m = 0; m < 60; m++) 5 if (bitset<10>(h << 6 | m).count() == num) 6 rs.emplace_back(to_string(h) + (m < 10 ? ":0" : ":") + to_string(m)); 7 return rs; 8 }
401. Binary Watch