每日算法系列【LeetCode 926】将字符串翻转到单调递增

简介: 每日算法系列【LeetCode 926】将字符串翻转到单调递增

题目描述

如果一个由 '0' 和 '1' 组成的字符串,是以一些 '0'(可能没有 '0')后面跟着一些 '1'(也可能没有 '1')的形式组成的,那么该字符串是单调递增的。

我们给出一个由字符 '0' 和 '1' 组成的字符串 S,我们可以将任何 '0' 翻转为 '1' 或者将 '1' 翻转为 '0'。

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

示例1

输入:
"00110"
输出:
1
解释:
我们翻转最后一位得到 00111.

示例2

输入:
"010110"
输出:
2
解释:
我们翻转得到 011111,或者是 000111。

示例3

输入:
"00011000"
输出:
2
解释:
我们翻转得到 00000000。

提示

  • 1 <= S.length <= 20000
  • S 中只包含字符 '0' 和 '1'

题解

要想把字符串变成递增的,只有两种可能,一种就是从某一处开始全是 1 ,之前都是 0 或者没有,另一种就是全 0 。那么我们只需要遍历这个 1 开始的位置就行了。

对于位置 i ,我们假设从它开始后面都是 1 ,前面都是 0 ,那么需要修改的的次数就是它后面 0 的数量减去它前面 1 的数量。

如果我们用数组预处理出来位置 i 开始到最后 1 的数量,记为  。那么它后面 0 的数量就可以表示为  ,也就是后面的长度减去 1 的数量。而它前面 1 的数量可以表示为  ,也就是 1 的总数量减去 i 后面 1 的数量。

那么总的修改次数就是  ,我们只需要遍历所有的 i ,找出最小值就行了。

另外还需要比较一下  的大小,也就是把所有的 1 都修改为 0 。

最终时间复杂度是  ,空间复杂度也是  。

代码

c++

class Solution {
public:
    int minFlipsMonoIncr(string S) {
        int n = S.size();
        int dp[n+1];
        dp[n] = 0;
        for (int i = n-1; i >= 0; --i) {
            dp[i] = dp[i+1] + (S[i] == '1');
        }
        int res = dp[0];
        for (int i = 0; i < n; ++i) {
            res = min(res, dp[0]-dp[i]+n-i-dp[i]);
        }
        return res;
    }
};

python

class Solution:
    def minFlipsMonoIncr(self, S: str) -> int:
        n = len(S)
        dp = [0] * (n+1)
        for i in range(n-1, -1, -1):
            dp[i] = dp[i+1] + (1 if S[i]=='1' else 0)
        res = dp[0]
        for i in range(n):
            res = min(res, dp[0]-dp[i]+n-i-dp[i])
        return res
相关文章
|
1月前
|
存储 算法 Java
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合,并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构,遍历字符串时将左括号压入栈中,遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
|
2月前
|
算法
两个字符串匹配出最长公共子序列算法
本文介绍了最长公共子序列(LCS)问题的算法实现,通过动态规划方法求解两个字符串的最长公共子序列,并提供了具体的编程实现细节和示例。
97 1
两个字符串匹配出最长公共子序列算法
|
2月前
|
JavaScript
力扣3333.找到初始输入字符串Ⅱ
【10月更文挑战第9天】力扣3333.找到初始输入字符串Ⅱ
37 1
|
2月前
|
算法
每日一道算法题(Leetcode 20)
每日一道算法题(Leetcode 20)
29 2
|
2月前
|
C++
Leetcode第43题(字符串相乘)
本篇介绍了一种用C++实现的字符串表示的非负整数相乘的方法,通过逆向编号字符串,将乘法运算转化为二维数组的累加过程,最后处理进位并转换为字符串结果,解决了两个大数相乘的问题。
25 9
|
2月前
|
算法 C++
Leetcode第八题(字符串转换整数(atoi))
这篇文章介绍了LeetCode上第8题“字符串转换整数(atoi)”的解题思路和C++的实现方法,包括处理前导空格、正负号、连续数字字符以及整数溢出的情况。
21 0
|
2月前
【LeetCode 22】459.重复的子字符串
【LeetCode 22】459.重复的子字符串
31 0
|
2月前
【LeetCode 20】151.反转字符串里的单词
【LeetCode 20】151.反转字符串里的单词
21 0
|
2月前
【LeetCode 19】541.反转字符串II
【LeetCode 19】541.反转字符串II
22 0
|
2月前
【LeetCode 18】6.2.反转字符串
【LeetCode 18】6.2.反转字符串
17 0