Source: InterviewBit – Bulbs

N light bulbs are connected by a wire.

Each bulb has a switch associated with it, however due to faulty wiring, a switch also changes the state of all the bulbs to the right of current bulb.

Given an initial state of all bulbs, find the minimum number of switches you have to press to turn on all the bulbs.

You can press the same switch multiple times.

Note : 0 represents the bulb is off and 1 represents the bulb is on.

Input Format:

The first and the only argument contains an integer array A, of size N.

Output Format:

Return an integer representing the minimum number of switches required.

Constraints:

1 <= N <= 5e5
0 <= A[i] <= 1

Example:

Input 1:
    A = [1]

Output 1:
    0

Explanation 1:
    There is no need to turn any switches as all the bulbs are already on.

Input 2: 
    A = [0 1 0 1]

Output 2:
    4

Explanation 2:
	press switch 0 : [1 0 1 0]
	press switch 1 : [1 1 0 1]
	press switch 2 : [1 1 1 0]
	press switch 3 : [1 1 1 1]

解題：

這題原則上用一次 for 迴圈掃過就可以解開了，但在迴圈過程中需要持續追蹤翻轉的狀態。換句話說，只要執行過一次翻轉，則該序列值之後的所有元素都要跟著一起轉，但只要再轉一次，該元素就又會回到原本狀態。因此對這類型的題目，我們可以設定一個 boolean 變數來儲存目前翻轉的閥值：在閥值為 FALSE 時我們把眼光放在找原本數值為 0 的元素，當找到時表示需要進行翻轉將該元素轉變成 1 ，此時將閥值轉變為 TRUE ；而在閥值為 TRUE 時，我們改為尋找原本數值為 1 之元素（因為該元素已經被翻轉為 0 ）。如此一來便可在 For 迴圈掃過一輪後更新完陣列內的所有元素，並統計總共需翻轉幾次。

Code:

class Solution:
    # @param A : list of integers
    # @return an integer
    def bulbs(self, A):
        n = len(A)
        flips = 0
        coinFlip = True #True => check 0, False => check 1
        for i in range(n):
            if A[i] == 1 and coinFlip: continue #OK
            elif A[i] == 0 and coinFlip:
                #FLIPA!!
                flips += 1
                coinFlip = False #now we flip when meeting 1
            elif A[i] == 1:
                #coinFlip == False, FLIP!
                flips += 1
                coinFlip = True
        return flips

GitHub: GitHub

發表留言