当前位置: 首页 > news >正文

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 题目来源我的题解方法一 暴力模拟方法二 动态规划方法三 直接拼接方法四 计算组数 题目来源 力扣每日一题&#xff1b;题序&#xff1a;2645 我的题解 方法一 暴力模拟 直接模拟&#xff0c;根据题意可知 若是abc则不用插入&#xff0c;若是ab,ac,bc这需要 插入一…...

软件测试|如何使用Selenium处理隐藏元素

简介 我们在使用selenium进行web自动化测试时&#xff0c;有时候会遇到元素被隐藏&#xff0c;从而无法对元素进行操作&#xff0c;导致我们的用例报错的情况。当我们遇到元素被隐藏的情况时&#xff0c;需要先对隐藏的元素进行处理&#xff0c;才能继续进行我们的操作&#x…...

第三次面试总结 - 吉云集团 - 全栈开发

&#x1f9f8;欢迎来到dream_ready的博客&#xff0c;&#x1f4dc;相信您对专栏 “本人真实面经” 很感兴趣o (ˉ▽ˉ&#xff1b;) 专栏 —— 本人真实面经&#xff0c;更多真实面试经验&#xff0c;中大厂面试总结等您挖掘 目录 总结&#xff08;非详细&#xff09; 面试内…...

buuctf-Misc 题目解答分解118-120

118.[INSHack2017]sanity 打开压缩包就是一个md 文件 typora 打开 发现flag INSA{Youre_sane_Good_for_you} 119.粽子的来历 解压压缩包 &#xff0c;得到文件夹如下 用010 editor 打开 我是A.doc 这个有些可以 都改成FF 保存 然后再次打开 docx 文件就发现了屈原的诗 其他b…...

Hive数据定义(1)

hive数据定义是hive的基础知识&#xff0c;所包含的知识点有&#xff1a;数据仓库的创建、数据仓库的查询、数据仓库的修改、数据仓库的删除、表的创建、表的删除、内部表、外部表、分区表、桶表、表的修改、视图。本篇文章先介绍&#xff1a;数据仓库的创建、数据仓库的查询、…...

golang 反序列化出现json: cannot unmarshal string into Go value of type model.Phone

项目场景&#xff1a; 今天在项目公关的过程中&#xff0c;需要对interface{}类型进行转换为具体结构体 问题描述 很自然的用到了resultBytes, _ : json.Marshal(result)&#xff0c;然后对resultBytes进行反序列化转换为对应的结构体err : json.Unmarshal(resultBytes, &…...

【闯关练习】—— 1400分(构造)

&#x1f30f;博客主页&#xff1a;PH_modest的博客主页 &#x1f6a9;当前专栏&#xff1a;cf闯关练习 &#x1f48c;其他专栏&#xff1a; &#x1f534;每日一题 &#x1f7e1; C跬步积累 &#x1f7e2; C语言跬步积累 &#x1f308;座右铭&#xff1a;广积粮&#xff0c;缓…...

Qt QProgressBar进度条控件

文章目录 1 属性和方法1.1 值1.2 方向1.3 外观1.4 信号和槽 2 实例2.1 布局2.2 代码实现 QProgressBar是进度条控件&#xff0c;进度条用来指示任务的完成情况 1 属性和方法 QProgressBar有很多属性&#xff0c;完整的可查看帮助文档。这里以QProgressBar为例&#xff0c;列出…...

【新】Unity Meta Quest MR 开发(一):Passthrough 透视配置

文章目录 &#x1f4d5;教程说明&#x1f4d5;配置透视的串流调试功能&#x1f4d5;第一步&#xff1a;设置 OVRManager&#x1f4d5;第二步&#xff1a;添加 OVRPassthroughLayer 脚本&#x1f4d5;第三步&#xff1a;在场景中添加虚拟物体&#x1f4d5;第四步&#xff1a;设置…...

快速排序【hoare版本】【挖坑法】【双指针法】(数据结构)

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法&#xff0c;其基本思想为&#xff1a;任取待排序元素序列中 的某元素作为基准值&#xff0c;按照该排序码将待排序集合分割成两子序列&#xff0c;左子序列中所有元素均小于基准值&#xff0c;右子序列中所有元素均…...

