Java?C++題解leetcode672燈泡開關(guān)示例

更新時(shí)間：2022年09月29日 14:27:03 作者：AnjaVon

這篇文章主要為大家介紹了Java?C++題解leetcode672燈泡開關(guān)示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

題目要求

思路：找規(guī)律

找到盡可能最精簡的通項(xiàng)表達(dá)，今日參考：京城打工人

首先，歸納每個(gè)開關(guān)會(huì)影響的燈，其中(k=0,1,2,…)：

開關(guān)	反轉(zhuǎn)燈編號(hào)
一	k
二	2k
三	2k+1
四	3k+1

可見燈以6盞為周期具有相同變化，所以以下只需要推導(dǎo)第一個(gè)周期里的6盞燈即可。

觀察前6盞燈：

燈	開關(guān)
1	一、三、四
2	一、二
3	一、三
4	一、二、四
5	一、三
6	一、二

發(fā)現(xiàn)燈2、6和3、5分別受同樣的開關(guān)影響，所以狀態(tài)相同；

觀察前4盞燈，發(fā)現(xiàn)燈1、3與燈2、4存在規(guī)律：

當(dāng)開關(guān)四按動(dòng)次數(shù)為偶數(shù)時(shí)，兩組燈狀態(tài)分別相同；
當(dāng)開關(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
                }
            },
        }
    }
}