Java C语言如何实现LeetCode 672 灯泡开关题解示例？

本文共计1016个文字，预计阅读时间需要5分钟。

目录 + 主题要求 + 思路：寻找规则 + Java + C++ + Rust + 总结 + 主题要求 + 思路：寻找规则 + 找到最简通项表达式，今日参考：京城打工人 + 优先，归纳每个开关的影响，其中(k=0,1,2,)：+ 开关 + 反转

目录

• 题目要求
• 思路：找规律
• Java
• C++
• Rust
• 总结

题目要求

思路：找规律

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

首先，归纳每个开关会影响的灯，其中(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存在规律：

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

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

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

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

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

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

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

但按动一次时仅会出现三种情况：

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

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++题解灯泡开关的资料请关注自由互联其它相关文章！