每日一题做题记录，参考官方和三叶的题解

题目要求

思路：找规律

• 找到尽可能最精简的通项表达，今日参考：京城打工人
• 首先，归纳每个开关会影响的灯，其中(k=0,1,2,… )(k=0,1,2,\dots)(k=0,1,2,…)：

  • 开关	反转灯编号
    一一一	kkk
    二二二	2k2k2k
    三三三	2k+12k+12k+1
    四四四	3k+13k+13k+1

  • 可见灯以666盏为周期具有相同变化，所以以下只需要推导第一个周期里的666盏灯即可。
• 观察前666盏灯：

  • 灯	开关
    111	一、三、四一、三、四一、三、四
    222	一、二一、二一、二
    333	一、三一、三一、三
    444	一、二、四一、二、四一、二、四
    555	一、三一、三一、三
    666	一、二一、二一、二

  • 发现灯2、62、62、6和3、53、53、5分别受同样的开关影响，所以状态相同；
  • 观察前444盏灯，发现灯1、31、31、3与灯2、42、42、4存在规律：
    • 当开关四按动次数为偶数时，两组灯状态分别相同；
    • 当开关四按动次数为奇数时，两组灯状态分别不同；
    • 所以根据其中一组灯的状态即可判断另一组。
  • 因此，选择一组+++另一组中的一盏，即可涵盖所有灯的状态。
• 因此选择观察前三盏灯即可预知所有明暗状态：
  • 前三盏灯在不同按动次数中的状态如下：
  • 发现在一次按动时会出现四种状态，两次按动时出现七种状态【缺少011011011状态】，三次及以上按动即可出现所有状态，共23=82^3=823=8种。
• 此时仅需枚举一盏灯和两盏灯时的状态即可，后续都与三盏相同：
  • 一盏灯仅可能有两种状态；
  • 两盏灯可能有四种状态；
    • 但按动一次时仅会出现三种情况【缺少111111状态】：
• 将上述规律归纳为代码即可！

Java

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
            return presses == 1 ? 4 : presses == 2 ? 7 : 8;
    }
}

• 时间复杂度：O(1)O(1)O(1)
• 空间复杂度：O(1)O(1)O(1)

C++

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
            return presses == 1 ? 4 : presses == 2 ? 7 : 8;
    }
};

• 时间复杂度：O(1)O(1)O(1)
• 空间复杂度：O(1)O(1)O(1)

Rust

• 浅学一下rust的match~

impl Solution {
    pub fn flip_lights(n: i32, presses: i32) -> i32 {
        if presses == 0 {
            return 1;
        }
        match n {
            1 => 2,
            2 => {
                match presses {
                    1 => 3,
                    _ => 4
                }
            },
            _ => {
                match presses {
                    1 => 4,
                    2 => 7,
                    _ => 8
                }
            },
        }
    }
}

• 时间复杂度：O(1)O(1)O(1)
• 空间复杂度：O(1)O(1)O(1)

总结

本来以为要DP或者生模拟，结果是数学思维找规律。

一道代码无敌简单，思路究极绕的题目，以至于推导完思路感觉就结束了【代码都没啥区别……】。

欢迎指正与讨论！