灯泡开关 Ⅱ : 分情况讨论

题目描述

这是 LeetCode 上的 672. 灯泡开关 Ⅱ ，难度为 中等。

Tag : 「脑筋急转弯」、「找规律」

房间中有 n 只已经打开的灯泡，编号从 1 到 n 。墙上挂着 4 个开关 。

这 4 个开关各自都具有不同的功能，其中：

• 
  
• 开关 1 ：反转当前所有灯的状态（即开变为关，关变为开）
  
• 开关 2 ：反转编号为偶数的灯的状态（即 2, 4, ...）
  
• 开关 3 ：反转编号为奇数的灯的状态（即 1, 3, ...）
  
• 开关 4 ：反转编号为 j = 3k + 1 的灯的状态，其中 k = 0, 1, 2, ...（即 1, 4, 7, 10, ...）
  

你必须 恰好 按压开关 presses 次。每次按压，你都需要从 4 个开关中选出一个来执行按压操作。

给你两个整数 n 和 presses，执行完所有按压之后，返回 不同可能状态 的数量。

示例 1：

输入：n = 1, presses = 1


输出：2


解释：状态可以是：

- 按压开关 1 ，[关]

- 按压开关 2 ，[开]

示例 2：

输入：n = 2, presses = 1


输出：3


解释：状态可以是：

- 按压开关 1 ，[关, 关]

- 按压开关 2 ，[开, 关]

- 按压开关 3 ，[关, 开]

示例 3：

输入：n = 3, presses = 1


输出：4


解释：状态可以是：

- 按压开关 1 ，[关, 关, 关]

- 按压开关 2 ，[关, 开, 关]

- 按压开关 3 ，[开, 关, 开]

- 按压开关 4 ，[关, 开, 开]

提示：

• 
  
• 1<=n<=10001 <= n <= 10001<=n<=1000
  
• 0<=presses<=10000 <= presses <= 10000<=presses<=1000
  

分情况讨论

记灯泡数量为 nnn（至少为 111），翻转次数为 kkk（至少为 000），使用 1 代表灯亮，使用 0 代表灯灭。

我们根据 nnn 和 kkk 的数值分情况讨论：

• 
  
• 当 k=0k = 0k=0 时，无论 nnn 为何值，都只有起始（全 1）一种状态；
  
• 当 k>0k > 0k>0 时，根据 nnn 进一步分情况讨论：
  
  • 
    
  • 当 n=1n = 1n=1 时，若 kkk 为满足「k>0k > 0k>0」的最小值 111 时，能够取满「1/0」两种情况，而其余更大 kkk 值情况能够使用操作无效化（不影响灯的状态）；
    
  • 当 n=2n = 2n=2 时，若 k=1k = 1k=1，能够取得「11/10/01」三种状态，当 k=2k = 2k=2 时，能够取满「11/10/01/00」四种状态，其余更大 kkk 可以通过前 k−1k - 1k−1 步归结到任一状态，再通过最后一次的操作 111 归结到任意状态；
    
  • 当 n=3n = 3n=3 时，若 k=1k = 1k=1 时，对应 444 种操作可取得 444 种方案；当 k=2k = 2k=2 时，可取得 777 种状态；而当 k=3k = 3k=3 时可取满 23=82^3 = 823=8 种状态，更大的 kkk 值可通过同样的方式归结到取满的 888 种状态。
    
  • 当 n>3n > 3n>3 时，根据四类操作可知，灯泡每 666 组一循环（对应序列 k + 1、2k + 2、2k + 1 和 3k + 1），即只需考虑 n<=6n <= 6n<=6 的情况，而 n=4n = 4n=4、n=5n = 5n=5 和 n=6n = 6n=6 时，后引入的灯泡状态均不会产生新的组合（即新引入的灯泡状态由前三个灯泡的状态所唯一确定），因此均可归纳到 n=3n = 3n=3 的情况。
    
  
  
  

Java 代码：

class Solution {

    public int flipLights(int n, int k) {

        if (k == 0) return 1;

        if (n == 1) return 2;

        else if (n == 2) return k == 1 ? 3 : 4;

        else return k == 1 ? 4 : k == 2 ? 7 : 8;

    }

}

TypeScript 代码：

function flipLights(n: number, k: number): number {

    if (k == 0) return 1

    if (n == 1) return 2

    else if (n == 2) return k == 1 ? 3 : 4;

    else return k == 1 ? 4 : k == 2 ? 7 : 8;

};

• 
  
• 时间复杂度：O(1)O(1)O(1)
  
• 空间复杂度：O(1)O(1)O(1)
  

最后

这是我们「刷穿 LeetCode」系列文章的第 No.672 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。