跳转至

LeetCode: 672. 灯泡开关 Ⅱ

1、题目描述

现有一个房间,墙上挂有 n 只已经打开的灯泡和 4 个按钮。在进行了 m 次未知操作后,你需要返回这 n 只灯泡可能有多少种不同的状态。

假设这 n 只灯泡被编号为 [1, 2, 3 ..., n],这 4 个按钮的功能如下:

  • 将所有灯泡的状态反转(即开变为关,关变为开)
  • 将编号为偶数的灯泡的状态反转
  • 将编号为奇数的灯泡的状态反转
  • 将编号为 3k+1 的灯泡的状态反转(k = 0, 1, 2, ...)

示例 1:

输入: n = 1, m = 1.
输出: 2
说明: 状态为: [开], [关]

示例 2:

输入: n = 2, m = 1.
输出: 3
说明: 状态为: [开, 关], [关, 开], [关, 关]

示例 3:

输入: n = 3, m = 1.
输出: 4
说明: 状态为: [关, 开, 关], [开, 关, 开], [关, 关, 关], [关, 开, 开].

注意: n 和 m 都属于 [0, 1000].

2、解题思路

  • 首先上面的4个条件分别记作a,b,c,d

  • 分析下几个灯泡能够覆盖上面的每个条件的所有情况

  • a:1

    • 全灭和全亮两种状态,只需要一个灯泡就能覆盖
    • b:2
    • 偶数灯泡反转,只需要两个灯泡就能覆盖全部情况
    • c:2
    • 奇数灯泡反转,只需要两个灯泡就能覆盖全部情况
    • d:3
    • 3k+1,需要3个灯泡才能覆盖全部情况

因此,灯泡值用(1,1,1)来表示,1表示亮,0表示灭

  • 当m=0,可能出现的灯泡组合为:

  • (1,1,1) 只能出现一种

  • 当m=1,可能出现的灯泡组合为:

  • (0,0,0),(1,0,1),(0,1,0),(0,1,1)

然后分别不同灯泡数量对应的结果组合数量

如果是一个灯泡,第一位出现0,1,表示可能的组合是2中

如果是两个灯泡,起那两位出现的组合为:(0,0),(1,0),(0,1),是3种

如果是3个灯泡,则是4种

  • 如果m=2,可能出现的灯泡组合为:

  • (0,0,0),(0,0,1),(0,1,0),(1,0,0),(1,0,1),(1,1,0),(1,1,1)

依次类推,一个,两个,三个灯泡分别对应2,4,7

  • 当m=3,3位数的8中组合都会出现,因此一个,两个,三个灯泡分别对应2,4,8

class Solution:
    def flipLights(self, n: int, m: int) -> int:
        if n == 0:
            return 1
        n = min(n, 3)

        if m == 0:
            return 1
        if m == 1:
            return [0, 2, 3, 4][n]
        if m == 2:
            return [0, 2, 4, 7][n]
        return [0, 2, 4, 8][n]