Java C++题解leetcode672灯泡开关示例

题目要求思路:找规律 找到尽可能最精简的通项表达,今日参考:京城打工人 首先,归纳每个开关会影响的灯,其中(k=0,1,2,…): 开关反转灯编号

题目要求

思路:找规律

找到尽可能最精简的通项表达,今日参考:京城打工人

首先,归纳每个开关会影响的灯,其中(k=0,1,2,…):

开关反转灯编号
k
2k
2k+1
3k+1

可见灯以6盏为周期具有相同变化,所以以下只需要推导第一个周期里的6盏灯即可。

观察前6盏灯:

开关
1一、三、四
2一、二
3一、三
4一、二、四
5一、三
6一、二

发现灯2、6和3、5分别受同样的开关影响,所以状态相同;

观察前4盏灯,发现灯1、3与灯2、4存在规律:

  • 当开关按动次数为数时,两组灯状态分别相同
  • 当开关按动次数为数时,两组灯状态分别不同
  • 所以根据其中一组灯的状态即可判断另一组。

因此,选择一组+另一组中的一盏,即可涵盖所有灯的状态。

因此选择观察前三盏灯即可预知所有明暗状态:

前三盏灯在不同按动次数中的状态如下:

发现在一次按动时会出现四种状态,两次按动时出现七种状态【缺少011状态】,三次及以上按动即可出现所有状态,共2^3=8种。

此时仅需枚举一盏灯和两盏灯时的状态即可,后续都与三盏相同:

  • 一盏灯仅可能有两种状态;
  • 两盏灯可能有四种状态;

但按动一次时仅会出现三种情况【缺少11状态】:

  • 将上述规律归纳为代码即可!

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)

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)

总结

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

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

以上就是Java C++题解leetcode672灯泡开关示例的详细内容,更多关于Java C++题解灯泡开关的资料请关注好代码网其它相关文章!