Binary Watch (E)
題目
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位表示小時，6位表示分鐘，求在10位中選出n位一共可以得到的時間組合，
思路
回溯法，需要注意其中的坑：小時最大值只能為11，分鐘最大值只能為59，
另一種暴力法是，小時數只有12種可能，分鐘數只有60種可能，直接暴力搜索每一種組合，判斷它們二進制1的位數相加是否為n，
代碼實作
Java
回溯法
class Solution {
public List<String> readBinaryWatch(int num) {
List<String> ans = new ArrayList<>();
int[] available = { 1, 2, 4, 8, 101, 102, 104, 108, 116, 132 };
dfs(num, new int[2], available, 0, ans);
return ans;
}
private void dfs(int num, int[] time, int[] available, int index, List<String> ans) {
if (num == 0) {
ans.add(time[0] + ":" + (time[1] < 10 ? "0" + time[1] : time[1]));
return;
}
if (index == 10) {
return;
}
if (available[index] > 100 && time[1] + available[index] - 100 < 60) {
time[1] += available[index] - 100;
dfs(num - 1, time, available, index + 1, ans);
time[1] -= available[index] - 100;
} else if (available[index] < 100 && time[0] + available[index] < 12) {
time[0] += available[index];
dfs(num - 1, time, available, index + 1, ans);
time[0] -= available[index];
}
dfs(num, time, available, index + 1, ans);
}
}
暴力法
class Solution {
public List<String> readBinaryWatch(int num) {
List<String> ans = new ArrayList<>();
for (int h = 0; h < 12; h++) {
for (int m = 0; m < 60; m++) {
if (countOne(h) + countOne(m) == num) {
ans.add(h + ":" + (m < 10 ? "0" + m : m));
}
}
}
return ans;
}
private int countOne(int num) {
int count = 0;
while (num != 0) {
if ((num & 1) == 1) {
count++;
}
num >>= 1;
}
return count;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/21341.html
標籤：其他
上一篇：兩數之和
下一篇：質數