宫水三叶的刷题日记

V1

2022/09/15阅读:22主题:前端之巅同款

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

题目描述

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

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

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

4 个开关各自都具有不同的功能,其中:

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

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

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

示例 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 + 12k + 22k + 13k + 1),即只需考虑 的情况,而 时,后引入的灯泡状态均不会产生新的组合(即新引入的灯泡状态由前三个灯泡的状态所唯一确定),因此均可归纳到 的情况。

Java 代码:

class Solution {
    public int flipLights(int n, int k) {
        if (k == 0return 1;
        if (n == 1return 2;
        else if (n == 2return k == 1 ? 3 : 4;
        else return k == 1 ? 4 : k == 2 ? 7 : 8;
    }
}

TypeScript 代码:

function flipLights(n: number, k: number): number {
    if (k == 0return 1
    if (n == 1return 2
    else if (n == 2return k == 1 ? 3 : 4;
    else return k == 1 ? 4 : k == 2 ? 7 : 8;
};
  • 时间复杂度:
  • 空间复杂度:

最后

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

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

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。

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

更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉

分类:

后端

标签:

后端

作者介绍

宫水三叶的刷题日记
V1