中等

问题描述

房间中有 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

枚举

两次相同的操作相当于一次空操作，那么当 $presses > 2$ 时，可以简化到 $3$ 或 $4$ 次的情况。通过观察可以发现，每 $6$ 盏灯可以构成一组，这 $6$ 盏灯可以通过观察前 $3$ 栈灯来决定状态，$3$ 栈灯的最多有 $2^3$ 种状态。

以 $presses$ 和 $n$ 进行枚举：

• 当 $presses$ = 0$ 时：
  • 无论有多少盏灯，都只有 $1$ 种状态
• 当 $presses$ = 1$ 时：
  • 当 $n = 1$，存在 $2$ 种状态:0|1
  • 当 $n = 2$，存在 $3$ 种状态: 00|10|11
  • 当 $n > 2$，存在 $4$ 种状态: 000|010|101|011
• 当 $presses$ = 2$ 时：
  • 当 $n = 1$，存在 $2$ 种状态: 0|1
  • 当 $n = 2$，存在 $4$ 种状态: 00|01|10|11
  • 当 $n > 2$，存在 $7$ 种状态: 001|010|011|100|101|110|111
• 当 $presses$ > 2$ 时：
  • 当 $n = 1$，存在 $2$ 种状态: 0|1
  • 当 $n = 2$，存在 $4$ 种状态: 00|01|10|11
  • 当 $n > 2$，存在 $8$ 种状态: 000|001|010|011|100|101|110|111

/**
 * @param {number} n
 * @param {number} presses
 * @return {number}
 */
var flipLights = function (n, presses) {
  if (presses === 0) return 1
  if (n === 1) {
    return 2
  } else if (n === 2) {
    return presses === 1 ? 3 : 4
  } else {
    if (presses === 1) return 4
    return presses === 2 ? 7 : 8
  }
}

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