专栏首页算法码上来【每日算法Day 61】LeetCode 672. 灯泡开关 Ⅱ

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

题目描述

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

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

  • 将所有灯泡的状态反转(即开变为关,关变为开)
  • 将编号为偶数的灯泡的状态反转
  • 将编号为奇数的灯泡的状态反转
  • 将编号为 的灯泡的状态反转()

示例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知乎同名华东师范大学计算机系硕士在读,方向自然语言处理与深度学习。喜欢与人分享技术与知识,期待与你的进一步交流~

本文分享自微信公众号 - 算法码上来(GodNLP),作者:godweiyang

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-03-06

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 论文赏析[ICLR18]联合句法和词汇学习的神经语言模型

    Neural Language Modeling by Jointly Learning Syntax and Lexicongodweiyang.com

    godweiyang
  • 【每日算法Day 72】谷歌面试题:又双叒叕是位运算,最详细的自动机推导过程

    给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现了三次。找出那个只出现了一次的元素。

    godweiyang
  • 【每日算法Day 108】一道简单的二叉树题目,写法还是挺多的。

    给定一棵二叉树,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。

    godweiyang
  • 设计模式~状态模式

    状态模式(State Pattern),又称状态对象模式(Pattern of Objects for States),状态模式是对象的行为模式。

    Vincent-yuan
  • 学以致用C++设计模式 之 “状态模式”

    要开发一款游戏,咱负责的模块是处理游戏角色属性框架的搭建,目前已知角色有:坦克、法师、射手,他们都有属性:血量、物攻、物抗、法攻、法抗、角色转换技能。

    看、未来
  • java设计模式之状态模式,策略模式的孪生兄弟

    状态模式(State Pattern)中,类的行为是基于它的状态改变的,状态之间的切换,在状态A执行完毕后自己控制状态指向状态B,状态模式是不停的切换状态执行,...

    用户4361942
  • 研究全脑神经网络时间动态的工具:脑电微状态介绍

    瑞士研究者Christoph M.Michel 和ThomasKoenig在NeuroImage发文,介绍了一种用多通道EEG表征人脑静息态活动的办法。...

    用户1279583
  • 书写高质量代码之状态维护

    我们第一眼接触新事物所触发的思考方式,决定了以后我们看待这样事物的角度,进而影响更深层次的理解和行为。

    哲洛不闹
  • 【设计模式系列】行为型之状态模式

    状态模式(State Pattern):允许一个对象在其内部状态改变时改变它的行为,对象看起来似乎修改了它的类。状态模式是一种对象行为型模式。大家着重理解对象,...

    沁溪源
  • 分布式系统中的“无状态”和“有状态”详解

    本文主要讲一些让系统更简单,更容易维护的东西——「易伸缩」,首当其冲的主题就是「stateless」,也叫「无状态」。

    一个会写诗的程序员

扫码关注云+社区

领取腾讯云代金券