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* 算法…...
Python爬虫实战:研究MechanicalSoup库相关技术
一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...
19c补丁后oracle属主变化,导致不能识别磁盘组
补丁后服务器重启,数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后,存在与用户组权限相关的问题。具体表现为,Oracle 实例的运行用户(oracle)和集…...
Admin.Net中的消息通信SignalR解释
定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...
PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建
制造业采购供应链管理是企业运营的核心环节,供应链协同管理在供应链上下游企业之间建立紧密的合作关系,通过信息共享、资源整合、业务协同等方式,实现供应链的全面管理和优化,提高供应链的效率和透明度,降低供应链的成…...
UDP(Echoserver)
网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法:netstat [选项] 功能:查看网络状态 常用选项: n 拒绝显示别名&#…...
服务器硬防的应用场景都有哪些?
服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式,避免服务器受到各种恶意攻击和网络威胁,那么,服务器硬防通常都会应用在哪些场景当中呢? 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...
django filter 统计数量 按属性去重
在Django中,如果你想要根据某个属性对查询集进行去重并统计数量,你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求: 方法1:使用annotate()和Count 假设你有一个模型Item,并且你想…...
新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案
随着新能源汽车的快速普及,充电桩作为核心配套设施,其安全性与可靠性备受关注。然而,在高温、高负荷运行环境下,充电桩的散热问题与消防安全隐患日益凸显,成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...
Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!
一、引言 在数据驱动的背景下,知识图谱凭借其高效的信息组织能力,正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合,探讨知识图谱开发的实现细节,帮助读者掌握该技术栈在实际项目中的落地方法。 …...
今日科技热点速览
🔥 今日科技热点速览 🎮 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售,主打更强图形性能与沉浸式体验,支持多模态交互,受到全球玩家热捧 。 🤖 人工智能持续突破 DeepSeek-R1&…...
