672. 燈泡開關 Ⅱ : 分情況讨論

​

題目描述

這是 LeetCode 上的 672. 燈泡開關 Ⅱ ，難度為 中等。

Tag : 「腦筋急轉彎」、「找規律」

房間中有 ​

​n​

​​ 隻已經打開的燈泡，編号從 ​

​1​

​​ 到 ​

​n​

​​ 。牆上挂着 ​

​4​

​ 個開關 。

這 ​

​4​

​ 個開關各自都具有不同的功能，其中：

• 開關 1 ：反轉目前所有燈的狀态（即開變為關，關變為開）
• 開關 2 ：反轉編号為偶數的燈的狀态（即​

  ​2, 4, ...​

  ​）
• 開關 3 ：反轉編号為奇數的燈的狀态（即​

  ​1, 3, ...​

  ​）
• 開關 4 ：反轉編号為​

  ​j = 3k + 1​

  ​​ 的燈的狀态，其中​

  ​k = 0, 1, 2, ...​

  ​​（即​

  ​1, 4, 7, 10, ...​

  ​）

你必須 恰好 按壓開關 ​

​presses​

​​ 次。每次按壓，你都需要從 ​

​4​

​ 個開關中選出一個來執行按壓操作。

給你兩個整數 ​

​n​

​​ 和 ​

​presses​

​，執行完所有按壓之後，傳回 不同可能狀态 的數量。

示例 1：

輸入：n = 1, presses = 1

輸出：2

解釋：狀态可以是：
- 按壓開關 1 ，[關]
- 按壓開關 2 ，[開]      

示例 2：

輸入：n = 2, presses = 1

輸出：3

解釋：狀态可以是：
- 按壓開關 1 ，[關, 關]
- 按壓開關 2 ，[開, 關]
- 按壓開關 3 ，[關, 開]      

示例 3：

輸入：n = 3, presses = 1

輸出：4

解釋：狀态可以是：
- 按壓開關 1 ，[關, 關, 關]
- 按壓開關 2 ，[關, 開, 關]
- 按壓開關 3 ，[開, 關, 開]
- 按壓開關 4 ，[關, 開, 開]      

提示：

分情況讨論

記燈泡數量為 （至少為 ），翻轉次數為 （至少為 ），使用 ​​

​1​

​​ 代表燈亮，使用 ​

​0​

​ 代表燈滅。

我們根據 和

• 當時，無論為何值，都隻有起始（全​​

  ​1​

  ​）一種狀态；
• 當時，根據進一步分情況讨論：

• 當時，若為滿足「」的最小值時，能夠取滿「​​

  ​1​

  ​​/​

  ​0​

  ​​」兩種情況，而其餘更大
• 當時，若，能夠取得「​​

  ​11​

  ​​/​

  ​10​

  ​​/​

  ​01​

  ​​」三種狀态，當時，能夠取滿「​​

  ​11​

  ​​/​

  ​10​

  ​​/​

  ​01​

  ​​/​

  ​00​

  ​​」四種狀态，其餘更大可以通過前步歸結到任一狀态，再通過最後一次的操作
• 當時，若時，對應種操作可取得種方案；當時，可取得種狀态；而當時可取滿種狀态，更大的值可通過同樣的方式歸結到取滿的
• 當時，根據四類操作可知，燈泡每組一循環（對應序列​​

  ​k + 1​

  ​​、​

  ​2k + 2​

  ​​、​

  ​2k + 1​

  ​​ 和​

  ​3k + 1​

  ​​），即隻需考慮的情況，而、和時，後引入的燈泡狀态均不會産生新的組合（即新引入的燈泡狀态由前三個燈泡的狀态所唯一确定），是以均可歸納到

Java 代碼：

class Solution {
    public int flipLights(int n, int {
        if (k == 0) return 1;
        if (n == 1) return 2;
        else if (n == 2) return k == 1 ? 3 : 4;
        else return k == 1 ? 4 : k == 2 ? 7 : 8;
    }
}      

TypeScript 代碼：

function flipLights(n: number, k: number): number {
    if (k == 0) return 1
    if (n == 1) return 2
    else if (n == 2) return k == 1 ? 3 : 4;
    else return k == 1 ? 4 : k == 2 ? 7 : 8;
};      

• 時間複雜度：
• 空間複雜度：

最後

這是我們「刷穿 LeetCode」系列文章的第 ​

​No.672​

​ 篇，系列開始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道題目，部分是有鎖題，我們将先把所有不帶鎖的題目刷完。

在這個系列文章裡面，除了講解解題思路以外，還會盡可能給出最為簡潔的代碼。如果涉及通解還會相應的代碼模闆。

為了友善各位同學能夠電腦上進行調試和送出代碼，我建立了相關的倉庫：github.com/SharingSour… 。