672. 灯泡开关 Ⅱ : 分情况讨论

​

题目描述

这是 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​

​​ 代表灯亮，使用 ​

​0​

​ 代表灯灭。

我们根据 和

• 当时，无论为何值，都只有起始（全​​

  ​1​

  ​）一种状态；
• 当时，根据进一步分情况讨论：

• 当时，若为满足「」的最小值时，能够取满「​​

  ​1​

  ​​/​

  ​0​

  ​​」两种情况，而其余更大
• 当时，若，能够取得「​​

  ​11​

  ​​/​

  ​10​

  ​​/​

  ​01​

  ​​」三种状态，当时，能够取满「​​

  ​11​

  ​​/​

  ​10​

  ​​/​

  ​01​

  ​​/​

  ​00​

  ​​」四种状态，其余更大可以通过前步归结到任一状态，再通过最后一次的操作
• 当时，若时，对应种操作可取得种方案；当时，可取得种状态；而当时可取满种状态，更大的值可通过同样的方式归结到取满的
• 当时，根据四类操作可知，灯泡每组一循环（对应序列​​

  ​k + 1​

  ​​、​

  ​2k + 2​

  ​​、​

  ​2k + 1​

  ​​ 和​

  ​3k + 1​

  ​​），即只需考虑的情况，而、和时，后引入的灯泡状态均不会产生新的组合（即新引入的灯泡状态由前三个灯泡的状态所唯一确定），因此均可归纳到

Java 代码：

class Solution {
    public int flipLights(int n, int {
        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;
};      

• 时间复杂度：
• 空间复杂度：

最后

这是我们「刷穿 LeetCode」系列文章的第 ​

​No.672​

​ 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

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

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