2024.1.11力扣每日一题——构造有效字符串的最少插入数
2024.1.11
- 题目来源
- 我的题解
- 方法一 暴力模拟
- 方法二 动态规划
- 方法三 直接拼接
- 方法四 计算组数
题目来源
力扣每日一题;题序:2645
我的题解
方法一 暴力模拟
直接模拟,根据题意可知 若是abc则不用插入,若是ab,ac,bc这需要 插入一个字符,其他的则需要插入两个字符。因此使用String的替换功能,先将word中的所有abc替换成 _ ,然后再分别将ab,ac,bc从左到右替换成 _ ,最后统计剩下的字符中 a b c的数量
时间复杂度:O( n 2 n^2 n2) n是字符串的长度。除了遍历的O(n),还有替换方法内部的O(n)
空间复杂度:O(1)
public int addMinimum(String word) {word=word.replaceAll("abc","_");int n=word.length();if(n==0)return 0;int res=0;while(word.contains("ab")){res++;word=word.replaceFirst("ab","_");}while(word.contains("bc")){res++;word=word.replaceFirst("bc","_");}while(word.contains("ac")){res++;word=word.replaceFirst("ac","_");}for(int i=0;i<word.length();i++){char ch=word.charAt(i);if(ch>='a'&&ch<='c'){res+=2;}}return res;
}
方法二 动态规划
定义dp[i]状态表示前i个字符凑成若干个abc所需插入的字符数,则转移过程:
- 若第i个字符单独在一组abc中,则dp[i]=dp[i-1]+2
- 若word[i]>word[i-1]则表示word[i]和word[i-1]在一组abc中,则dp[i]=dp[i-1]-1
时间复杂度:O(n)
空间复杂度:O(n)
public int addMinimum(String word) {int n=word.length();int[] dp=new int[n+1];for(int i=0;i<n;i++){dp[i+1]=dp[i]+2;if(i<n-1&&word.charAt(i+1)>word.charAt(i)){dp[i+1]=dp[i]-1;}}return dp[n];
}
当然,可以发现转移至于i-1状态有关,所以可以使用滚动数组优化空间
public int addMinimum(String word) {int n=word.length();int dp_0=0;int dp_1=0;for(int i=0;i<n;i++){dp_1=dp_0+2;if(i<n-1&&word.charAt(i+1)>word.charAt(i)){dp_1=dp_0-1;}dp_0=dp_1;}return dp_1;
}
方法三 直接拼接
参考:官方题解
当前字符小于等于前面字符说明它们一定不在同一组 abc 中,只需要添置若干字符过渡这两者即可。例如 b前面是 c,则需要在中间添置 a,又例如 b 前面是 b,则需要在中间添置 ca。
以上两种情况可以用一个模型来表示,设当前字符是 x,前面字符是 y,那么需要添置的字符个数为 (x−y−1+3)mod 3。其中 +3 再对 3取模,可以应对 x 小于等于 y 的情况。
最后还需要处理头尾两个字符,word[0] 前面添置 word[0]−‘a′ 个字符,word[n−1]后面添置 ‘c′−word[n−1]个字符。两个可以合并为 word[0]−word[n−1]+2
时间复杂度:O(n)
空间复杂度:O(1)
public int addMinimum(String word) {int n=word.length();int res=0;if(n==1)return 2;res+=word.charAt(0)-word.charAt(n-1)+2;for(int i=0;i<n-1;i++){int count=word.charAt(i+1)-word.charAt(i)-1+3;res+=count%3;}return res;}
方法四 计算组数
计算递增序列的组——也就是每一个递增序列都是一个组,然后使用一个变量count记录当前递增序列的长度,需要插入的字符数=3-count。在不满足递增的时候才会计算需要插入的字符数,并且重置count。
时间复杂度:O(n)。n是word的长度
空间复杂度:O(1)
public int addMinimum(String word) {int n=word.length();if(n==1){return 2;}int res=0;int count=1;for(int i=0;i<n-1;i++){if(word.charAt(i+1)<=word.charAt(i)){res+=3-count;count=1;}else{count++;}}return res+(3-count);}
有任何问题,欢迎评论区交流,欢迎评论区提供其它解题思路(代码),也可以点个赞支持一下作者哈😄~
相关文章:
2024.1.11力扣每日一题——构造有效字符串的最少插入数
2024.1.11 题目来源我的题解方法一 暴力模拟方法二 动态规划方法三 直接拼接方法四 计算组数 题目来源 力扣每日一题;题序:2645 我的题解 方法一 暴力模拟 直接模拟,根据题意可知 若是abc则不用插入,若是ab,ac,bc这需要 插入一…...
软件测试|如何使用Selenium处理隐藏元素
简介 我们在使用selenium进行web自动化测试时,有时候会遇到元素被隐藏,从而无法对元素进行操作,导致我们的用例报错的情况。当我们遇到元素被隐藏的情况时,需要先对隐藏的元素进行处理,才能继续进行我们的操作&#x…...
第三次面试总结 - 吉云集团 - 全栈开发
🧸欢迎来到dream_ready的博客,📜相信您对专栏 “本人真实面经” 很感兴趣o (ˉ▽ˉ;) 专栏 —— 本人真实面经,更多真实面试经验,中大厂面试总结等您挖掘 目录 总结(非详细) 面试内…...
buuctf-Misc 题目解答分解118-120
118.[INSHack2017]sanity 打开压缩包就是一个md 文件 typora 打开 发现flag INSA{Youre_sane_Good_for_you} 119.粽子的来历 解压压缩包 ,得到文件夹如下 用010 editor 打开 我是A.doc 这个有些可以 都改成FF 保存 然后再次打开 docx 文件就发现了屈原的诗 其他b…...
Hive数据定义(1)
hive数据定义是hive的基础知识,所包含的知识点有:数据仓库的创建、数据仓库的查询、数据仓库的修改、数据仓库的删除、表的创建、表的删除、内部表、外部表、分区表、桶表、表的修改、视图。本篇文章先介绍:数据仓库的创建、数据仓库的查询、…...
golang 反序列化出现json: cannot unmarshal string into Go value of type model.Phone
项目场景: 今天在项目公关的过程中,需要对interface{}类型进行转换为具体结构体 问题描述 很自然的用到了resultBytes, _ : json.Marshal(result),然后对resultBytes进行反序列化转换为对应的结构体err : json.Unmarshal(resultBytes, &…...
【闯关练习】—— 1400分(构造)
🌏博客主页:PH_modest的博客主页 🚩当前专栏:cf闯关练习 💌其他专栏: 🔴每日一题 🟡 C跬步积累 🟢 C语言跬步积累 🌈座右铭:广积粮,缓…...
Qt QProgressBar进度条控件
文章目录 1 属性和方法1.1 值1.2 方向1.3 外观1.4 信号和槽 2 实例2.1 布局2.2 代码实现 QProgressBar是进度条控件,进度条用来指示任务的完成情况 1 属性和方法 QProgressBar有很多属性,完整的可查看帮助文档。这里以QProgressBar为例,列出…...
【新】Unity Meta Quest MR 开发(一):Passthrough 透视配置
文章目录 📕教程说明📕配置透视的串流调试功能📕第一步:设置 OVRManager📕第二步:添加 OVRPassthroughLayer 脚本📕第三步:在场景中添加虚拟物体📕第四步:设置…...
快速排序【hoare版本】【挖坑法】【双指针法】(数据结构)
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法,其基本思想为:任取待排序元素序列中 的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均…...
class_5:在c++中一个类包含另一个类的对象叫做组合
#include <iostream> using namespace std;class Wheel{ public://成员数据string brand; //品牌int year; //年限//真正的成员函数void printWheelInfo(); //声明成员函数 };void Wheel::printWheelInfo() {cout<<"我的轮胎品牌是:"<…...
Linux - No space left on device
问题描述 No space left on device 原因分析 说明在服务器设备上的存储空间已经满了,不能再上传或者新建文件夹或者文件等。 解决方案 确认查看服务器系统的磁盘使用情况是否是真的已经没有剩余空间,复制下面命令在服务器上运行,然后发现如果…...
STC8H8K蓝牙智能巡线小车——2. 点亮左右转弯灯与危险报警灯
任务调用示例 RTX 51 TNY 可做多任务调度,API较为简单。 /* 接口API */// 创建任务 extern unsigned char os_create_task (unsigned char task_id); // 结束任务 extern unsigned char os_delete_task (unsigned char task_id);// 等待 extern unsig…...
【微信小程序独立开发 3】个人资料页面编写
这一节完成用户个人信息昵称的填写和获取 上节编写完成后的页面如下所示: 首先进行用户昵称编辑功能的编写,铲屎官昵称采用了navigator标签,当点击昵称时会自动跳转到昵称编辑页面。 首先输入昵称编辑界面的导航栏名称 {"usingCompone…...
Linux笔记:Linux中的文件系统权限
在Red Hat Enterprise Linux 或其他类似的Linux发行版中,全局umask设置通常在几个不同的系统级配置文件中定义。以下是一些可能设置umask的地方: (1)/etc/profile: 这是为系统上的所有用户设置全局环境变量和启动程序的地方。通…...
Android基于Matrix绘制PaintDrawable设置BitmapShader,以手指触点为中心显示原图的圆切图,Kotlin(4)
Android基于Matrix绘制PaintDrawable设置BitmapShader,以手指触点为中心显示原图的圆切图,Kotlin(4) 这篇 Android基于Matrix绘制PaintDrawable设置BitmapShader,以手指触点为中心显示原图像圆图,Kotlin&am…...
WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!
问题背景 当我们尝试通过SSH(Secure Shell)连接到远程服务器时,有时会遇到一个警告信息:“WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!”。这个消息表明SSH客户端检测到远程主机的身份(即其SSH密钥)…...
深入理解JVM虚拟机第三十九篇:JVM中新生代和老年代相关参数设置
😉😉 欢迎加入我们的学习交流群呀! ✅✅1:这是孙哥suns给大家的福利! ✨✨2:我们免费分享Netty、Dubbo、k8s、Mybatis、Spring、Security、Docker、Grpc、消息中间件、Rpc、SpringCloud等等很多应用和源码级别高质量视频和笔记资料,你想学的我们这里都有! 🥭🥭3:…...
打造创新的金融数据平台,加速数字化和智能化转型丨PingCAP 官网金融行业专区上线
自诞生以来,TiDB 的原生分布式架构在强一致性、高可用性和可扩展性等方面与金融级业务需求高度契合,早期版本即为包括北京银行在内的金融用户提供服务。 TiDB 的核心能力始终源自与中国金融用户的共同创造。作为金融级分布式数据库,TiDB 在国…...
记ubuntu2004通过NetworkManager修改网络的优先级
这里写自定义目录标题 前言步骤 前言 起因在于万恶的校园网,突然台式有线死活没法认证(感觉是IP冲突了?另外一台电脑同样的系统就没有问题,连路由器WIFI也是可以的,路由器设置的是桥接模式,有没有大佬提供…...
五年级数学知识边界总结思考-下册
目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解:由来、作用与意义**一、知识点核心内容****二、知识点的由来:从生活实践到数学抽象****三、知识的作用:解决实际问题的工具****四、学习的意义:培养核心素养…...
《通信之道——从微积分到 5G》读书总结
第1章 绪 论 1.1 这是一本什么样的书 通信技术,说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号(调制) 把信息从信号中抽取出来&am…...
srs linux
下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935,SRS管理页面端口是8080,可…...
Python爬虫(二):爬虫完整流程
爬虫完整流程详解(7大核心步骤实战技巧) 一、爬虫完整工作流程 以下是爬虫开发的完整流程,我将结合具体技术点和实战经验展开说明: 1. 目标分析与前期准备 网站技术分析: 使用浏览器开发者工具(F12&…...
DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI
前一阵子在百度 AI 开发者大会上,看到基于小智 AI DIY 玩具的演示,感觉有点意思,想着自己也来试试。 如果只是想烧录现成的固件,乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外,还提供了基于网页版的 ESP LA…...
工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配
AI3D视觉的工业赋能者 迁移科技成立于2017年,作为行业领先的3D工业相机及视觉系统供应商,累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成,通过稳定、易用、高回报的AI3D视觉系统,为汽车、新能源、金属制造等行…...
蓝桥杯 冶炼金属
原题目链接 🔧 冶炼金属转换率推测题解 📜 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V,是一个正整数,表示每 V V V 个普通金属 O O O 可以冶炼出 …...
HDFS分布式存储 zookeeper
hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架,允许使用简单的变成模型跨计算机对大型集群进行分布式处理(1.海量的数据存储 2.海量数据的计算)Hadoop核心组件 hdfs(分布式文件存储系统)&a…...
C#中的CLR属性、依赖属性与附加属性
CLR属性的主要特征 封装性: 隐藏字段的实现细节 提供对字段的受控访问 访问控制: 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性: 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑: 可以…...
AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机
这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机,因为在使用过程中发现 Airsim 对外部监控相机的描述模糊,而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置,最后在源码示例中找到了,所以感…...