class_5:在c++中一个类包含另一个类的对象叫做组合

#include <iostream> using namespace std;class Wheel{ public://成员数据string brand; //品牌int year; //年限//真正的成员函数void printWheelInfo(); //声明成员函数 };void Wheel::printWheelInfo() {cout<<"我的轮胎品牌是&#xff1a;"<…...

Linux - No space left on device

问题描述 No space left on device 原因分析 说明在服务器设备上的存储空间已经满了&#xff0c;不能再上传或者新建文件夹或者文件等。 解决方案 确认查看服务器系统的磁盘使用情况是否是真的已经没有剩余空间&#xff0c;复制下面命令在服务器上运行&#xff0c;然后发现如果…...

STC8H8K蓝牙智能巡线小车——2. 点亮左右转弯灯与危险报警灯

任务调用示例 RTX 51 TNY 可做多任务调度&#xff0c;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】个人资料页面编写

这一节完成用户个人信息昵称的填写和获取 上节编写完成后的页面如下所示&#xff1a; 首先进行用户昵称编辑功能的编写&#xff0c;铲屎官昵称采用了navigator标签&#xff0c;当点击昵称时会自动跳转到昵称编辑页面。 首先输入昵称编辑界面的导航栏名称 {"usingCompone…...

Linux笔记:Linux中的文件系统权限

在Red Hat Enterprise Linux 或其他类似的Linux发行版中&#xff0c;全局umask设置通常在几个不同的系统级配置文件中定义。以下是一些可能设置umask的地方&#xff1a; &#xff08;1&#xff09;/etc/profile: 这是为系统上的所有用户设置全局环境变量和启动程序的地方。通…...

Android基于Matrix绘制PaintDrawable设置BitmapShader,以手指触点为中心显示原图的圆切图,Kotlin(4)

Android基于Matrix绘制PaintDrawable设置BitmapShader&#xff0c;以手指触点为中心显示原图的圆切图&#xff0c;Kotlin&#xff08;4&#xff09; 这篇 Android基于Matrix绘制PaintDrawable设置BitmapShader&#xff0c;以手指触点为中心显示原图像圆图&#xff0c;Kotlin&am…...

WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!

问题背景 当我们尝试通过SSH&#xff08;Secure Shell&#xff09;连接到远程服务器时&#xff0c;有时会遇到一个警告信息&#xff1a;“WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!”。这个消息表明SSH客户端检测到远程主机的身份&#xff08;即其SSH密钥&#xff09…...

深入理解JVM虚拟机第三十九篇:JVM中新生代和老年代相关参数设置

😉😉 欢迎加入我们的学习交流群呀! ✅✅1:这是孙哥suns给大家的福利! ✨✨2:我们免费分享Netty、Dubbo、k8s、Mybatis、Spring、Security、Docker、Grpc、消息中间件、Rpc、SpringCloud等等很多应用和源码级别高质量视频和笔记资料,你想学的我们这里都有! 🥭🥭3:…...

打造创新的金融数据平台,加速数字化和智能化转型丨PingCAP 官网金融行业专区上线

自诞生以来&#xff0c;TiDB 的原生分布式架构在强一致性、高可用性和可扩展性等方面与金融级业务需求高度契合&#xff0c;早期版本即为包括北京银行在内的金融用户提供服务。 TiDB 的核心能力始终源自与中国金融用户的共同创造。作为金融级分布式数据库&#xff0c;TiDB 在国…...

记ubuntu2004通过NetworkManager修改网络的优先级

这里写自定义目录标题 前言步骤 前言 起因在于万恶的校园网&#xff0c;突然台式有线死活没法认证&#xff08;感觉是IP冲突了&#xff1f;另外一台电脑同样的系统就没有问题&#xff0c;连路由器WIFI也是可以的&#xff0c;路由器设置的是桥接模式&#xff0c;有没有大佬提供…...

Spring Framework测试框架完整指南:从单元测试到集成测试的10个最佳实践

