Python|找规律解决灯泡开关Ⅱ

本文首发于微信公众号："算法与编程之美"，欢迎关注，及时了解更多此系列文章。

问题描述

现有一个房间，墙上挂有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

说明: 状态为: [开, 关], [关, 开], [关, 关]

解决方案

这道题看着挺难，但不能按照题中的要求直接暴力的思考。题中重点就是4个按钮的功能，所以首先根据4种按钮的功能可以发现，所有功能执行2次与不执行效果相同，因此可以将所有功能执行情况分为执行0次与执行1次。其次，按钮执行的前后顺序变换对最终灯泡情况没有影响。

首先观察开关次数对开关方式变化：

m=0时，情况不变，只有1种状态

m=1时，根据示例思考一下可以知道，当n>=3时状态恒为4

m=2时，数字1-4代表按钮的4种功能，0代表返回原状态：

1+1=0 1+2=3 1+3=2 1+4=？5？

2+2=0 2+3=1 2+4=？6？

3+3=0 3+4=？7？

4+4=0

共7种情况。

m=3时，这时可以认为在m=2情况下再次进行一步，由于顺序可调换，显然m=3的情况相比m=2的情况又多了一种，因此为8种。

m>3时，由于前3个灯可以确定后面其余部分，因此最多状态为8中。也就是可以把m>3和m=3归为一类。

再分析n对状态的影响：

实际上，前3个灯唯一地确定了序列的其余部分，因此n>3的情况与n=3的情况相同。

再将n=2以及n=1的情况列举一下，

最后把m和n对状态的影响结合起来。

题目代码：

class Solution:

    def flipLights(self, n: int, m: int) -> int:

        if m == 0:

            return 1

        if n == 1:

            return 2

        elif n == 2:

            if m == 1:

                return 3

            return 4

        elif n >= 3:

            if m == 1:

                return 4

            elif m == 2:

                return 7

            return 8

结语

这道题看着感觉很难，似乎最后有很多种状态，特别是随着灯泡数量n的增大，最后状态数量可能很多。但仔细观察题中给出的4种按钮功能，每一次改变都是某些部分一起改变，并不会出现一大堆灯泡里面只有一个灯泡发生改变。所以只要仔细观察，确定规律就很好解决。