二进制手表(LeetCode)
题目描述:
二进制手表顶部有 4 个 LED 代表小时(0-11),底部的 6 个 LED 代表分钟(0-59)。
每个 LED 代表一个 0 或 1,最低位在右侧。
例如,上面的二进制手表读取 “3:25”。
给定一个非负整数 n 代表当前 LED 亮着的数量,返回所有可能的时间。
案例:
输入: 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”。
- 分钟必须由两位数组成,可能会以零开头,比如 “10:2” 是无效的,应为 “10:02”。
解题思路:
- 由于在本题中时间只用时和分表示,所以表示的方式一共有720(12*60)种。
- 所以采用暴力遍历法,计算出每一个时间对应的手表中LED灯亮的个数。
- 每当有一个时间对应的手表中LED灯亮的个数等于题目给定数字,就将该时间字符串加入LIst中。
代码实现:
class Solution {
public List<String> readBinaryWatch(int num) {
List<String> list = new LinkedList<>();
for (int i = 0; i < 12; i++) {
for (int j = 0; j < 60; j++) {
if (numberOfOne(i) + numberOfOne(j) == num) {
String time = i + ":" + (j >= 10 ? j : "0" + j);
list.add(time);
}
}
}
return list;
}
/**
* 算出给定整数对应二进制数中1的个数
* @param value 给定整数
* @return 返回1的个数
*/
private int numberOfOne(int value) {
int count = 0;
while (value > 0) {
if ((value & 1) == 1) {
count++;
}
value >>= 1;
}
return count;
}
}