关于后端: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 <= n <= 1000$
• $0 <= presses <= 1000$

分状况探讨

记灯泡数量为 $n$（至多为 $1$），翻转次数为 $k$（至多为 $0$），应用 1 代表灯亮，应用 0 代表灯灭。

咱们依据 $n$ 和 $k$ 的数值分状况探讨：

• 当 $k = 0$ 时，无论 $n$ 为何值，都只有起始（全 1）一种状态；

• 当 $k > 0$ 时，依据 $n$ 进一步分状况探讨：

  • 当 $n = 1$ 时，若 $k$ 为满足「$k > 0$」的最小值 $1$ 时，可能取满「1/0」两种状况，而其余更大 $k$ 值状况可能应用操作有效化（不影响灯的状态）；
  • 当 $n = 2$ 时，若 $k = 1$，可能获得「11/10/01」三种状态，当 $k = 2$ 时，可能取满「11/10/01/00」四种状态，其余更大 $k$ 能够通过前 $k – 1$ 步归结到任一状态，再通过最初一次的操作 $1$ 归结到任意状态；
  • 当 $n = 3$ 时，若 $k = 1$ 时，对应 $4$ 种操作可获得 $4$ 种计划；当 $k = 2$ 时，可获得 $7$ 种状态；而当 $k = 3$ 时可取满 $2^3 = 8$ 种状态，更大的 $k$ 值可通过同样的形式归结到取满的 $8$ 种状态。
  • 当 $n > 3$ 时，依据四类操作可知，灯泡每 $6$ 组一循环（对应序列 k + 1、2k + 2、2k + 1 和 3k + 1），即只需思考 $n <= 6$ 的状况，而 $n = 4$、$n = 5$ 和 $n = 6$ 时，后引入的灯泡状态均不会产生新的组合（即新引入的灯泡状态由前三个灯泡的状态所惟一确定），因而均可归纳到 $n = 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)$

最初

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

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

为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。

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

更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉

本文由 mdnice 多平台公布