递归，迭代（定长列表 + 位集），3 解法求解《672. 灯泡开关 Ⅱ》
例题
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 ，[关, 开, 开]
提示：
1 <= n <= 1000
0 <= presses <= 1000
答案
递归
var flipLights = function(n, presses) { // 模拟
const s = new Array(n).fill(1), h = new Set, m = new Set, d = (s, step) => {
if (step === presses) return h.add(s.join(''))
if (m.has(step + s.join(''))) return
else m.add(step + s.join(''))
d(s.map(v => v ^ 1), step + 1)
d(s.map((v, i) => (i & 1) === 0 ? v ^ 1 : v), step + 1)
d(s.map((v, i) => (i & 1) === 1 ? v ^ 1 : v), step + 1)
d(s.map((v, i) => i % 3 === 0 ? v ^ 1 : v), step + 1)
}
d(s, 0)
return h.size
};var flipLights = function(n, presses) { // 掩码
const h = new Set, m = new Set, add = (mask, cb) => {
for (let i = 0; i < Math.min(n, 4); i++) {
if (cb(i)) mask ^= (1 << i)
}
return mask
}, d = (mask, step) => {
if (m.has(step + ',' + mask)) return
else m.add(step + ',' + mask)
if (step === presses) return h.add(mask)
d(add(mask, _ => true), step + 1)
d(add(mask, i => (i & 1) === 0), step + 1)
d(add(mask, i => (i & 1) === 1), step + 1)
d(add(mask, i => i % 3 === 0), step + 1)
}
d(0, 0)
return h.size
};var flipLights = function(n, presses) { // 掩码 + 仅递归 3 步
const h = new Set, add = (mask, cb) => {
for (let i = 0; i < Math.min(n, 4); i++) {
if (cb(i)) mask ^= (1 << i)
}
return mask
}, d = (mask, step) => {
if (step === Math.min(presses,3)) return h.add(mask)
d(add(mask, _ => true), step + 1)
d(add(mask, i => (i & 1) === 0), step + 1)
d(add(mask, i => (i & 1) === 1), step + 1)
d(add(mask, i => i % 3 === 0), step + 1)
}
d(0, 0)
return h.size
};定长列表
var flipLights = function(n, presses) {
const h = new Set
for (let i = 0; i < 1 << 4; i++) { // 枚举 4 种开关，16 种可能
const mask = new Uint8Array(4)
let sum = 0
for (let j = 0; j < 4; j++) { // 1 的位置：有效按动开关（开关按偶数次，相当于没按）
mask[j] = i >> j & 1
sum += mask[j]
}
if (sum % 2 === presses % 2 && sum <= presses) { // 对照图
state = mask[0] ^ mask[2] ^ mask[3]
if (n >= 2) state |= (mask[0] ^ mask[1]) << 1
if (n >= 3) state |= (mask[0] ^ mask[2]) << 2
if (n >= 4) state |= (mask[0] ^ mask[1] ^ mask[3]) << 3
h.add(state)
}
}
return h.size
};function flipLights(n: number, presses: number): number {
const h = new Set
for (let i = 0; i < 1 << 4; i++) {
const mask = new Uint8Array(4)
let sum = 0
for (let j = 0; j < 4; j++) {
mask[j] = i >> j & 1
sum += mask[j]
}
if ((sum & 1) === (presses & 1) && sum <= presses) {
let state = mask[0] ^ mask[2] ^ mask[3]
if (n >= 2) state |= (mask[0] ^ mask[1]) << 1
if (n >= 3) state |= (mask[0] ^ mask[2]) << 2
if (n >= 4) state |= (mask[0] ^ mask[1] ^ mask[3]) << 3
h.add(state)
}
}
return h.size
};class Solution {
function flipLights($n, $presses) {
$h = array();
for ($i = 0; $i < 1 << 4; $i++) {
$mask = array_fill(0, 4, 0);
for ($j = 0; $j < 4; $j++) {
$mask[$j] = $i >> $j & 1;
}
$sum = array_sum($mask);
if (($sum & 1) === ($presses & 1) && $sum <= $presses) {
$state = $mask[0] ^ $mask[2] ^ $mask[3];
if ($n >= 2) $state |= ($mask[0] ^ $mask[1]) << 1;
if ($n >= 3) $state |= ($mask[0] ^ $mask[2]) << 2;
if ($n >= 4) $state |= ($mask[0] ^ $mask[1] ^ $mask[3]) << 3;
$h[$state] = 1;
}
}
return count(array_keys($h));
}
}func flipLights(n int, presses int) int {
h := map[int]struct{}{}
for i := 0; i < 1 << 4; i++ {
mask, sum := make([]int, 4), 0
for j := 0; j < 4; j++ {
mask[j] = i >> j & 1
sum += mask[j]
}
if sum & 1 == presses & 1 && sum <= presses {
state := mask[0] ^ mask[2] ^ mask[3]
if n >= 2 {
state |= (mask[0] ^ mask[1]) << 1
}
if n >= 3 {
state |= (mask[0] ^ mask[2]) << 2
}
if n >= 4 {
state |= (mask[0] ^ mask[1] ^ mask[3]) << 3
}
h[state] = struct{}{}
}
}
return len(h)
}class Solution {
public int flipLights(int n, int presses) {
Set<Integer> h = new HashSet<Integer>();
for (int i = 0; i < 1 << 4; i++) {
int[] mask = new int[4];
for (int j = 0; j < 4; j++) {
mask[j] = i >> j & 1;
}
int sum = Arrays.stream(mask).sum();
if ((sum & 1) == (presses & 1) && sum <= presses) {
int state = mask[0] ^ mask[2] ^ mask[3];
if (n >= 2) state |= (mask[0] ^ mask[1]) << 1;
if (n >= 3) state |= (mask[0] ^ mask[2]) << 2;
if (n >= 4) state |= (mask[0] ^ mask[1] ^ mask[3]) << 3;
h.add(state);
}
}
return h.size();
}
}public class Solution {
public int FlipLights(int n, int presses) {
ISet<int> h = new HashSet<int>();
for (int i = 0; i < 1 << 4; i++) {
int[] mask = new int[4];
for (int j = 0; j < 4; j++) {
mask[j] = i >> j & 1;
}
int sum = mask.Sum();
if ((sum & 1) == (presses & 1) && sum <= presses) {
int state = mask[0] ^ mask[2] ^ mask[3];
if (n >= 2) state |= (mask[0] ^ mask[1]) << 1;
if (n >= 3) state |= (mask[0] ^ mask[2]) << 2;
if (n >= 4) state |= (mask[0] ^ mask[1] ^ mask[3]) << 3;
h.Add(state);
}
}
return h.Count;
}
}typedef struct {
int key;
UT_hash_handle hh;
} HashItem;
int flipLights(int n, int presses){
HashItem* h = NULL;
for (int i = 0; i < 1 << 4; i++) {
int* mask = malloc(sizeof(int) * 4);
int sum = 0;
for (int j = 0; j < 4; j++) {
mask[j] = i >> j & 1;
sum += mask[j];
}
if ((sum & 1) == (presses & 1) && sum <= presses) {
int state = mask[0] ^ mask[2] ^ mask[3];
if (n >= 2) state |= (mask[0] ^ mask[1]) << 1;
if (n >= 3) state |= (mask[0] ^ mask[2]) << 2;
if (n >= 4) state |= (mask[0] ^ mask[1] ^ mask[3]) << 3;
HashItem* pEntry = NULL;
HASH_FIND_INT(h, &state, pEntry);
if (pEntry == NULL) {
pEntry = malloc(sizeof(HashItem));
pEntry->key = state;
HASH_ADD_INT(h, key, pEntry);
}
}
}
int r = HASH_COUNT(h);
HashItem *cur = NULL, *tmp = NULL;
HASH_ITER(hh, h, cur, tmp) {
HASH_DEL(h, cur);
free(cur);
}
return r;
}class Solution {
public:
int flipLights(int n, int presses) {
unordered_set<int> h;
for (int i = 0; i < 1 << 4; i++) {
vector<int> mask(4, 0);
for (int j = 0; j < 4; j++) {
mask[j] = i >>j & 1;
}
int sum = accumulate(mask.begin(), mask.end(), 0);
if ((sum & 1) == (presses & 1) && sum <= presses) {
int state = mask[0] ^ mask[2] ^ mask[3];
if (n >= 2) state |= (mask[0] ^ mask[1]) << 1;
if (n >= 3) state |= (mask[0] ^ mask[2]) << 2;
if (n >= 4) state |= (mask[0] ^ mask[1] ^ mask[3]) << 3;
h.emplace(state);
}
}
return h.size();
}
};class Solution:
def flipLights(self, n: int, presses: int) -> int:
h = set()
for i in range(0, 1 << 4):
mask = [0] * 4
for j in range(0, 4):
mask[j] = i >> j & 1
total = sum(mask)
if total & 1 == presses & 1 and total <= presses:
state = mask[0] ^ mask[2] ^ mask[3]
if n >= 2: state |= (mask[0] ^ mask[1]) << 1
if n >= 3: state |= (mask[0] ^ mask[2]) << 2
if n >= 4: state |= (mask[0] ^ mask[1] ^ mask[3]) << 3
h.add(state)
return len(h)位集
var flipLights = function(n, presses) {
const h = new Set
for (let i = 0; i < 1 << 4; i++) { // 枚举 4 种开关，16 种可能
const mask = new Bit
for (let j = 0; j < 4; j++) { // 1 的位置：有效按动开关（开关按偶数次，相当于没按）
if (i >> j & 1) mask.add(j)
}
const sum = mask.count1()
if (sum % 2 === presses % 2 && sum <= presses) { // 对照图
state = mask.get(0) ^ mask.get(2) ^ mask.get(3)
if (n >= 2) state |= (mask.get(0) ^ mask.get(1)) << 1
if (n >= 3) state |= (mask.get(0) ^ mask.get(2)) << 2
if (n >= 4) state |= (mask.get(0) ^ mask.get(1) ^ mask.get(3)) << 3
h.add(state)
}
}
return h.size
};
class Bit {
constructor() {
this.b = 0
}
add(n) {
this.b |= 1 << n
}
get(n) {
return this.b >> n & 1
}
count1() {
let n = this.b, r = 0
while (n) {
n &= n - 1
r++
}
return r
}
}function flipLights(n: number, presses: number): number {
const h = new Set
for (let i = 0; i < 1 << 4; i++) {
const mask = new Bit
for (let j = 0; j < 4; j++) {
if (i >> j & 1) mask.add(j)
}
const sum = mask.count1()
if (sum % 2 === presses % 2 && sum <= presses) {
let state = mask.get(0) ^ mask.get(2) ^ mask.get(3)
if (n >= 2) state |= (mask.get(0) ^ mask.get(1)) << 1
if (n >= 3) state |= (mask.get(0) ^ mask.get(2)) << 2
if (n >= 4) state |= (mask.get(0) ^ mask.get(1) ^ mask.get(3)) << 3
h.add(state)
}
}
return h.size
};
class Bit {
#b = 0
add(n: number) {
this.#b |= 1 << n
}
get(n: number) {
return this.#b >> n & 1
}
count1() {
let n = this.#b, r = 0
while (n) {
r++
n &= n - 1
}
return r
}
}class Solution {
function flipLights($n, $presses) {
$h = array();
for ($i = 0; $i < 1 << 4; $i++) {
$mask = new Bit();
for ($j = 0; $j < 4; $j++) {
if ($i >> $j & 1) $mask->add($j);
}
$sum = $mask->count1();
if (($sum & 1) === ($presses & 1) && $sum <= $presses) {
$state = $mask->get(0) ^ $mask->get(2) ^ $mask->get(3);
if ($n >= 2) $state |= ($mask->get(0) ^ $mask->get(1)) << 1;
if ($n >= 3) $state |= ($mask->get(0) ^ $mask->get(2)) << 2;
if ($n >= 4) $state |= ($mask->get(0) ^ $mask->get(1) ^ $mask->get(3)) << 3;
$h[$state] = 1;
}
}
return count(array_keys($h));
}
}
class Bit {
private $b = 0;
public function add($n) {
$this->b |= 1 << $n;
}
public function get($n) {
return $this->b >> $n & 1;
}
public function count1() {
$n = $this->b;
$r = 0;
while ($n) {
$r++;
$n &= $n - 1;
}
return $r;
}
}func flipLights(n int, presses int) int {
h := map[int]struct{}{}
for i := 0; i < 1 << 4; i++ {
mask, sum := &Bit{}, 0
for j := 0; j < 4; j++ {
if i >> j & 1 == 1 {
mask.add(j)
sum++
}
}
if sum & 1 == presses & 1 && sum <= presses {
state := mask.get(0) ^ mask.get(2) ^ mask.get(3)
if n >= 2 {
state |= (mask.get(0) ^ mask.get(1)) << 1
}
if n >= 3 {
state |= (mask.get(0) ^ mask.get(2)) << 2
}
if n >= 4 {
state |= (mask.get(0) ^ mask.get(1) ^ mask.get(3)) << 3
}
h[state] = struct{}{}
}
}
return len(h)
}
type Bit struct {
b int
}
func (this *Bit) add(n int) {
this.b |= 1 << n
}
func (this *Bit) get(n int) int {
return this.b >> n & 1
}
func (this *Bit) count1() int {
n, r := this.b, 0
for n > 0 {
n &= n - 1
r++
}
return r
}class Solution {
public int flipLights(int n, int presses) {
Set<Integer> h = new HashSet<Integer>();
for (int i = 0; i < 1 << 4; i++) {
Bit mask = new Bit();
for (int j = 0; j < 4; j++) {
if ((i >> j & 1) == 1) mask.add(j);
}
int sum = mask.count1();
if ((sum & 1) == (presses & 1) && sum <= presses) {
int state = mask.get(0) ^ mask.get(2) ^ mask.get(3);
if (n >= 2) state |= (mask.get(0) ^ mask.get(1)) << 1;
if (n >= 3) state |= (mask.get(0) ^ mask.get(2)) << 2;
if (n >= 4) state |= (mask.get(0) ^ mask.get(1) ^ mask.get(3)) << 3;
h.add(state);
}
}
return h.size();
}
}
class Bit {
private int b = 0;
public void add(int n) {
b |= 1 << n;
}
public int get(int n) {
return b >> n & 1;
}
public int count1() {
int n = b, r = 0;
while (n > 0) {
n &= n - 1;
r++;
}
return r;
}
}public class Solution {
public int FlipLights(int n, int presses) {
ISet<int> h = new HashSet<int>();
for (int i = 0; i < 1 << 4; i++) {
Bit mask = new Bit();
for (int j = 0; j < 4; j++) {
if ((i >> j & 1) == 1) mask.Add(j);
}
int sum = mask.Count1();
if ((sum & 1) == (presses & 1) && sum <= presses) {
int state = mask.Get(0) ^ mask.Get(2) ^ mask.Get(3);
if (n >= 2) state |= (mask.Get(0) ^ mask.Get(1)) << 1;
if (n >= 3) state |= (mask.Get(0) ^ mask.Get(2)) << 2;
if (n >= 4) state |= (mask.Get(0) ^ mask.Get(1) ^ mask.Get(3)) << 3;
h.Add(state);
}
}
return h.Count;
}
}
public class Bit {
private int b = 0;
public void Add(int n) {
b |= 1 << n;
}
public int Get(int n) {
return b >> n & 1;
}
public int Count1() {
int n = b, r = 0;
while (n > 0) {
n &= n - 1;
r++;
}
return r;
}
}typedef struct {
int b;
} Bit;
void bitAdd(Bit* bit, int n) {
bit->b |= 1 << n;
}
int bitGet(Bit* bit, int n) {
return bit->b >> n & 1;
}
int bitCount1(Bit* bit) {
int n = bit->b, r = 0;
while (n) {
n &= (n - 1);
r++;
}
return r;
}
typedef struct {
int key;
UT_hash_handle hh;
} HashItem;
int flipLights(int n, int presses){
HashItem* h = NULL;
for (int i = 0; i < 1 << 4; i++) {
Bit* mask = malloc(sizeof(Bit));
mask->b = 0;
for (int j = 0; j < 4; j++) {
if (i >> j & 1) bitAdd(mask, j);
}
int sum = bitCount1(mask);
if ((sum & 1) == (presses & 1) && sum <= presses) {
int state = bitGet(mask, 0) ^ bitGet(mask, 2) ^ bitGet(mask, 3);
if (n >= 2) state |= (bitGet(mask, 0) ^ bitGet(mask, 1)) << 1;
if (n >= 3) state |= (bitGet(mask, 0) ^ bitGet(mask, 2)) << 2;
if (n >= 4) state |= (bitGet(mask, 0) ^ bitGet(mask, 1) ^ bitGet(mask, 3)) << 3;
HashItem* pEntry = NULL;
HASH_FIND_INT(h, &state, pEntry);
if (pEntry == NULL) {
pEntry = malloc(sizeof(HashItem));
pEntry->key = state;
HASH_ADD_INT(h, key, pEntry);
}
}
}
int r = HASH_COUNT(h);
HashItem *cur = NULL, *tmp = NULL;
HASH_ITER(hh, h, cur, tmp) {
HASH_DEL(h, cur);
free(cur);
}
return r;
}class Bit {
private: int b = 0;
public:
void add(int n) {
b |= 1 << n;
}
int get(int n) {
return b >> n & 1;
}
int count1() {
int n = b, r = 0;
while (n) {
n &= n - 1;
r++;
}
return r;
}
};
class Solution {
public:
int flipLights(int n, int presses) {
unordered_set<int> h;
for (int i = 0; i < 1 << 4; i++) {
Bit mask;
for (int j = 0; j < 4; j++) {
if (i >>j & 1) mask.add(j);
}
int sum = mask.count1();
if ((sum & 1) == (presses & 1) && sum <= presses) {
int state = mask.get(0) ^ mask.get(2) ^ mask.get(3);
if (n >= 2) state |= (mask.get(0) ^ mask.get(1)) << 1;
if (n >= 3) state |= (mask.get(0) ^ mask.get(2)) << 2;
if (n >= 4) state |= (mask.get(0) ^ mask.get(1) ^ mask.get(3)) << 3;
h.emplace(state);
}
}
return h.size();
}
};class Solution:
def flipLights(self, n: int, presses: int) -> int:
h = set()
for i in range(0, 1 << 4):
mask = Bit()
for j in range(0, 4):
if i >> j & 1: mask.add(j)
total = mask.count1()
if total & 1 == presses & 1 and total <= presses:
state = mask.get(0) ^ mask.get(2) ^ mask.get(3)
if n >= 2: state |= (mask.get(0) ^ mask.get(1)) << 1
if n >= 3: state |= (mask.get(0) ^ mask.get(2)) << 2
if n >= 4: state |= (mask.get(0) ^ mask.get(1) ^ mask.get(3)) << 3
h.add(state)
return len(h)
class Bit:
b = 0
def add(self, n: int): self.b |= 1 << n
def get(self, n: int) -> int: return self.b >> n & 1
def count1(self) -> int:
n, r = self.b, 0
while n > 0:
n &= n - 1
r += 1
return r