Java?C++題解leetcode672燈泡開(kāi)關(guān)示例
題目要求
思路:找規(guī)律
找到盡可能最精簡(jiǎn)的通項(xiàng)表達(dá),今日參考:京城打工人
首先,歸納每個(gè)開(kāi)關(guān)會(huì)影響的燈,其中(k=0,1,2,…):
開(kāi)關(guān) | 反轉(zhuǎn)燈編號(hào) |
---|---|
一 | k |
二 | 2k |
三 | 2k+1 |
四 | 3k+1 |
可見(jiàn)燈以6盞為周期具有相同變化,所以以下只需要推導(dǎo)第一個(gè)周期里的6盞燈即可。
觀察前6盞燈:
燈 | 開(kāi)關(guān) |
---|---|
1 | 一、三、四 |
2 | 一、二 |
3 | 一、三 |
4 | 一、二、四 |
5 | 一、三 |
6 | 一、二 |
發(fā)現(xiàn)燈2、6和3、5分別受同樣的開(kāi)關(guān)影響,所以狀態(tài)相同;
觀察前4盞燈,發(fā)現(xiàn)燈1、3與燈2、4存在規(guī)律:
- 當(dāng)開(kāi)關(guān)
四
按動(dòng)次數(shù)為偶數(shù)時(shí),兩組燈狀態(tài)分別相同; - 當(dāng)開(kāi)關(guān)
四
按動(dòng)次數(shù)為奇數(shù)時(shí),兩組燈狀態(tài)分別不同; - 所以根據(jù)其中一組燈的狀態(tài)即可判斷另一組。
因此,選擇一組+另一組中的一盞,即可涵蓋所有燈的狀態(tài)。
因此選擇觀察前三盞燈即可預(yù)知所有明暗狀態(tài):
前三盞燈在不同按動(dòng)次數(shù)中的狀態(tài)如下:
發(fā)現(xiàn)在一次按動(dòng)時(shí)會(huì)出現(xiàn)四種狀態(tài),兩次按動(dòng)時(shí)出現(xiàn)七種狀態(tài)【缺少011狀態(tài)】,三次及以上按動(dòng)即可出現(xiàn)所有狀態(tài),共2^3=8種。
此時(shí)僅需枚舉一盞燈和兩盞燈時(shí)的狀態(tài)即可,后續(xù)都與三盞相同:
- 一盞燈僅可能有兩種狀態(tài);
- 兩盞燈可能有四種狀態(tài);
但按動(dòng)一次時(shí)僅會(huì)出現(xiàn)三種情況【缺少11狀態(tài)】:
- 將上述規(guī)律歸納為代碼即可!
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; } }
- 時(shí)間復(fù)雜度:O(1)O(1)O(1)
- 空間復(fù)雜度: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; } };
- 時(shí)間復(fù)雜度:O(1)
- 空間復(fù)雜度:O(1)
Rust
- 淺學(xué)一下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 } }, } } }
- 時(shí)間復(fù)雜度:O(1)
- 空間復(fù)雜度:O(1)
總結(jié)
本來(lái)以為要DP或者生模擬,結(jié)果是數(shù)學(xué)思維找規(guī)律。
一道代碼無(wú)敵簡(jiǎn)單,思路究極繞的題目,以至于推導(dǎo)完思路感覺(jué)就結(jié)束了【代碼都沒(méi)啥區(qū)別……】
以上就是Java C++題解leetcode672燈泡開(kāi)關(guān)示例的詳細(xì)內(nèi)容,更多關(guān)于Java C++題解燈泡開(kāi)關(guān)的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
如何解決Spring的UnsatisfiedDependencyException異常問(wèn)題
這篇文章主要介紹了如何解決Spring的UnsatisfiedDependencyException異常問(wèn)題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2024-04-04mybatis insert 返回自增主鍵的實(shí)現(xiàn)示例
mybatis 在新增之后怎么也獲取不到自增主鍵,本文主要介紹了mybatis insert 返回自增主鍵的實(shí)現(xiàn)示例,具有一定的參考價(jià)值,感興趣的可以了解一下2024-06-06Java獲取漢字對(duì)應(yīng)的拼音(全拼或首字母)
這篇文章主要介紹了Java如何獲取漢字對(duì)應(yīng)的拼音(全拼或首字母),文中實(shí)現(xiàn)的方法是引用了pinyin4j-2.5.0.jar,然后給出了完整的示例代碼,有需要的朋友可以參考借鑒,下面來(lái)一起看看吧。2017-01-01解決Eclipse add external jars運(yùn)行出現(xiàn)java.lang.NoClassDefFoundErro
本篇文章對(duì)Eclipse add external jars導(dǎo)致運(yùn)行出現(xiàn)java.lang.NoClassDefFoundError的解決方法進(jìn)行了詳細(xì)的分析介紹。需要的朋友參考下2013-05-05Required?request?body?is?missing的問(wèn)題及解決
這篇文章主要介紹了Required?request?body?is?missing的問(wèn)題及解決方案,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-12-12