LC926. 将字符串翻转到单调递增(JAVA - 动态规划)
将字符串翻转到单调递增
- 题目描述
- 动态规划
题目描述
难度 - 中等
LC926. 将字符串翻转到单调递增(JAVA - 动态规划)
如果一个二进制字符串,是以一些 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 <= 10^5
s[i] 为 ‘0’ 或 ‘1’

动态规划
单调递增的字符串满足以下性质:
1.首个字符是 0 或 1;
2.其余的每个字符,字符 0 前面的相邻字符一定是 0,字符 1 前面的相邻字符可以是 0 或 1。
我们用动态规划去解答这个题时,每个位置我们都要考虑,其变成0或者1,的情况,最后我们取改变最小的值,
当 1≤i<n 时,考虑下标 i 处的字符。如果下标 i 处的字符是 0,则只有当下标 i−1 处的字符是 0 时才符合单调递增;如果下标 i 处的字符是 1,则下标 i−1 处的字符是 0 或 1 都符合单调递增,此时为了将翻转次数最小化,应分别考虑下标 i−1 处的字符是 0 和 1 的情况下需要的翻转次数,取两者的最小值。
代码演示:
class Solution {public int minFlipsMonoIncr(String s) {int n = s.length();int dp0 = 0;int dp1 = 1;for(int i = 0; i < n;i++){char c = s.charAt(i);int newDp0 = dp0;int newDp1 = Math.min(dp0,dp1);if(c == '1'){newDp0++;}else{newDp1++;}dp0 = newDp0;dp1 = newDp1;}return Math.min(dp0,dp1);}}
相关文章:
LC926. 将字符串翻转到单调递增(JAVA - 动态规划)
将字符串翻转到单调递增 题目描述动态规划 题目描述 难度 - 中等 LC926. 将字符串翻转到单调递增(JAVA - 动态规划) 如果一个二进制字符串,是以一些 0(可能没有 0)后面跟着一些 1(也可能没有 1)的形式组成的࿰…...
【高阶数据结构】哈希的应用 {位图;std::bitset;位图的应用;布隆过滤器;布隆过滤器的应用}
一、位图 1.1 位图概念 面试题 给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在这40亿个数中。【腾讯】 遍历查找:内存中无法存放40亿个整数(约占内存15-16G);时间复杂…...
金融生产存储亚健康治理:升级亚健康 3.0 ,应对万盘规模的挑战
随着集群规模的不断扩大,硬盘数量指数级上升,信创 CPU 和操作系统、硬盘多年老化、物理搬迁等多种复杂因素叠加,为企业的存储亚健康管理增加了新的挑战。 在亚健康 2.0 的基础上,星辰天合在 XSKY SDS V6.2 实现了亚健康 3.0&#…...
C语言自定义类型讲解:结构体,枚举,联合(2)
🐵本篇文章将会对位段、枚举和联合的相关知识进行讲解 1. 位段📚 1.1 什么是位段 位段的声明和结构体类似,但是有两点不同: 1.位段的成员必须是int,unsigned int,signed int (C99之后也可以是其他成员&am…...
AI编程助手 Amazon CodeWhisperer 全面解析与实践
目录 引言Amazon CodeWhisperer简介智能编程助手智能代码建议代码自动补全 提升代码质量代码质量提升安全性检测 支持多平台多语言 用户体验和系统兼容性用户体验文档和学习资源个性化体验系统兼容性 功能全面性和代码质量功能全面性代码生成质量和代码安全性 CodeWhisperer的代…...
利用EXCEL进行XXE攻击
利用EXCEL进行XXE攻击 原因 原因 Microsoft Office从2007版本引入了新的开放的XML文件格式,新的XML文件格式基于压缩的ZIP文件格式规范,由许多部分组成。 我们可以将其解压缩到特定的文件夹中来查看其包含的文件夹和文件,可以发现其中多数是…...
芯片验证就是一次旅行
如果你国庆希望去一个你不曾去过的城市旅行,比如“中国苏州”。对游客来说,它是个蛮大的城市,有许多景点可以游玩,还有许多事情可以做。但实际上,即使最豪也最清闲的游客也很难看苏州的所有方方面面。同样的道理也适用…...
Java深入理解线程的三大特性
目录 1 CPU缓存导致可见性问题2 线程切换导致原子性问题3 性能优化导致有序性问题4 JMM(Java Memory Model)5 volatile6 synchronized 1 CPU缓存导致可见性问题 线程的三大特性: 可见性:Visibility有序性:Ordering原子性:Atomic…...
2025快手校招面试真题汇总及其解答(二)
6. hashmap数据结构 HashMap 是一种散列表,它是一种根据键值对来存储数据的数据结构。HashMap 的特点是插入、查找和删除操作的时间复杂度都是 O(1),因此它是一种非常高效的数据结构。 HashMap 的工作原理是将键值对存储在一个数组中,每个键值对都由一个哈希函数来映射到数…...
PHP生成带中文的图片
imagettftext() 函数是 PHP 中的一个内置函数,用于使用 TrueType 字体将文本写入图像。 句法: 数组imagettftext(资源$image,float $size,float $angle, int $x,int $y,…...
java框架-Dubbo
Dubbo整合Springboot BIO NIO Netty Dubbo 原理 在这里插入图片描述...
Vue+iview 组件中通过v-for循环动态生成form表单进行表单校验
在做项目时,需要根据需要动态添加或新增表单,同时还需要对表单做校验。详情如下图: 刚开始做表单验证的时候,对于这个动态的表单验证有点难搞,试了好几种方法都没有搞定。最后按照下面这种方法实现了,以此…...
sns.load_dataset(“iris“)报错原因探究+解决办法
问题描述 import seaborn as sns # 读取数据 iris sns.load_dataset("iris")在代码中使用了seaborn ,并加载iris数据,结果产生了报错信息如下所示 问题分析 原因很简单,我们使用了sns.load_dataset("iris")来加载数据…...
python回文素数
这能有1和本身整除的整数叫素数;如一个素数从左向右和从右向左是相同的数,则该素数为回文素数。编程求出2-1000内的所有回文素数。 源代码: def sushu(n): for i in range(2,n//21): if n%i 0: return False r…...
纽扣电池16CRF1700.15,16CFR1700.20,ANSI C18.3M如何申请?
随着科技的发展,纽扣电池被广泛应用于小型电子产品,如计算器、电子手表、玩具、医疗设备等。由于其体积小,易于拆卸,也造成了儿童误吞的潜在风险。因此,对于纽扣电池的认证和包装,各国均有相应的规定。 在美…...
10.12广州见 | 第十六届智慧城市大会报名通道全面开启
第十六届中国智慧城市大会 将于10月12日至13日 在广州举办 智慧城市是数字中国、智慧社会的核心载体,是数字时代城市发展的高级形态。由中国服务贸易协会、中国测绘学会、中国遥感委员会主办的第十六届中国智慧城市大会,将以“数实融合开放创新智引未…...
2023-油猴(Tampermonkey)脚本推荐
2023-油猴(Tampermonkey)脚本推荐 知乎增强 链接 https://github.com/XIU2/UserScript https://greasyfork.org/zh-CN/scripts/419081 介绍 移除登录弹窗、屏蔽首页视频、默认收起回答、快捷收起回答/评论(左键两侧)、快捷回…...
某度sign参数逆向
文章目录 前文分析完整代码结尾 前文 本文章中所有内容仅供学习交流,严禁用于商业用途和非法用途,否则由此产生的一切后果均与作者无关,若有侵权,请联系我立即删除! 分析 经过我们几次抓包,测试…...
【选型】JAVA生成PPT及选型
可以使用的框架(类库):POI,OpenOffice/LibreOffice,Aspose.Slides,Java开源报表工具(JasperReports,BIRT等)。 具体如下: 方案优点缺点Apache POI- 开源免费- 可完全控制PPT生成- …...
LPA*算法图文详解
之前我们看过了A* 算法,知道了A* 算法的基本原理,但是A* 算法的缺陷也很明显:它是离线的路径规划算法,只能一次规划出路径,但是后面路径被改变的话就无法生效了。针对这个问题,人们研究出了D* 算法。D* 算法…...
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造,完美适配AGV和无人叉车。同时,集成以太网与语音合成技术,为各类高级系统(如MES、调度系统、库位管理、立库等)提供高效便捷的语音交互体验。 L…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用
1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...
全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比
目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec? IPsec VPN 5.1 IPsec传输模式(Transport Mode) 5.2 IPsec隧道模式(Tunne…...
OPENCV形态学基础之二腐蚀
一.腐蚀的原理 (图1) 数学表达式:dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一,腐蚀跟膨胀属于反向操作,膨胀是把图像图像变大,而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...
算法打卡第18天
从中序与后序遍历序列构造二叉树 (力扣106题) 给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。 示例 1: 输入:inorder [9,3,15,20,7…...
在 Visual Studio Code 中使用驭码 CodeRider 提升开发效率:以冒泡排序为例
目录 前言1 插件安装与配置1.1 安装驭码 CodeRider1.2 初始配置建议 2 示例代码:冒泡排序3 驭码 CodeRider 功能详解3.1 功能概览3.2 代码解释功能3.3 自动注释生成3.4 逻辑修改功能3.5 单元测试自动生成3.6 代码优化建议 4 驭码的实际应用建议5 常见问题与解决建议…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现指南针功能
指南针功能是许多位置服务应用的基础功能之一。下面我将详细介绍如何在HarmonyOS 5中使用DevEco Studio实现指南针功能。 1. 开发环境准备 确保已安装DevEco Studio 3.1或更高版本确保项目使用的是HarmonyOS 5.0 SDK在项目的module.json5中配置必要的权限 2. 权限配置 在mo…...
高保真组件库:开关
一:制作关状态 拖入一个矩形作为关闭的底色:44 x 22,填充灰色CCCCCC,圆角23,边框宽度0,文本为”关“,右对齐,边距2,2,6,2,文本颜色白色FFFFFF。 拖拽一个椭圆,尺寸18 x 18,边框为0。3. 全选转为动态面板状态1命名为”关“。 二:制作开状态 复制关状态并命名为”开…...
STL 2迭代器
文章目录 1.迭代器2.输入迭代器3.输出迭代器1.插入迭代器 4.前向迭代器5.双向迭代器6.随机访问迭代器7.不同容器返回的迭代器类型1.输入 / 输出迭代器2.前向迭代器3.双向迭代器4.随机访问迭代器5.特殊迭代器适配器6.为什么 unordered_set 只提供前向迭代器? 1.迭代器…...
【立体匹配】:双目立体匹配SGBM:(1)运行
注:这是一个专题,我会一步步介绍SGBM的实现,按照我的使用和优化过程逐步改善算法,附带实现方法 系列文章【立体匹配】:双目立体匹配SGBM:(1)运行 【立体匹配】:双目立体匹…...
