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* 算法…...
7.4.分块查找
一.分块查找的算法思想: 1.实例: 以上述图片的顺序表为例, 该顺序表的数据元素从整体来看是乱序的,但如果把这些数据元素分成一块一块的小区间, 第一个区间[0,1]索引上的数据元素都是小于等于10的, 第二…...
React hook之useRef
React useRef 详解 useRef 是 React 提供的一个 Hook,用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途,下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...
线程同步:确保多线程程序的安全与高效!
全文目录: 开篇语前序前言第一部分:线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分:synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分ÿ…...
Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务
通过akshare库,获取股票数据,并生成TabPFN这个模型 可以识别、处理的格式,写一个完整的预处理示例,并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务,进行预测并输…...
python如何将word的doc另存为docx
将 DOCX 文件另存为 DOCX 格式(Python 实现) 在 Python 中,你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是,.doc 是旧的 Word 格式,而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...
【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)
要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况,可以通过以下几种方式模拟或触发: 1. 增加CPU负载 运行大量计算密集型任务,例如: 使用多线程循环执行复杂计算(如数学运算、加密解密等)。运行图…...
【Go语言基础【12】】指针:声明、取地址、解引用
文章目录 零、概述:指针 vs. 引用(类比其他语言)一、指针基础概念二、指针声明与初始化三、指针操作符1. &:取地址(拿到内存地址)2. *:解引用(拿到值) 四、空指针&am…...
从 GreenPlum 到镜舟数据库:杭银消费金融湖仓一体转型实践
作者:吴岐诗,杭银消费金融大数据应用开发工程师 本文整理自杭银消费金融大数据应用开发工程师在StarRocks Summit Asia 2024的分享 引言:融合数据湖与数仓的创新之路 在数字金融时代,数据已成为金融机构的核心竞争力。杭银消费金…...
Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统
💝💝💝欢迎莅临我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:「storms…...
【Post-process】【VBA】ETABS VBA FrameObj.GetNameList and write to EXCEL
ETABS API实战:导出框架元素数据到Excel 在结构工程师的日常工作中,经常需要从ETABS模型中提取框架元素信息进行后续分析。手动复制粘贴不仅耗时,还容易出错。今天我们来用简单的VBA代码实现自动化导出。 🎯 我们要实现什么? 一键点击,就能将ETABS中所有框架元素的基…...
