开发者社区> 游客z3jcatjk57fiu> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

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

简介: 如果一个由 '0' 和 '1' 组成的字符串,是以一些 '0'(可能没有 '0')后面跟着一些 '1'(也可能没有 '1')的形式组成的,那么该字符串是单调递增的。 我们给出一个由字符 '0' 和 '1' 组成的字符串 S,我们可以将任何 '0' 翻转为 '1' 或者将 '1' 翻转为 '0'。 返回使 S 单调递增的最小翻转次数。
+关注继续查看

题目描述


如果一个由 '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 的数量。


image.png

代码


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

image.png

作者简介:godweiyang知乎同名华东师范大学计算机系硕士在读,方向自然语言处理与深度学习喜欢与人分享技术与知识,期待与你的进一步交流~


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
每日算法系列【LeetCode 927】三等分
给定一个由 0 和 1 组成的数组 A,将数组分成 3 个非空的部分,使得所有这些部分表示相同的二进制值。
32 0
LeetCode 709. 转换成小写字母 | 算法-从菜鸟开始
在LeetCode中有一道这样的题目,将字符串中的大写字母转换成相同的小写字母,要求稍微简单了一些,今天我们把他升级一下,要求改成将大写字母转为对应的小写字母,将小写字母转为对应的大写字母。 看看完整的题目描述
16 0
Leetcode --- 字符串系列3(面试篇)
Leetcode --- 字符串系列3(面试篇)
29 0
leetcode算法160.相交链表
当给你两个单链表的头节点 headA 和 headB ,如何找出并返回两个单链表相交的起始节点?本文带大家解决这个问题。
14 0
LeetCode 训练场:226. 翻转二叉树
LeetCode 训练场:226. 翻转二叉树
24 0
LeetCode刷题226-简单-翻转二叉树
LeetCode刷题226-简单-翻转二叉树
36 0
LeetCode——K个一组翻转链表(三指针)
LeetCode——K个一组翻转链表(三指针)
31 0
[leetcode/lintcode 题解] 阿里算法面试题:猜数字游戏
[leetcode/lintcode 题解] 阿里算法面试题:猜数字游戏
155 0
[leetcode/lintcode 题解] 字节跳动面试题:01交换
[leetcode/lintcode 题解] 字节跳动面试题:01交换
178 0
[leetcode/lintcode 题解] 阿里算法面试真题:交叉字符串
[leetcode/lintcode 题解] 阿里算法面试真题:交叉字符串
346 0
217
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载