【2022-09-15每日一题】672. 灯泡开关 Ⅱ
2022-09-15
2分钟阅读时长
2022-09-15每日一题：672. 灯泡开关 Ⅱ
- 难度：Medium
- 标签：位运算 、 深度优先搜索 、 广度优先搜索 、 数学
房间中有 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 <= 10000 <= presses <= 1000
方法一：归纳找规律
详细思路过程见官方题解，这里只做个人刷题记录，方便后续查询阅读
推荐题解
func flipLights(n int, presses int) int {
if presses == 0 {
return 1
}
if n == 1 {
return 2
} else if n == 2 {
if presses == 1 {
return 3
}
return 4
}
// n >= 3
if presses == 1 {
return 4
} else if presses == 2 {
return 7
}
return 8
}
复杂度分析
- 时间复杂度：O(1)。
- 空间复杂度：O(1)。
方法二：官方降低搜索空间
func flipLights(n int, presses int) int {
seen := map[int]struct{}{}
for i := 0; i < 1<<4; i++ {
pressArr, sum := [4]int{}, 0
for j := 0; j < 4; j++ {
pressArr[j] = i >> j & 1
sum += pressArr[j]
}
if sum%2 == presses%2 && sum <= presses {
// 编号为 6k+1，受按钮 1,3,41,3,4 影响；
status := pressArr[0] ^ pressArr[2] ^ pressArr[3]
if n >= 2 {
// 编号为 6k+2, 6k+6，受按钮 1,21,2 影响；
status |= (pressArr[0] ^ pressArr[1]) << 1
}
if n >= 3 {
// 编号为 6k+3, 6k+5，受按钮 1,31,3 影响；
status |= (pressArr[0] ^ pressArr[2]) << 2
}
if n >= 4 {
// 编号为 6k+4，受按钮 1,2,41,2,4 影响。
status |= (pressArr[0] ^ pressArr[1] ^ pressArr[3]) << 3
}
seen[status] = struct{}{}
}
}
return len(seen)
}