文章目录
- 一【题目类别】
- 二【题目难度】
- 三【题目编号】
- 四【题目描述】
- 五【题目示例】
- 六【题目提示】
- 七【解题思路】
- 八【时间频度】
- 九【代码实现】
- 十【提交结果】
一【题目类别】
- 回溯
二【题目难度】
- 简单
三【题目编号】
- 401.二进制手表
四【题目描述】
- 二进制手表顶部有 4 个 LED 代表 小时(0-11),底部的 6 个 LED 代表 分钟(0-59)。每个 LED 代表一个 0 或 1,最低位在右侧。
- 例如,下面的二进制手表读取
"4:51"
。
- 给你一个整数
turnedOn
,表示当前亮着的 LED 的数量,返回二进制手表可以表示的所有可能时间。你可以 按任意顺序 返回答案。 - 小时不会以零开头:
- 例如,
"01:00"
是无效的时间,正确的写法应该是"1:00"
。
- 例如,
- 分钟必须由两位数组成,可能会以零开头:
- 例如,
"10:2"
是无效的时间,正确的写法应该是"10:02"
。
- 例如,
五【题目示例】
-
示例 1:
- 输入:turnedOn = 1
- 输出:[“0:01”,“0:02”,“0:04”,“0:08”,“0:16”,“0:32”,“1:00”,“2:00”,“4:00”,“8:00”]
-
示例 2:
- 输入:turnedOn = 9
- 输出:[]
六【题目提示】
0 <= turnedOn <= 10
七【解题思路】
- 该题目很容易想到使用回溯+剪枝来解决
- 我们需要在10个灯中选择n个灯点亮,并计算其时间和,需要注意要判断该时间和是否合理,如果不合理(小时超过11,分钟超过59)需要进行剪枝
- 上面提到“选择n个灯点亮”,我们肯定不能一起全部点亮,所以需要用到回溯,一个一个选择,还可以进行不同的组合
- 为了实现“选择n个灯点亮”,我们可以设置小时数组和分钟数组,长度为10,不足10位补零,目的是使用这两个数组来模拟小时和分钟的亮灯情况(数组索引选中的值即为亮的灯)
- 具体实现可以参考下面的代码,最后按照回溯+剪枝的方法将结果计算出并返回即可
八【时间频度】
- 时间复杂度: O ( C 10 n ) O(C_{10}^{n}) O(C10n), n n n为传入的参数值
- 空间复杂度: O ( n ) O(n) O(n), n n n为传入的参数值
九【代码实现】
- Java语言版
class Solution {
public List<String> readBinaryWatch(int turnedOn) {
// 定义时间数组
int[] hours = {1, 2, 4, 8, 0, 0, 0, 0, 0, 0};
int[] minutes = {0, 0, 0, 0, 1, 2, 4, 8, 16, 32};
// 定义结果列表
List<String> res = new ArrayList<>();
// 回溯计算可能的时间组合
backtrack(turnedOn, 0, 0, 0, res, hours, minutes);
// 返回结果
return res;
}
private void backtrack(int count, int index, int hour, int minute, List<String> res, int[] hours, int[] minutes) {
if (hour > 11 || minute > 59) {
return;
}
if (count == 0) {
res.add(String.format("%d:%02d", hour, minute));
}
for (int i = index; i < 10; i++) {
backtrack(count - 1, i + 1, hour + hours[i], minute + minutes[i], res, hours, minutes);
}
}
}
- Python语言版
class Solution:
def readBinaryWatch(self, turnedOn: int) -> List[str]:
# 定义时间数组
hours = [1, 2, 4, 8, 0, 0, 0, 0, 0, 0]
minutes = [0, 0, 0, 0, 1, 2, 4, 8, 16, 32]
# 定义结果列表
res = []
# 回溯计算可能的时间组合
def backtrack(count, index, hour, minute):
if hour > 11 or minute > 59:
return
if count == 0:
res.append("%d:%02d" % (hour, minute))
return
for i in range(index, 10):
backtrack(count - 1, i + 1, hour + hours[i], minute + minutes[i])
backtrack(turnedOn, 0, 0, 0)
# 返回结果
return res
- C语言版
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
#define MAX_RES_SIZE 256
// 定义回调函数来递归查找所有可能的时间组合
void backtrack(int count, int index, int hour, int minute, char res[MAX_RES_SIZE][6], int *returnSize, int * hours, int *minutes)
{
if (hour > 11 || minute > 59)
{
return;
}
if (count == 0)
{
sprintf(res[*returnSize], "%d:%02d", hour, minute);
(*returnSize)++;
return;
}
for (int i = index; i < 10; i++)
{
backtrack(count - 1, i + 1, hour + hours[i], minute + minutes[i], res, returnSize, hours, minutes);
}
}
char** readBinaryWatch(int turnedOn, int* returnSize)
{
// 定义时间数组
int hours[] = {1, 2, 4, 8, 0, 0, 0, 0, 0, 0};
int minutes[] = {0, 0, 0, 0, 1, 2, 4, 8, 16, 32};
// 分配空间用于存储结果
char (*res)[6] = malloc(MAX_RES_SIZE * sizeof(*res));
*returnSize = 0;
// 开始递归
backtrack(turnedOn, 0, 0, 0, res, returnSize, hours, minutes);
// 转换为char**返回
char** finRes = malloc(*returnSize * sizeof(char*));
for (int i = 0; i < *returnSize; i++)
{
finRes[i] = res[i];
}
return finRes;
}
十【提交结果】
-
Java语言版
-
Python语言版
-
C语言版