926 Flip String to Monotone Increasing 將字符串翻轉(zhuǎn)到單調(diào)遞增
Description:
A binary string is monotone increasing if it consists of some number of 0's (possibly none), followed by some number of 1's (also possibly none).
You are given a binary string s. You can flip s[i] changing it from 0 to 1 or from 1 to 0.
Return the minimum number of flips to make s monotone increasing.
Example:
Example 1:
Input: s = "00110"
Output: 1
Explanation: We flip the last digit to get 00111.
Example 2:
Input: s = "010110"
Output: 2
Explanation: We flip to get 011111, or alternatively 000111.
Example 3:
Input: s = "00011000"
Output: 2
Explanation: We flip to get 00000000.
Constraints:
1 <= s.length <= 10^5
s[i] is either '0' or '1'.
題目描述:
如果一個由 '0' 和 '1' 組成的字符串呛伴，是以一些 '0'（可能沒有 '0'）后面跟著一些 '1'（也可能沒有 '1'）的形式組成的谒所，那么該字符串是單調(diào)遞增的。
我們給出一個由字符 '0' 和 '1' 組成的字符串 S劣领，我們可以將任何 '0' 翻轉(zhuǎn)為 '1' 或者將 '1' 翻轉(zhuǎn)為 '0'。
返回使 S 單調(diào)遞增的最小翻轉(zhuǎn)次數(shù)庶弃。
示例 :
示例 1：
輸入："00110"
輸出：1
解釋：我們翻轉(zhuǎn)最后一位得到 00111.
示例 2：
輸入："010110"
輸出：2
解釋：我們翻轉(zhuǎn)得到 011111德澈，或者是 000111。
示例 3：
輸入："00011000"
輸出：2
解釋：我們翻轉(zhuǎn)得到 00000000缴守。
提示:
1 <= S.length <= 20000
S 中只包含字符 '0' 和 '1'
思路:
動態(tài)規(guī)劃
設(shè) dp[i] 為下標為 i 對應的翻轉(zhuǎn)次數(shù)
如果當前字符為 '1', 這個字符不影響翻轉(zhuǎn)次數(shù) dp[i] = dp[i - 1]
如果當前字符為 '0', 要么 s[i + 1] = '1' 發(fā)生一次翻轉(zhuǎn) dp[i] = dp[i - 1] + 1, 要么將之前的 '1' 全部翻轉(zhuǎn)為 '0', 取兩者的最小值, 即 dp[i] = min(dp[i - 1] + 1, count of '1')
注意到 dp[i] 僅與 dp[i - 1] 有關(guān), 可以將空間復雜度優(yōu)化為 O(1)
時間復雜度為 O(n), 空間復雜度為 O(1)
代碼:
C++:
class Solution
{
public:
int minFlipsMonoIncr(string s)
{
int result = 0, one = 0, n = s.size();
for (const auto& c : s)
{
if (c == '1') ++one;
else result = min(result + 1, one);
}
return result;
}
};
Java:
class Solution {
public int minFlipsMonoIncr(String s) {
int result = 0, one = 0, n = s.length();
for (char c : s.toCharArray()) {
if (c == '1') ++one;
else result = Math.min(result + 1, one);
}
return result;
}
}
Python:
class Solution:
def minFlipsMonoIncr(self, s: str) -> int:
result, one, n = 0, 0, len(s)
for c in s:
result = min((one := one + 1 if c == '1' else one), (result := result + 1 if c == '0' else result))
return result
