[LeetCode解题报告] 926. 将字符串翻转到单调递增

• • 一、 题目
  • • 1. 题目描述
    • 2. 原题链接
  • 二、 解题报告
  • • 1. 思路分析
    • 2. 复杂度分析
    • 3. 代码实现
  • 三、 本题小结

如果一个二进制字符串，是以一些 0（可能没有 0）后面跟着一些 1（也可能没有 1）的形式组成的，那么该字符串是 单调递增 的。

给你一个二进制字符串 s，你可以将任何 0 翻转为 1 或者将 1 翻转为 0 。

返回使 s 单调递增的最小翻转次数。

示例 1：

输入：s = "00110"
输出：1
解释：翻转最后一位得到 00111.

示例 2：

输入：s = "010110"
输出：2
解释：翻转得到 011111，或者是 000111。

示例 3：

输入：s = "00011000"
输出：2
解释：翻转得到 00000000。

提示：

1 <= s.length <= 105
s[i] 为 ‘0’ 或 ‘1’

链接: 926. 将字符串翻转到单调递增

1. 转化为LIS求单调不降子序列最大长度，然后翻转其他位置即可，套板子，O(nlgn).
2. dp 。dp[i][0]表示截止位置i，s[0,i]若以0为结尾，最少翻转多少次。dp[i][1]是以1结尾。
   • 转移的时候考虑当前字符是0还是1，
   • s[i]==0，
     • 那么0 只能放到上个字符是0 的后边：dp[i][0]=dp[i-1][0]
     • 1可以放0或者1后边，把自己翻转步数+1:dp[i][1] = min(dp[i-1][0],dp[i-1][1)+1
   • s[i] == 1,
     • 那么0 只能放到上个字符是0 的后边，但自己要翻转：dp[i][0]=dp[i-1][0]+1
     • 1可以放0或者1后边:dp[i][1] = min(dp[i-1][0],dp[i-1][1])
3. 最后dp可以空间优化。
   

1. LIS O(nlgn)
2. dp O(n)

LIS。

class Solution:
    def minFlipsMonoIncr(self, s: str) -> int:
        def lis_non_decrease(nums):
            n = len(nums)
            # dp = [float('inf')] * (n+1)  # dp[i] 为长度为i的上升子序列的可以的最小尾巴  
            dp = []          
            for num in nums:
                if not dp or num >= dp[-1]:
                    dp.append(num)
                else:
                    pos = bisect_right(dp,num)
                    dp[pos] = num            
            return len(dp)
        
        return len(s) - lis_non_decrease([int(c) for c in s])

dp

class Solution:
    def minFlipsMonoIncr(self, s: str) -> int:
        n = len(s)
        dp = [[0]*2 for _ in range(n)]  # dp[i][0] 为截止位置i，s[0,i]若以0为结尾，最少翻转多少次。dp[i][1]是以1结尾。
        if s[0] == '0':
            dp[0][1] = 1
        else:
            dp[0][0] = 1
        for i in range(1,n):
            if s[i] == '0':
                dp[i][0] = dp[i-1][0]
                dp[i][1] = min(dp[i-1])+1
            else:
                dp[i][0] = dp[i-1][0] + 1
                dp[i][1] = min(dp[i-1])
                
        # print(dp)
        return min(dp[n-1])

dp空间优化

class Solution:
    def minFlipsMonoIncr(self, s: str) -> int:
        n = len(s)
        zero = 0 if s[0] == '0' else 1
        one = 0 if s[0] == '1' else 1
        for i in range(1,n):
            if s[i] == '0':
                one = min(zero,one) + 1
            else:
                zero,one = zero+1,min(zero,one)
        return min(zero)

1. 空间优化可以省一半多时间，看来Python内存管理有点费性能。