题目要求
思路:找规律
找到尽可能最精简的通项表达,今日参考:京城打工人
首先,归纳每个开关会影响的灯,其中(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++题解灯泡开关的资料请关注好代码网其它相关文章!