Day 21：401. Binary Watch

今日题目

题目连结：401. Binary Watch
题目主题：Backtracking, Bit Manipulation

简单说说 Backtracking

Backtracking 有点像是 Enumeration 的进化，在 Enumeration 我们列出了所有可能的路出来，而 Backtracking 在列出所有可能性的过程已经发现不符合条件的路出现，就会往回走直接往新的路再去走。

找一个范例来说明，假设 nums = [5, 3, 2, 4, 1]，想要在这个 nums 中找出所有三个数加起来小於 8 的组合找出来，实际上 Backtracking 想像起来如下图：

简单来说，用 Enumeration 的方式先想像，但是在算的过程中，如果走到一半已经发现不可能符合条件了，就会直接往下一条路走了，这张图红色叉就代表这条路已经不用走下去了，红色叉开始以下没走到的都是提升效能的部份，最终可以找到[3, 2, 1] 及 [2, 4, 1] 这两种可能。

题目解说

建议可以看看LeetCode原本的题目说明，这边是用我的方式说明题目，参考就好。

下图是Leetcode的范例图，可以看到这是一个 Binary Watch，这张图的范例显示的时间是 4:51。

这个 Binary Watch 分成上面的 4 个数字为小时范围是是 0 - 11，下面的 6 个数字为分钟范围是 0 - 59，如果今天是 11:20 分，总共会亮 5 个灯，分别是小时的 8, 2, 1及分钟的16 ,4 这五个灯。

题目会给你一个 turnedOn 为亮灯的数量，目的是要将所有可能性列出来，如果 turnedOn 给的是 5，就要把所有 5 个灯的可能性都列出来，最终回传一个字串阵列。

另外要注意的是，小时若是个位数不用显示前面的 0：
Ex. 不能显示 "01:00"，应该显示 "1:00"

若是分钟的话，个位数需要显示前面的 0：
Ex. 不能显示 "10:2"，应该显示"10:02"

约束：

• 0 <= turnedOn <= 10

范例1

输入: turnedOn = 1
输出: ["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]
解说: 总共只有 10 个灯，因此就每个灯轮流亮一次即可得到这个答案。

范例2

输入: turnedOn = 9
输出: []
解说: 总共有 10 个灯，但不可能 9 个灯同时亮，举例来说若小时的四个灯全亮，数字总共已经到了 15 已经超过范围 0 - 11 了，因此在这个范例最後回传的是空阵列。

建议到这边先停下来，尝试自己解解看，若没有想法可再继续走下去。

解题的想像

文字描述

1. 宣告 hours 及 minutes 纪录所有会亮的数字。
2. 写两个递回方法，分别为取得小时数及分钟数。
3. 取得小时递回方法：
   • 若有符合条件的小时出现，呼叫取得分钟的递回方法。
   • 若出现大於 11 以上的小时数，继续往下个可能性确认。
   • 若超过指定亮灯数，继续往下个可能性确认。
   • 跑一个回圈，用一个 Stack 来纪录，目前亮灯的小时数组合。
   • 最终回传目前符合条件的字串列表。
4. 取得分钟递回方法：
   • 若有符合条件的分钟出现，将目前小时数及分钟数组合成字串，放进字串列表。
   • 若出现大於 59 以上的分钟数，继续往下个可能性确认。
   • 若超过指定亮灯数，继续往下个可能性确认。
   • 跑一个回圈，用一个 Stack 来纪录，目前亮灯的分钟数组合。
   • 最终回传目前符合条件的字串列表。
5. 若指定亮灯数是 0 回传 ['0:00'] 一种可能，若指定亮灯树有1以上，从取得小时数的递回方法开始走。

图解过程

范例：turnedOn = 8

这次用的范例目标是要亮 8 个灯，下图是列出的是运作的过程：

上图中可以看到，实际运作过程会先从 hours 开始检查，其中 hours 只有亮 1 个灯及 2 个灯的状况有个箭头指到一个 X 是因为，如果小时只有亮 1 或 2 个灯，要符合 8 个灯的条件，代表 minutes 需要亮到 7 或 6 个灯，但实际上分钟的灯也只有 6 个， 6 个都亮会超过分钟最大值59了，因此直接在这边结束，没有去查到分钟。

另外比较特别的是 [8, 4] 这个组合，没有箭头直接看到 X 的原因是，8 + 4 已经等於 12 了，已经超过最大小时数，因此在这边直接结束不用继续往下去查看。

最後是 [8, 2, 1] 及 [4, 2, 1] 这两组小时数，都是亮 3 个灯，代表分钟要亮 5 个灯，两组小时都会找到同样的分钟组合，最後列出的结果是 ["11:59", "11:55", "11:47", "11:31", "7:59", "7:55", "7:47", "7:31"]。

若因为没想法而走到这边，建议看完想像以後再给自己一次机会试一次。

程序码撰写

class Solution:
    # 先准备好小时及分钟的所有灯
    def __init__(self):
        self.hours = [8, 4, 2, 1]
        self.minutes = [32, 16, 8, 4, 2, 1]
        
    # 取得可能的小时数
    def getHours(self, timeList, turnedOn, startIndex, hourStack = []):
        # 若超过 11 小时以上结束
        if sum(hourStack) >= 12: return timeList
        # 若亮灯树符合条件，取得目前小时数的所有分钟数，并且放进最终要回传的字串列表中
        if len(hourStack) <= turnedOn:
            timeList = self.getMins(timeList, sum(hourStack), turnedOn-len(hourStack), 0)
        # 若已经等於指定亮灯数结束
        if len(hourStack) == turnedOn: return timeList
        # 继续组合可能的小时数
        for hourIndex in range(startIndex, len(self.hours)):
            hourStack.append(self.hours[hourIndex])
            timeList = self.getHours(timeList, turnedOn, hourIndex+1, hourStack)
            hourStack.pop()
        return timeList
            
    # 取得可能的分钟数
    def getMins(self, timeList, hour, turnedOn, startIndex, minStack = []):
        # 若亮灯数超过分钟总灯数结束
        if turnedOn >= len(self.minutes): return timeList
        # 若超过 59 分钟以上结束
        if sum(minStack) >= 60: return timeList
        # 若亮灯数符合条件，取得目前小时数的所有分钟数
        if len(minStack) == turnedOn:
            minute = sum(minStack)
            minStr = f"0{minute}" if minute < 10 else minute
            timeList.append(f"{hour}:{minStr}")
            return timeList
        # 继续组合可能的分钟数
        for minIndex in range(startIndex, len(self.minutes)):
            minStack.append(self.minutes[minIndex])
            timeList = self.getMins(timeList, hour, turnedOn, minIndex+1, minStack)
            minStack.pop()
        return timeList
    
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        # 若没有任何灯亮直接回传 0:00 一种可能，若有亮灯开始走递回方法
        return ['0:00'] if turnedOn == 0 else self.getHours([], turnedOn, 0)

希望您今天能了解到...

1. Backtracking 的基本概念
2. 401. Binary Watch 的解题方法

若内容有什麽问题或建议欢迎一起交流：）
感谢您今天愿意花时间看完这篇文章~~~~

Next：1863. Sum of All Subset XOR Totals