LeetCode 319 Bulb Switcher（燈泡切換）（從規律中發現算法……）

翻譯

這兒有n個燈泡被初始化。

首先，你點亮所有的燈泡。

然後，你關掉每第二個燈泡。

在第三回，你切換每第三個燈泡（如果它是關閉的則開啟它，如果它是開啟的則關閉它）。

對於第i回，你切換每第i個燈泡。

對於第n回，你僅僅切換最後一個燈泡。

找出在n回之後還有多少個燈泡是亮著的。

原文

There are n bulbs that are initially off. 

You first turn on all the bulbs. 

Then, you turn off every second bulb. 

On the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). 

For the ith round, you toggle every i bulb. 

For the nth round, you only toggle the last bulb. 

Find how many bulbs are on after n rounds.

Example:

Given n = 3. 

At first, the three bulbs are [off, off, off].
After first round, the three bulbs are [on, on, on].
After second round, the three bulbs are [on, off, on].
After third round, the three bulbs are [on, off, off]. 

So you should return 1, because there is only one bulb is on.

分析

我在本道題的第一階段

我甚至都不能理解題目，什麼叫every second bulb？又不是有一個二維數組（矩陣），如果把every second bulb理解成second bulb那最後豈不是只有第一個燈是亮著的了？

所以隨便寫了個函數試試：

class Solution {
public:
    int bulbSwitch(int n) {
        if(n == 0) return 0;
        return 1;
    }
};

於是LeetCode就告訴我如果輸入是4，則應該返回2……繼續：

class Solution {
public:
    int bulbSwitch(int n) {
        if(n == 0) return 0;
        if(n == 4) return 2;
        return 1;
    }
};

又告訴我如果輸入是5，還是應該返回2。

於是在紙上演算了一下，結論是每兩個的意思是第二個、第四個、第六個……

我在本道題的第二階段

根據以上的思路，寫出了如下算法，功能是實現了，體驗卻不好。LeetCode也告訴我如果是999999什麼的，就超時了……

int bulbSwitch(int n) {
    bool* bulb = new bool[n];
    for (int i = 1; i <= n; ++i) {
        if (i == 1) {
            for (int j = 0; j < n; ++j)
                bulb[j] = true;
        }
        if (i > 1 && i < n) {
            for (int j = i; j < n; ) {
                bulb[j - 1] = bulb[j - 1] == true ? false : true;
                j += i;
            }
        }
        if (i == n) {
            bulb[n - 1] = bulb[n - 1] == true ? false : true;
        }
    }
    int result = 0;
    for (int i = 0; i < n; ++i) {
        if (bulb[i] == true)
            result += 1;
    }
    return result;
}

我在本道題的第三階段

於是我就試圖用位運算，把bool型的數組換成一個二進制的數字，二進制中的0和1正好表示bool數組，這樣一來存儲花費的空間就小了，效率也就高了。然而，我並沒有完成……實在是有些復雜，以後可以繼續嘗試。

我在本道題的第四階段

位運算沒走通，就想走捷徑了。為了清晰看到裡面的變化過程，就全部打印了出來：

7的話好像還看不出來什麼……

20的話，忽然發現了最底下，哎喲，有點意思啊……

繼續試了試30，於是就堅信了是這樣的。

1 + 2 + 1 + 4 + 1 + 6 + 1 + 8 + 1 + 10 + 1

我把這個稱為履帶車，其中的“2，4，6，8……”稱為輪子。

    int wheel = 2;
    int result = 0;
    int trackvehicle = 0;
    bool isNotWheel = true;

第一個輪子是從2開始的，result是最終的結果，trackvehicle是整個履帶車的長度，isNotWheel作為初始的第一個並不是輪子（第二個、第四個才是輪子）。

Ok，邏輯也非常簡單，直接上代碼……

代碼

class Solution {
public:
int bulbSwitch(int n) {
    int wheel = 2;
    int result = 0;
    int    trackvehicle = 0;
    bool isNotWheel = true;
    while ( trackvehicle < n ) {
        if (isNotWheel) {
            trackvehicle += 1;
            result += 1;
            isNotWheel = !isNotWheel;
        }
        else {
            trackvehicle += wheel;
            wheel += 2;                       
            isNotWheel = !isNotWheel;
        }   
    }
    return result;
}
};