672 灯泡开关 Ⅱ（思维题）

骑猪看日落 2022-09-02 11:58 141阅读 0赞

**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\].  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/bulb-switcher-ii

**2. 思路分析：**

这道题目属于思维题，涉及到很多的分析过程与分析细节，不过感觉题目出的非常棒，非常巧妙。我们首先需要找一下规律，需要求解出从当前状态到任何一个状态的最少操作次数，可以发现当一个灯被摁两次的时候那么相当于是没摁，所以当presess > 4的时候由抽屉原理可以知道一定存在两个操作是一样的那么其中的两次相同的操作相当于是没摁，所以当presess > 4的时候我们都可以将每一次减去2次相同的操作，最终会变成presess < 4的情况，所以从初始状态到目标状态的操作次数一定小于4，所以我们可以考虑presses <= 3的情况，前面的开关1~3是至少摁2次的，且摁两次灯相当于是摁开关1,2,3中的一个，所以最终就可以转化为presess <= 2的情况：

*  摁开关1，2相当于是摁3
 *  摁开关1，3相当于是摁2
 *  摁开关2，3相当于是摁1

摁的次数小于等于2最多可以形成8个不同的状态，分别为相应开关的组合：0，1，2，3，4，14，24，34，接下来我们根据presess的次数分为以下几种情况

*  presess = 0，表示不摁的状态：0
 *  presess = 1，表示摁1次可能的状态：1,2,3,4
 *  presess = 2，表示摁2次可能的状态：0,1,2,3,14,24,34
 *  presess = 3，表示摁3次可能的状态：0,1,2,3,4,14,24,34

可以发现当presess >= 3的不管是奇数还是偶数都可以转化为presess = 3的情况，所以我们分情况讨论即可。上面讨论的是摁的次数，接下来考虑灯的数目，可以发现每6盏灯为一个循环，也即第k盏灯与第k + 6盏灯在摁的时候状态是一样的，所以只需要考虑前6盏灯的情况即可，我们可以将8种状态存储到一个二维数组中，判断当前的presess 的次数属于哪一种情况，并且n = min(n, 6)，也即最多考虑前6栈灯的状态，枚举每一种状态对应的二进制串的不同书记木即可。

**3. 代码如下：**

from typing import List
    
    
    class Solution:
        state = [
            # 6盏灯的8种状态
            [1, 1, 1, 1, 1, 1],  # 0 不摁
            [0, 0, 0, 0, 0, 0],  # 1, 按开关1一次
            [1, 0, 1, 0, 1, 0],  # 2, 按开关2一次
            [0, 1, 0, 1, 0, 1],  # 3, 按开关3一次
            [0, 1, 1, 0, 1, 1],  # 4, 按开关4一次
            [1, 0, 0, 1, 0, 0],  # 14 4的状态上摁1
            [0, 0, 1, 1, 1, 0],  # 24 4的状态上摁2
            [1, 1, 0, 0, 0, 1]   # 34 4的状态上摁3
        ]
        
        # 判断前n盏灯的所有状态, 我们计算不同的二进制串的个数即可
        def work(self, n: int, ops: List[int]):
            s = set()
            for i in range(len(ops)):
                t = 0
                for j in range(n):
                    t = t * 2 + self.state[ops[i]][j]
                s.add(t)
            return len(s)
    
        def flipLights(self, n: int, presses: int) -> int:
            # 首先考虑从初始状态到目标状态最多的的操作次数, 可以发现n最多为6, presess最多为4
            n = min(n, 6)
            # 将摁的次数转化为对应的四种摁法可能的所有状态
            if presses == 0:
                return self.work(n, [0])
            elif presses == 1:
                return self.work(n, [1, 2, 3, 4])
            elif presses == 2:
                return self.work(n, [0, 1, 2, 3, 5, 6, 7])
            else:
                return self.work(n, [0, 1, 2, 3, 4, 5, 6, 7])