【每日算法Day 61】LeetCode 672. 灯泡开关 Ⅱ

godweiyang

发布于 2020-03-24 11:07:52

5210

发布于 2020-03-24 11:07:52

文章被收录于专栏：算法码上来

题目描述

现有一个房间，墙上挂有只已经打开的灯泡和个按钮。在进行了次未知操作后，你需要返回这只灯泡可能有多少种不同的状态。

假设这只灯泡被编号为，这个按钮的功能如下：

将所有灯泡的状态反转（即开变为关，关变为开）
将编号为偶数的灯泡的状态反转
将编号为奇数的灯泡的状态反转
将编号为的灯泡的状态反转（)

示例1

输入：
n = 1, m = 1.
输出：
2
解释：
状态为: [开], [关]

示例2

输入：
n = 2, m = 1.
输出：
3
解释：
状态为: [开, 关], [关, 开], [关, 关]

示例3

输入：
n = 3, m = 1.
输出：
4
解释：
状态为: [关, 开, 关], [开, 关, 开], [关, 关, 关], [关, 开, 开].

提示

和都属于 .

题解

首先我们要知道，一个操作做两次就等于没做，所以一个操作只有没做和做了两种状态，也就是说有效操作数量最多次：。

然后我们观察每一个操作对灯状态（初始都开着，状态都为）的影响：

操作每个灯状态就要反转一次，也就是灯的状态按照周期重复（与异或）。
操作每个灯状态就要反转一次，也就是灯的状态按照周期重复（与异或）。
操作每个灯状态就要反转一次，也就是灯的状态按照周期重复（与异或）。
操作每个灯状态就要反转一次，也就是灯的状态按照周期重复（与异或）。

综上，我们只需要取周期的最小公倍数就行了。也就是只需要看前盏灯的最终状态，就能唯一确定后面所有灯的最终状态。

形式化表示，用表示第个操作是否用过。那么对于第盏灯来说，它的最终状态可以表示为：

由此可以推出：，也就是灯的最终状态以为周期。

到此其实可以直接暴力枚举的所有状态了，但是还是有优化空间的。

如果我们列出前盏灯的状态：

我们可以看出，如果前盏灯状态确定了，可以唯一确定出后盏灯状态。因此，我们只需要计算前盏灯有多少种状态就行了。

最终经过枚举计算（）：

如果，那么就只有种状态（灯都开着）。
否则如果，那么有种状态。
否则如果，若，就有种状态；若，就有种状态。
否则如果，若，就有种状态；若，就有种状态；若，就有种状态。

如果你实在不想手动计算，那你可以枚举所有的种操作状态，然后保存前三盏灯的状态到一个集合中，最终输出集合大小就行了。

代码

c++

class Solution {
public:
    int flipLights(int n, int m) {
        if (m == 0) return 1;
        if (n == 1) return 2;
        m = min(m, 3);
        if (n == 2) return vector<int>{3, 4, 4}[m-1];
        return vector<int>{4, 7, 8}[m-1];
    }
};

python

class Solution:
    def flipLights(self, n: int, m: int) -> int:
        if m == 0: return 1
        if n == 1: return 2
        m = min(m, 3)
        if n == 2: return [3, 4, 4][m-1]
        return [4, 7, 8][m-1]

python（枚举）

class Solution:
    def flipLights(self, n, m):
        seen = set()
        for cand in itertools.product((0, 1), repeat = 4):
            if sum(cand) % 2 == m % 2 and sum(cand) <= m:
                A = []
                for i in range(min(n, 3)):
                    light = 1
                    light ^= cand[0]
                    light ^= cand[1] and i % 2
                    light ^= cand[2] and i % 2 == 0
                    light ^= cand[3] and i % 3 == 0
                    A.append(light)
                seen.add(tuple(A))
        return len(seen)

作者简介：godweiyang，知乎同名，华东师范大学计算机系硕士在读，方向自然语言处理与深度学习。喜欢与人分享技术与知识，期待与你的进一步交流~

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-03-06，如有侵权请联系 cloudcommunity@tencent.com 删除

python

本文分享自算法码上来微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

python

登录后参与评论

0 条评论

热度