Problem:
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”.
Solution 1:
Time complexity: O(11*59*n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// Author: Huahua // Running time: 2 ms (beats 100%) class Solution { public: vector<string> readBinaryWatch(int num) { vector<string> ans; for (int i = 0; i <= num; ++i) for (int h : nums(i, 12)) for (int m : nums(num - i, 60)) ans.push_back(to_string(h) + (m < 10 ? ":0" : ":") + to_string(m)); return ans; } private: // Return numbers in [0,r) that has b 1s in their binary format. vector<int> nums(int b, int r) { vector<int> ans; for (int n = 0; n < r; ++n) if (__builtin_popcount(n) == b) ans.push_back(n); return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment