從LeetCode學演算法 - 101 String (6)

1529. Bulb Switcher IV (Medium)

寫在前面

抽獎活動還在繼續累積人數(現在好像沒有人想抽XD)
在Python Taiwan的連結第100篇的文章 底下，
公開分享到你的臉書、按讚該篇文章、並留言告訴我說，
「你最喜歡這一整個系列的哪一篇？為什麼？」或
「除了從LeetCode學演算法系列以外，
你還想要看到關於什麼方向的文章？」
超過20則留言的話 (有完成以上步驟的才算)，我們就抽一組
「從Leetcode學演算法｜進階篇」+「從Leetcode學演算法｜面試篇」
課程的免費兌換券進行贈送！

截止時間為7/31 23:59:59，這之後的留言問題我有看到還是會回答，
但就不會納入抽獎資格歐！

容筆者工商一下，
「從Leetcode學演算法｜進階篇」 開放預購啦！
這次選了40道難度加深的LeetCode題目，
同樣也會細部解說對應的技巧及須要掌握的演算法！
同時這次購買進階篇的話，
額外還加贈**「從Leetcode學演算法｜面試篇」** ！
當中包含了面試準備須知分享 ，及訪談國內外不同經驗的工程師 ，
讓你不論是想走前端/後端/一般軟工 或者是想找國外的工作 ，
是初學想轉職 還是正在工作 ，都能夠從中得到收穫呦！

當前面試篇以上傳完畢，進階篇則會在8/31前陸續上傳完成呦！

有興趣的朋友可以使用下面的早鳥優惠～
「從Leetcode學演算法｜進階篇」+「從Leetcode學演算法｜面試篇」 ：
https://bit.ly/advleetcode

「從Leetcode學演算法」全套(基礎/進階/面試篇)同捆優惠：
https://bit.ly/allleetcode

Question

There is a room with n bulbs, numbered from 0 to n-1, arranged in a row from left to right. Initially all the bulbs are turned off .

Your task is to obtain the configuration represented by target where target[i] is ‘1’ if the i-th bulb is turned on and is ‘0’ if it is turned off.

You have a switch to flip the state of the bulb, a flip operation is defined as follows:

Choose any bulb (index i) of your current configuration.
Flip each bulb from index i to n-1.

When any bulb is flipped it means that if it is 0 it changes to 1 and if it is 1 it changes to 0.

Return the minimum number of flips required to form target.

Example 1

1
2
3
4
5
6
7
Input: target = "10111"
Output: 3
Explanation: Initial configuration "00000".
flip from the third bulb:  "00000" -> "00111"
flip from the first bulb:  "00111" -> "11000"
flip from the second bulb:  "11000" -> "10111"
We need at least 3 flip operations to form target.

Example 2

1
2
3
Input: target = "101"
Output: 3
Explanation: "000" -> "111" -> "100" -> "101".

Example 3

1
2
Input: target = "00000"
Output: 0

Example 4

1
2
Input: target = "001011101"
Output: 5

Constraints

1 <= target.length <= 10^5
target[i] == '0' or target[i] == '1'

分析/解題

這題是今天(2020/07/26)舉辦的199th LeetCode Weekly Contest的第2題。
房間裡有n個燈泡**(0~n-1)** ，從左至右排列，初始全數是關的 。
我們的目標是將燈開關成target 的狀態，在index i的位置上，
target[i]如果是'1’的話就表示開，target[i]如果是'0’的話就表示關。

所能夠做的操作只有一種叫flip 的方法。
flip方法的操作是選取一個index i，
接著會將i~n-1的所有燈泡狀態反轉，1變成0，0變成1 。

我們要作的事情是找出最少完成target的flip次數。

是說每次碰到稍微生活化一點的題目，就會覺得有點87：
像這題亮燈就亮燈，搞那麼麻煩的開關方式幹嘛啦！！！
不怕燈泡壞掉逆？？？

這題乍看之下好像不容易，
但仔細一看，flip的操作只影響該點及其右側的燈泡，
所以我們由左往右看的話，只需要考慮當前該燈泡需不需要翻轉 即可，
因為某個點右側的燈泡flip不會影響該點。

由於右邊的會一起反轉 ，所以我們可以定位一個flag=1 ，
一開始大家都是0，所以第一次我們要翻轉的狀況，
就是碰到target[i]和flag相等時。 把右側翻過來以後，我們可以將flag從'1’變成'0’，
因為我們只要考慮翻或不翻 ，所以使用flag的變化 ，
和target[i]碰到的値來作對照 會相當方便：
只要碰到和flag相同的就代表要加翻一次 ，
不同的就代表不用翻 ，這樣沿路走到尾端，就可以得到計數的答案。

依此，寫成程式碼如下：

Java

Java的部分使用charAt可以按char來取出每個字元，
請留意要比較的時候要取成int，這邊直接減去’0’即可。

Python

Python的部分直接用int進行轉換字元成整數即可。

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(len(target))/O(1)，除了flag跟cnt以外並未額外再多用到其他空間)

相似及延伸

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~

另外，「從Leetcode學演算法｜基礎篇」 已經回原價囉，
先前的優惠碼會失效，但這邊仍然為讀者保留了300塊的折抵，
雖然整捆一起買總體比較划算 (差290而已就有整組了阿XD)，
如果你還是想先試試基礎課的話，
300元折抵的連結 在這邊：
https://bit.ly/1desolve