class Solution {
public:
int flipLights(int n, int presses) {
}
};
672. 灯泡开关 Ⅱ
现有一个房间，墙上挂有 n 只已经打开的灯泡和 4 个按钮。在进行了 m 次未知操作后，你需要返回这 n 只灯泡可能有多少种不同的状态。
假设这 n 只灯泡被编号为 [1, 2, 3 ..., n]，这 4 个按钮的功能如下：
3k+1 的灯泡的状态反转（k = 0, 1, 2, ...)示例 1:
输入: n = 1, m = 1. 输出: 2 说明: 状态为: [开], [关]
示例 2:
输入: n = 2, m = 1. 输出: 3 说明: 状态为: [开, 关], [关, 开], [关, 关]
示例 3:
输入: n = 3, m = 1. 输出: 4 说明: 状态为: [关, 开, 关], [开, 关, 开], [关, 关, 关], [关, 开, 开].
注意： n 和 m 都属于 [0, 1000].
相似题目
原站题解
java 解法, 执行用时: 0 ms, 内存消耗: 38.3 MB, 提交时间: 2022-12-10 13:31:52
class Solution {
public int flipLights(int n, int presses) {
//不按开关
if (presses == 0) {
return 1;
}
//特殊情况处理
if (n == 1) {
return 2;
} else if (n == 2) {
//特殊情况
return presses == 1 ? 3 : 4;
} else {
//n >= 3
return presses == 1 ? 4 : presses == 2 ? 7 : 8;
}
}
}
golang 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2022-12-10 13:31:12
func flipLights(n, presses int) int {
seen := map[int]struct{}{}
for i := 0; i < 1<<4; i++ {
pressArr := [4]int{}
sum := 0
for j := 0; j < 4; j++ {
pressArr[j] = i >> j & 1
sum += pressArr[j]
}
if sum%2 == presses%2 && sum <= presses {
status := pressArr[0] ^ pressArr[2] ^ pressArr[3]
if n >= 2 {
status |= (pressArr[0] ^ pressArr[1]) << 1
}
if n >= 3 {
status |= (pressArr[0] ^ pressArr[2]) << 2
}
if n >= 4 {
status |= (pressArr[0] ^ pressArr[1] ^ pressArr[3]) << 3
}
seen[status] = struct{}{}
}
}
return len(seen)
}
javascript 解法, 执行用时: 60 ms, 内存消耗: 41 MB, 提交时间: 2022-12-10 13:30:58
/**
* @param {number} n
* @param {number} presses
* @return {number}
*/
var flipLights = function(n, presses) {
const seen = new Set();
for (let i = 0; i < 1 << 4; i++) {
const pressArr = new Array(4).fill(0);
for (let j = 0; j < 4; j++) {
pressArr[j] = (i >> j) & 1;
}
const sum = _.sum(pressArr);
if (sum % 2 === presses % 2 && sum <= presses) {
let status = pressArr[0] ^ pressArr[2] ^ pressArr[3];
if (n >= 2) {
status |= (pressArr[0] ^ pressArr[1]) << 1;
}
if (n >= 3) {
status |= (pressArr[0] ^ pressArr[2]) << 2;
}
if (n >= 4) {
status |= (pressArr[0] ^ pressArr[1] ^ pressArr[3]) << 3;
}
seen.add(status);
}
}
return seen.size;
};
java 解法, 执行用时: 2 ms, 内存消耗: 38.8 MB, 提交时间: 2022-12-10 13:30:42
class Solution {
public int flipLights(int n, int presses) {
Set<Integer> seen = new HashSet<Integer>();
for (int i = 0; i < 1 << 4; i++) {
int[] pressArr = new int[4];
for (int j = 0; j < 4; j++) {
pressArr[j] = (i >> j) & 1;
}
int sum = Arrays.stream(pressArr).sum();
if (sum % 2 == presses % 2 && sum <= presses) {
int status = pressArr[0] ^ pressArr[2] ^ pressArr[3];
if (n >= 2) {
status |= (pressArr[0] ^ pressArr[1]) << 1;
}
if (n >= 3) {
status |= (pressArr[0] ^ pressArr[2]) << 2;
}
if (n >= 4) {
status |= (pressArr[0] ^ pressArr[1] ^ pressArr[3]) << 3;
}
seen.add(status);
}
}
return seen.size();
}
}
python3 解法, 执行用时: 36 ms, 内存消耗: 14.9 MB, 提交时间: 2022-12-10 13:30:29
class Solution:
def flipLights(self, n: int, presses: int) -> int:
seen = set()
for i in range(2**4):
pressArr = [(i >> j) & 1 for j in range(4)]
if sum(pressArr) % 2 == presses % 2 and sum(pressArr) <= presses:
status = pressArr[0] ^ pressArr[2] ^ pressArr[3]
if n >= 2:
status |= (pressArr[0] ^ pressArr[1]) << 1
if n >= 3:
status |= (pressArr[0] ^ pressArr[2]) << 2
if n >= 4:
status |= (pressArr[0] ^ pressArr[1] ^ pressArr[3]) << 3
seen.add(status)
return len(seen)