来自中专的天才少女，排名全球 12
这里贴一下阿里巴巴预选赛的七道题（题目来源：橙柿互动）：
回归主线。
数学题不会是吧，那来一道超简单的算法题。
题目描述
平台：LeetCode
题号：672
房间中有 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 ，[关, 开, 开]
提示：
分情况讨论
记灯泡数量为 n（至少为 1），翻转次数为 k（至少为 0），使用 1 代表灯亮，使用 0 代表灯灭。
我们根据 n 和 k 的数值分情况讨论：
- 当
时，无论
为何值，都只有起始（全 1）一种状态；
- 当
时，根据
进一步分情况讨论：
- 当
时，若
为满足「
」的最小值
时，能够取满「1/0」两种情况，而其余更大
值情况能够使用操作无效化（不影响灯的状态）；
- 当
时，若
，能够取得「00/10/01」三种状态，当
时，能够取满「11/10/01/00」四种状态，其余更大
可以通过前
步归结到任一状态，再通过最后一次的操作
归结到任意状态；
- 当
时，若
时，对应
种操作可取得
种方案；当
时，可取得
种状态；而当
时可取满
种状态，更大的
值可通过同样的方式归结到取满的
种状态。
- 当
时，根据四类操作可知，灯泡每
组一循环（对应序列 k + 1、2k + 2、2k + 1 和 3k + 1），即只需考虑
的情况，而
、
和
时，后引入的灯泡状态均不会产生新的组合（即新引入的灯泡状态由前三个灯泡的状态所唯一确定），因此均可归纳到
的情况。
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;
}
}
C++ 代码：
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;
}
};
Python 3 代码：
class Solution:
def flipLights(self, n: int, k: int) -> int:
if k == 0:
return 1
if n == 1:
return 2
elif n == 2:
return 3 if k == 1 else 4
else:
return 4 if k == 1 else 7 if k == 2 else 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;
};
- 时间复杂度：
- 空间复杂度：