Description
A string of '0'
s and '1'
s is monotone increasing if it consists of some number of '0'
s (possibly 0), followed by some number of '1'
s (also possibly 0.)
We are given a string S
of '0'
s and '1'
s, and we may flip any '0'
to a '1'
or a '1'
to a '0'
.
Return the minimum number of flips to make S
monotone increasing.
Example 1:
Input: "00110"
Output: 1
Explanation: We flip the last digit to get 00111.
Example 2:
Input: "010110"
Output: 2
Explanation: We flip to get 011111, or alternatively 000111.
Example 3:
Input: "00011000"
Output: 2
Explanation: We flip to get 00000000.
Note:
1 <= S.length <= 20000
S
only consists of'0'
and'1'
characters.
Solutions
1. Brute Force
# Time: O(n^2)
# Space: O(1)
class Solution:
def minFlipsMonoIncr(self, S: str) -> int:
if not S or len(S) == 0:
return 0
n = len(S)
min_flips = float('inf')
for i in range(n):
cnt, cnt0, cnt1 = 0, 0, 0
for j in range(i):
if S[j] == '1':
cnt += 1
for l in range(i, n):
if S[l] == '0':
cnt += 1
for m in range(n):
if S[m] == '0':
cnt0 += 1
else:
cnt1 += 1
min_flips = min(min_flips, cnt, cnt0, cnt1)
return min_flips
# TLE
2. 1D-DP
从两端扫描。
# Time: O(n)
# Space: O(n)
class Solution:
def minFlipsMonoIncr(self, S: str) -> int:
if not S or len(S) == 0:
return 0
n = len(S)
l = [0 for _ in range(n + 1)]
r = [0 for _ in range(n + 1)]
l[0] = 1 if S[0] == '1' else 0
r[n - 1] = 1 if S[n - 1] == '0' else 0
for i in range(1, n):
l[i] = l[i-1] + (1 if S[i] == '1' else 0)
for i in range(n-2, -1, -1):
r[i] = r[i+1] + (1 if S[i] == '0' else 0)
min_flips = r[0]
for i in range(1, n + 1):
min_flips = min(min_flips, l[i - 1] + r[i])
return min_flips
# 81/81 cases passed (108 ms)
# Your runtime beats 15.62 % of python3 submissions
# Your memory usage beats 25 % of python3 submissions (14.3 MB)
2. 2D-DP
# Time: O(n)
# Sapce: O(n)
class Solution:
def minFlipsMonoIncr(self, S: str) -> int:
if not S or len(S) == 0:
return 0
n = len(S)
dp = [[0 for _ in range(2)] for _ in range(n + 1)]
for i in range(1, n+1):
if S[i - 1] == '1':
dp[i][0] = dp[i-1][0] + 1
dp[i][1] = min(dp[i-1][0], dp[i-1][1])
else:
dp[i][0] = dp[i-1][0]
dp[i][1] = min(dp[i-1][0], dp[i - 1][1]) + 1
return min(dp[n][0], dp[n][1])
# 81/81 cases passed (144 ms)
# Your runtime beats 5.8 % of python3 submissions
# Your memory usage beats 25 % of python3 submissions (15.4 MB)
3. Optimized DP
当 dp[i] 只和 dp[i-1] 有关的话,可以进行降维!
# Time: O(n)
# Sapce: O(n)
class Solution:
def minFlipsMonoIncr(self, S: str) -> int:
if not S or len(S) == 0:
return 0
n = len(S)
dp0, dp1 = 0, 0
for i in range(1, n+1):
tmp0 = dp0 + (1 if S[i-1] == '1' else 0)
dp1 = min(dp0, dp1) + (1 if S[i-1] == '0' else 0)
dp0 = tmp0
return min(dp0, dp1)
# 81/81 cases passed (144 ms)
# Your runtime beats 5.8 % of python3 submissions
# Your memory usage beats 25 % of python3 submissions (15.4 MB)