JAVA程序设计：灯泡开关 Ⅱ（LeetCode：672）

68 阅读 0 评论 45 点赞

我是靠谱客的博主秀丽胡萝卜，最近开发中收集的这篇文章主要介绍JAVA程序设计：灯泡开关 Ⅱ（LeetCode：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].

方法一：

这道题真的很有意思，看似很棘手的问题，我们可以从规则中看出端倪

1）前6个灯唯一地决定了其余的灯。这是因为每一个修改第 x 的灯光的操作都会修改第 (x+6) 的灯光。

2）进行 A 操作后接 B 操作和 B 操作后接 A 操作是一样的，所以我们可以假设我们按顺序进行所有操作。

3）连续两次执行相同的操作与不执行任何操作相同。所以我们只需要考虑每个操作是 0 次还是 1 次。

此时我们就能用暴力解决啦。

class Solution {
int ans;
StringBuilder str;
Map<String,Boolean> map;
public int flipLights(int n, int m) {
ans=0;
map=new HashMap<>();
int[] a=new int[n+1];
str=new StringBuilder();
for(int i=1;i<=n;i++)
a[i]=1;
dfs(a,Math.min(n, 6),Math.min(m, 4));
return ans;
}
private void dfs(int[] a,int n,int m) {
if(m==0) {
str.delete(0, str.length());
for(int i=1;i<=n;i++)
str.append(String.valueOf(a[i]));
if(!map.containsKey(str.toString())) {
ans++;
map.put(str.toString(), true);
}
return;
}
for(int i=1;i<=n;i++) a[i]=1-a[i];
dfs(a,n,m-1);
for(int i=1;i<=n;i++) a[i]=1-a[i];
for(int i=1;i<=n;i++) if(i%2==0) a[i]=1-a[i];
dfs(a,n,m-1);
for(int i=1;i<=n;i++) if(i%2==0) a[i]=1-a[i];
for(int i=1;i<=n;i++) if(i%2==1) a[i]=1-a[i];
dfs(a,n,m-1);
for(int i=1;i<=n;i++) if(i%2==1) a[i]=1-a[i];
for(int i=1;i<=n;i++) if(i%3==1) a[i]=1-a[i];
dfs(a,n,m-1);
for(int i=1;i<=n;i++) if(i%3==1) a[i]=1-a[i];
}
}

方法二：上述暴力的优化，我们可以直接枚举4个开关的状态，因为每个按钮不管按多少次其等效于0次或者1次！

class Solution {
public int flipLights(int n, int m) {
n=Math.min(n, 6);
int shift=Math.max(0, 6-n);
Set<Integer> st=new HashSet<>();
for(int status=0;status<16;status++) {
int count=Integer.bitCount(status);
if(count%2==m%2 && count<=m) {
int lights=0;
if(((status>>0)&1)>0) lights^=0b111111>>shift;
if(((status>>1)&1)>0) lights^=0b010101>>shift;
if(((status>>2)&1)>0) lights^=0b101010>>shift;
if(((status>>3)&1)>0) lights^=0b110110>>shift;
st.add(lights);
}
}
return st.size();
}
}

方法三：

因为前 6 个灯唯一地决定了其余的灯。这是因为修改第 xx 灯光的每个操作都会修改第 (x+6)(x+6) 灯光，因此 xx 灯光始终等于 (x+6)(x+6) 灯光。
实际上，前 3 个灯唯一地确定了序列的其余部分，如下表所示，用于执行操作 a, b, c, d:

Light 1 = 1 + a + c + d
Light 2 = 1 + a + b
Light 3 = 1 + a + c
Light 4 = 1 + a + b + d
Light 5 = 1 + a + c
Light 6 = 1 + a + b

上述理由表明，在不损失一般性的情况下，取 n = min(n, 3)是合理的。
让我们用 (a, b, c) 来表示灯的状态。与值为 (1, 1, 1), (0, 1, 0), (1, 0, 1) xor.
当 m=0 时，所有灯都亮起，只有一个状态 (1, 1, 1)(1,1,1)。在这种情况下，答案总是 1。
当 m=1 时，我们可以得到状态 (0, 0, 0), (1, 0, 1), (0, 1, 0), (0,1,1)。在这种情况下，对于 n = 1, 2, 3 的答案是 2, 3, 4。
当 m=2 时，我们可以检查是否可以获得 7 个状态：除(0, 1, 1)之外的所有状态。在这种情况下，n = 1, 2, 3n=1,2,3 的答案是 2, 4, 7。
当 m=3 时，我们可以得到所有 8 个状态。在这种情况下，n = 1, 2, 3 的答案是 2, 4, 8

class Solution {
public int flipLights(int n, int m) {
n = Math.min(n, 3);
if (m == 0) return 1;
if (m == 1) return n == 1 ? 2 : n == 2 ? 3 : 4;
if (m == 2) return n == 1 ? 2 : n == 2 ? 4 : 7;
return n == 1 ? 2 : n == 2 ? 4 : 8;
}
}