一【題目類別】

• 回溯

二【題目難度】

• 簡單

三【題目編號】

• 401.二進制手表

四【題目描述】

• 二進制手表頂部有 4 個 LED 代表 小時（0-11），底部的 6 個 LED 代表 分鐘（0-59）。每個 LED 代表一個 0 或 1，最低位在右側。
• 例如，下面的二進制手表讀取 "4:51" 。
  
• 給你一個整數(shù) turnedOn ，表示當前亮著的 LED 的數(shù)量，返回二進制手表可以表示的所有可能時間。你可以 按任意順序 返回答案。
• 小時不會以零開頭：
  • 例如，"01:00" 是無效的時間，正確的寫法應該是 "1:00" 。
• 分鐘必須由兩位數(shù)組成，可能會以零開頭：
  • 例如，"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個燈點亮”，我們肯定不能一起全部點亮，所以需要用到回溯，一個一個選擇，還可以進行不同的組合
• 為了實現(xiàn)“選擇n個燈點亮”，我們可以設置小時數(shù)組和分鐘數(shù)組，長度為10，不足10位補零，目的是使用這兩個數(shù)組來模擬小時和分鐘的亮燈情況（數(shù)組索引選中的值即為亮的燈）
• 具體實現(xiàn)可以參考下面的代碼，最后按照回溯+剪枝的方法將結果計算出并返回即可

八【時間頻度】

• 時間復雜度：$O(C_{10}^n)$，$n$為傳入的參數(shù)值
• 空間復雜度：$O(n)$，$n$為傳入的參數(shù)值

九【代碼實現(xiàn)】

1. Java語言版

class Solution {public List<String> readBinaryWatch(int turnedOn) {// 定義時間數(shù)組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);}}
}

2. Python語言版

class Solution:def readBinaryWatch(self, turnedOn: int) -> List[str]:# 定義時間數(shù)組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:returnif count == 0:res.append("%d:%02d" % (hour, minute))returnfor i in range(index, 10):backtrack(count - 1, i + 1, hour + hours[i], minute + minutes[i])backtrack(turnedOn, 0, 0, 0)# 返回結果return res

3. C語言版

/*** Note: The returned array must be malloced, assume caller calls free().*/#define MAX_RES_SIZE 256// 定義回調函數(shù)來遞歸查找所有可能的時間組合
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)
{// 定義時間數(shù)組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;
}

十【提交結果】

1. Java語言版
   

2. Python語言版
   

3. C語言版