[leetcode] 926. Flip String to Monotone Increasing

[leetcode] 926. Flip String to Monotone Increasing

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: 1Explanation: We flip the last digit to get 00111.

Example 2:

Input: "010110"Output: 2Explanation: We flip to get 011111, or alternatively 000111.

Example 3:

Input: "00011000"Output: 2Explanation: We flip to get 00000000.

Note:

1 <= S.length <= 20000S only consists of ‘0’ and ‘1’ characters.

分析

题目的意思是：只包含0和1的字符串，可以0变成1，1变成0，问把一个字符串变成单调递增数列的最小替换操作数。这道题我想了一下，暴力破解难度好大，当然肯定会超时。看了答案发现用一个数组来存储前i个字符中1的个数：

P[i+1] = A[0] + A[1] + ... + A[i]A[i] = 1 如果 S[i] == '1', 否则 A[i] = 0

如果希望有x个0，后面跟着N-x个1的话，就需要使N-x -(P[-1]-P[x])个0需要被替换为1，P[x]替换为0。有点绕，想想好像是这么回事

代码

class Solution: def minFlipsMonoIncr(self, S: str) -> int: n=len(S) P=[0] for x in S: P.append(P[-1]+int(x)) res=float('inf') for j in range(len(P)): res=min(res,P[j]+len(S)-j-(P[-1]-P[j])) return res

参考文献

​​[LeetCode] Approach 1: Prefix Sums​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。