首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >golang 刷leetcode:将字符串翻转到单调递增

golang 刷leetcode:将字符串翻转到单调递增

作者头像
golangLeetcode
发布于 2022-08-02 11:51:18
发布于 2022-08-02 11:51:18
29500
代码可运行
举报
运行总次数:0
代码可运行

如果一个二进制字符串,是以一些 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'

解题思路:

1,本题很容拆分子问题

假设dp0[i],表示i位置是0,也就是0~i位置都是0 需要的最小翻转次数;假设dp1[i],表示i位置是1,也就是0~k位置为0,k~i 位置为i需要的最小翻转次数

2,那么对于i+1位置,如果s[i+1]=='0',

dp0[i+1]=dp0[i],都是0,不需要翻转

dp1[i+1]=dp1'[i]+1,需要翻转一次,变成1

3,对于i+1位置,如果s[i]=='1'

dp0[i+1]=dp0[i]+1,需要翻转一次,变成0

dp1[i+1]=dp1[i]',都是1,不需要翻转

4,对于i+1位置,每次计算dp0就是统计1的个数;

5,对于i+1位置,计算dp1,需要看下k到i位置,变成0还是1,谁的代价更小

即上面的dp1'[i]=min(dp1[i],dp0[i]

6,由于每个位置只依赖前一个位置,可以将一维动态规划压缩到常数

代码实现

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
func minFlipsMonoIncr(s string) int {
   dp0,dp1:=0,0
   for _,v:=range s{
       dp1=min(dp0,dp1)
       if v=='1'{
          dp0++
       }else{
          dp1++
       }
   }
   return min(dp0,dp1)
}

