926. Flip String to Monotone Increasing
給你一個只有 0 和 1 的 string s，問你最少要翻轉幾次才能把它變為遞增
翻轉:把某個 0 變成 1 或者是把某個 1 變成 0
Example 1:
Input: s = "00110"
Output: 1
翻轉成 00111
Example 2:
Input: s = "010110"
Output: 2
翻轉成 000111/011111
Example 3:
Input: s = "00011000"
Output: 2
翻轉成 00000000
思路:
1.要讓 string 是遞增就必須是一串 0 接著一串 1
也就是說對於某個 index = i, s[:i] 全部都是 0, s[i:] 全部都是 1
我們就去遍歷所有 i, 看看要讓 s[:i] 翻轉成 0 的次數加上 s[i:] 翻轉成 1 的次數
在哪個 i 時會是最小
2.要把 s[:i] 翻轉成 0 的次數其實就是算 s 的 prefix sum, O(n)解決
算完全部後再反著做 s[i:], iterate i = len(s)-1 ~ 0 然後一邊檢查最小值就好
時間 O(n) 空間 O(n)
3.看了討論區有種更好的做法是用類似 dp 的概念
假設已經知道要把 s[:i] 翻轉成遞增的最小次數 n 了
那 s[:i+1] 就有兩種可能
一種是 s[i] 變成/保持 1, 這種狀況下可以直接拿 n 來用
因為 s[:i] 翻轉 n 次已經變成遞增了, s[i] 的 1 可以直接接在後面
這種情況下最佳解就會是 n + (s[i] == 0), 也就是如果 s[i] == 0 要把他轉成 1
另一種是 s[i] 變成/保持 0, 這種狀況下 n 就沒用了
因為 s[:i] 轉完後有可能是 1 結尾, s[i] 的 0 不能接
所以這裡最佳解就只能是把 s[:i] 和 s[i] 全部都變成 0, 也就是 prefix sum
最後再比兩種狀況哪種比較小就好
這種做法比剛剛那種好的原因是可以只 iterate i 一次, 也不用記整個 prefix sum
時間一樣是 O(n) 空間變成 O(1)
Python code:
class Solution:
def minFlipsMonoIncr(self, s: str) -> int:
one = opt = 0
for c in s:
one += (c == '1')
opt = min(one, opt + (c == '0'))
return opt

大師