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".
題目描述:
二進制手表頂部有 4 個 LED 代表小時（0-11），底部的 6 個 LED 代表分鐘（0-59）。
每個 LED 代表一個 0 或 1菲饼，最低位在右側(cè)里初。
例如掂铐，上面的二進制手表讀取 “3:25”芒澜。
給定一個非負整數(shù) n 代表當前 LED 亮著的數(shù)量蛮原，返回所有可能的時間卧须。
案例:
輸入: n = 1
返回: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]
注意事項:
輸出的順序沒有要求。
小時不會以零開頭，比如 “01:00” 是不允許的花嘶，應為 “1:00”笋籽。
分鐘必須由兩位數(shù)組成，可能會以零開頭椭员，比如 “10:2” 是無效的车海，應為 “10:02”。
思路:
參考Java源碼Integer.bitCount算法解析隘击，分析原理（統(tǒng)計二進制bit位）
設置兩個指針, 一個為時針(0~12), 一個為分針(0~60), 統(tǒng)計二進制中 1的數(shù)量滿足要求的即可
時間復雜度O(1), 空間復雜度O(1)
代碼:
C++:
class Solution
{
public:
vector<string> readBinaryWatch(int num)
{
vector<string> result;
// 左移 6位是為了j(j < 64)與 i一定不相交, 取 6-28都可以
for (int i = 0; i < 12; i++) for (int j = 0; j < 60; j++) if (bitCount((i << 6) | j) == num) result.push_back(to_string(i) + ":" + (j > 9 ? "" : "0") + to_string(j));
return result;
}
private:
int bitCount(int i)
{
i = (i & 0x55555555) + ((i >> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
i = (i & 0x0f0f0f0f) + ((i >> 4) & 0x0f0f0f0f);
i = (i & 0x00ff00ff) + ((i >> 8) & 0x00ff00ff);
i = (i & 0x0000ffff) + ((i >> 16) & 0x0000ffff);
return i;
}
};
Java:
class Solution {
public List<String> readBinaryWatch(int num) {
List<String> result = new ArrayList<>();
for (int i = 0; i < 12; i++) for (int j = 0; j < 60; j++) if (Integer.bitCount((i << 6) | j) == num) result.add(i + ":" + (j > 9 ? "" : "0") + j);
return result;
}
}
Python:
class Solution:
def readBinaryWatch(self, num: int) -> List[str]:
result = []
for i in range(12):
for j in range(60):
if bin(i).count('1') + bin(j).count('1') == num:
if j < 10:
j = "0" + str(j)
result.append(str(i) + ":" + str(j))
return result