func min(a,b int)int{
    if a<b{
        return a
    }
    return b
}
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2022-06-11,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 golang算法架构leetcode技术php 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
LeetCode 926. 将字符串翻转到单调递增(动态规划)
如果一个由 '0' 和 '1' 组成的字符串,是以一些 '0'(可能没有 '0')后面跟着一些 '1'(也可能没有 '1')的形式组成的,那么该字符串是单调递增的。
Michael阿明
2021/02/19
5250
每日算法系列【LeetCode 926】将字符串翻转到单调递增
如果一个由 '0' 和 '1' 组成的字符串,是以一些 '0'(可能没有 '0')后面跟着一些 '1'(也可能没有 '1')的形式组成的,那么该字符串是单调递增的。
godweiyang
2020/03/24
7030
算法-动态规划
动态规划是一种解决多阶段决策过程最优化问题的数学方法。通常需要保存决策路径的问题用回溯法,而只是求最优解的时候选择动态规划。
宅蓝三木
2024/10/09
2830
golang刷leetcode:最大波动的子字符串
字符串的 波动 定义为子字符串中出现次数 最多 的字符次数与出现次数 最少 的字符次数之差。
golangLeetcode
2022/08/02
3160
LeetCode 1758. 生成交替二进制字符串的最少操作数(DP)
给你一个仅由字符 ‘0’ 和 ‘1’ 组成的字符串 s 。 一步操作中,你可以将任一 ‘0’ 变成 ‘1’ ,或者将 ‘1’ 变成 ‘0’ 。
Michael阿明
2021/09/07
3050
2025-07-10:字符相同的最短子字符串Ⅰ。用go语言,给定一个长度为 n 的二进制字符串 s 和一个允许执行的最大操作次数
2025-07-10:字符相同的最短子字符串Ⅰ。用go语言,给定一个长度为 n 的二进制字符串 s 和一个允许执行的最大操作次数 numOps。
福大大架构师每日一题
2025/07/10
1180
2025-07-10:字符相同的最短子字符串Ⅰ。用go语言,给定一个长度为 n 的二进制字符串 s 和一个允许执行的最大操作次数
LeetCode-面试题46-把数字翻译成字符串
给定一个数字,我们按照如下规则把它翻译为字符串:0 翻译成 “a” ,1 翻译成 “b”,……,11 翻译成 “l”,……,25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数,用来计算一个数字有多少种不同的翻译方法。
benym
2022/07/14
2870
Leetcode | 第C节:字符串综合题(2)
东京奥运会圆满收官!当然我自己也将迎来留学前的最后准备,所以更新速度可能还是会比较慢……但还好,大部分的内容都已经在之前写的差不多了,也希望最后这几篇我也能够尽快更完,当然也希望大家可以谅解~
学弱猹
2021/09/07
7910
golang刷leetcode:检查是否有合法括号字符串路径
一个括号字符串是一个 非空 且只包含 '(' 和 ')' 的字符串。如果下面 任意 条件为 真 ,那么这个括号字符串就是 合法的 。
golangLeetcode
2022/08/02
1.2K0
【刷穿 LeetCode】978. 最长湍流子数组(中等)
当 A 的子数组 A[i], A[i+1], ..., A[j] 满足下列条件时,我们称其为湍流子数组:
宫水三叶的刷题日记
2021/02/20
3480
Leetcode 【48、926、1014】
如果使用常规方法,需要找规律得到每个位置变换后的位置,比较繁琐。一种巧妙的方法是将图像旋转 90° 等价于先将图像转置,然后再将每一行数字反转。因此,需要遍历两次 matrix,先转置再反转每一行,时间复杂度为 O(n)。
echobingo
2019/06/24
4860
2025-03-30:统计满足 K 约束的子字符串数量Ⅱ。用go语言,给定一个二进制字符串 s 和一个整数 k,还有一个二维整数
2025-03-30:统计满足 K 约束的子字符串数量Ⅱ。用go语言,给定一个二进制字符串 s 和一个整数 k,还有一个二维整数数组 queries,其中每个元素 queries[i] = [li, ri] 代表一个查询。
福大大架构师每日一题
2025/03/31
1040
2025-03-30:统计满足 K 约束的子字符串数量Ⅱ。用go语言,给定一个二进制字符串 s 和一个整数 k,还有一个二维整数
golang刷leetcode:贴纸拼词
您想要拼写出给定的字符串 target ,方法是从收集的贴纸中切割单个字母并重新排列它们。如果你愿意,你可以多次使用每个贴纸,每个贴纸的数量是无限的。
golangLeetcode
2022/08/02
3810
LeetCode官方举办!279场周赛题解合集
今天我们来看上周日进行的LeetCode第279场周赛,这也是LeetCode官方举办的招聘周赛。
TechFlow-承志
2022/09/22
3630
LeetCode官方举办!279场周赛题解合集
LeetCode 0132. 分割回文串 II[动态规划详解]
记 f(i) 为字符串 s0,i 切割的最小分割次数,则 f(i) 的状态转移方程为:
Yano_nankai
2021/04/12
3450
LeetCode 0132. 分割回文串 II[动态规划详解]
用javascript分类刷leetcode20.字符串(图文视频讲解)2
方法1.截取字符串,循环字符串,遇到#就截掉最后一个字符,循环完毕之后,最后比较两个去除掉#退格之后的字符串是否相等,时间复杂度O(m+n),m、n是两个字符串的长度。空间复杂度O(1)
hellocoder2028
2023/01/04
8440
2025-04-23:形成目标字符串需要的最少字符串数Ⅱ。用go语言,给定一个字符串数组 words 和一个目标字符串 targ
2025-04-23:形成目标字符串需要的最少字符串数Ⅱ。用go语言,给定一个字符串数组 words 和一个目标字符串 target。
福大大架构师每日一题
2025/04/23
1010
2025-04-23:形成目标字符串需要的最少字符串数Ⅱ。用go语言,给定一个字符串数组 words 和一个目标字符串 targ
LeetCode 第 199 场周赛(757/5231,前14.5%)
全国排名: 757 / 5231,14.5%;全球排名: 0 / 1,00.0%
Michael阿明
2021/02/19
4190
LeetCode 738. 单调递增的数字(贪心)
给定一个非负整数 N,找出小于或等于 N 的最大的整数,同时这个整数需要满足其各个位数上的数字是单调递增。
Michael阿明
2020/07/13
1.1K0
LeetCode 738. 单调递增的数字(贪心)
LeetCode 第 27 场双周赛(1125/1966,前57.2%)
全国排名:1125 / 1966,57.2%;全球排名:4236 / 7924,53.5%
Michael阿明
2020/07/13
4270
LeetCode 第 27 场双周赛(1125/1966,前57.2%)
推荐阅读
相关推荐
LeetCode 926. 将字符串翻转到单调递增(动态规划)
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档