Spring Framework测试框架完整指南&#xff1a;从单元测试到集成测试的10个最佳实践 【免费下载链接】spring-framework spring-projects/spring-framework: 一个基于 Java 的开源应用程序框架&#xff0c;用于构建企业级 Java 应用程序。适合用于构建各种企业级 Java 应用程序…...

K8s Ingress实战:如何为静态资源开启Gzip压缩和Cache Control(附完整ConfigMap配置)

Kubernetes Ingress高级配置&#xff1a;静态资源Gzip压缩与缓存策略实战指南 在当今快节奏的数字化体验中&#xff0c;网页加载速度直接影响用户留存率和转化率。根据行业研究&#xff0c;页面加载时间每增加1秒&#xff0c;可能导致转化率下降7%。作为Kubernetes运维专家&…...

实战复盘-Redis连接数爆满引发的生产事故与优化策略

1. 事故背景&#xff1a;一场由促销活动引发的Redis雪崩 那天凌晨三点&#xff0c;我被一阵急促的电话铃声惊醒。电话那头是值班同事焦急的声音&#xff1a;"所有商品页面都打不开了&#xff0c;订单系统也瘫痪了&#xff01;"我瞬间清醒&#xff0c;抓起电脑就开始…...

modelsim crack过程中显示dll文件找不到解决方法

把这几个文件放到modelsim/win64目录下&#xff0c;按照教程点击patch64生成license时会报错&#xff0c;如下找不到文件 - mgls.dll找不到文件 - mgls64.dll这个时候关闭杀毒软件进入你的 D:\modeltech64_10.5\win64 文件夹。在文件夹上方的地址栏&#xff08;显示路径的地方&…...

AtlasOS系统性能优化指南:从诊断到维护的全流程解决方案

AtlasOS系统性能优化指南&#xff1a;从诊断到维护的全流程解决方案 【免费下载链接】Atlas &#x1f680; An open and lightweight modification to Windows, designed to optimize performance, privacy and security. 项目地址: https://gitcode.com/GitHub_Trending/atl…...

Go语言广播系统设计:基于Channel的高性能事件分发机制

引言 在后端系统架构中&#xff0c;事件广播是一种常见的通信模式。本文将深入分析一个基于Go语言channel实现的广播管理器&#xff0c;探讨其设计思想、实现细节以及在实际项目中的应用价值。 参考代码 点击直达 背景与需求 在许多应用场景中&#xff0c;我们需要实现一对…...

LazyVim终极指南:如何快速打造你的Neovim梦幻开发环境

LazyVim终极指南&#xff1a;如何快速打造你的Neovim梦幻开发环境 【免费下载链接】LazyVim Neovim懒人配置。 项目地址: https://gitcode.com/GitHub_Trending/la/LazyVim 你是否曾经因为Neovim配置的复杂性而望而却步&#xff1f;是否尝试过各种配置方案却始终找不到那…...

Wan2.2-I2V-A14B企业应用:品牌广告片AI辅助生成+人工精修工作流

Wan2.2-I2V-A14B企业应用&#xff1a;品牌广告片AI辅助生成人工精修工作流 1. 企业级视频创作新范式 在品牌营销领域&#xff0c;高质量视频内容的需求正呈指数级增长。传统视频制作流程面临三大痛点&#xff1a;创意实现周期长、专业团队成本高、批量生产难度大。Wan2.2-I2V…...

3步实现手游PC级操控:QtScrcpy键鼠映射技术全解析

3步实现手游PC级操控&#xff1a;QtScrcpy键鼠映射技术全解析 【免费下载链接】QtScrcpy Android实时投屏软件&#xff0c;此应用程序提供USB(或通过TCP/IP)连接的Android设备的显示和控制。它不需要任何root访问权限 项目地址: https://gitcode.com/barry-ran/QtScrcpy …...

BiliRoamingX集成开发:Android 14兼容性优化与高级模块注入技术解析

BiliRoamingX集成开发&#xff1a;Android 14兼容性优化与高级模块注入技术解析 【免费下载链接】BiliRoamingX-integrations BiliRoamingX integrations powered by revanced. 项目地址: https://gitcode.com/gh_mirrors/bi/BiliRoamingX-integrations BiliRoamingX作为…...