【LeetCode每日一题】2645. 构造有效字符串的最少插入数(计算组数+动态规划+考虑相邻字母)

本文主要是介绍【LeetCode每日一题】2645. 构造有效字符串的最少插入数(计算组数+动态规划+考虑相邻字母),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

2024-1-11

文章目录

      • [2645. 构造有效字符串的最少插入数](https://leetcode.cn/problems/minimum-additions-to-make-valid-string/)
            • 方法一:计算组数
            • 方法二:动态规划
            • 方法三: 考虑相邻字母

2645. 构造有效字符串的最少插入数

在这里插入图片描述

方法一:计算组数

1.用count统计,能构成几组abc

2.如果当前字符大于之前字符,说明还在组内,不更新

3.如果当前字符小于等于之前字符,说明不是同一组的abc,组数更新

4.最终返回值:组数*3,再减去原本的字符数,就是要插入的次数

    //2645. 构造有效字符串的最少插入数---计算组数public int addMinimum2(String word) {int n = word.length();int count = 1;//最终构成abc的组数for (int i = 1; i < n; i++) {if (word.charAt(i - 1) >= word.charAt(i)) {//当前字符小于等于之前字符count++;//组数加一}}return count*3-n;//返回最终构成abc的总数-原本字符,即为要插入的次数}
方法二:动态规划

1.从1开始,d[i]为前i个字符拼成abc需要的最小插入数

2.情况一:word[i]单独存在于一组abc中,需要插两次,才能组成abc.插入次数为之前的次数+2

3.情况二:当前字符比前一个字符大,需要插一次,就可以组成abc.修改当前插入次数为:之前的次数-1,因为之前插入的两次中已经包含了当前字符。

    public int addMinimum(String word) {int n = word.length();int[] d = new int[n + 1];//d[]数组用来统计,1到n的插入次数//从1开始,d[i]为前i个字符拼成abc需要的最小插入数。for (int i = 1; i <= n; i++) {d[i] = d[i - 1] + 2;//word[i]单独存在于一组abc中,在之前情况的基础上+2. eg: a+bc / b+ac / c+abif (i > 1 && word.charAt(i - 1) > word.charAt(i - 2)) {//如果当前字符比前一个字符大,eg:ab/ ac / bcd[i] = d[i - 1] - 1;//当前字符和之前的字符在同一个abc中,重新覆盖d[i],前一个位置的插入数-1}}return d[n];}
方法三: 考虑相邻字母

1.设当前字符为x,前一个字符为y,

2.x大于y的情况:x-y-1

3.x小于等于y的情况:(x-y-1+3)mod 3 ,将计算的结果控制在0-2之间

4.开头的单独一个字符:word[0]-‘a’ ,结尾的一个字符:‘c’-word[n-1],合并为word[0]-word[n-1]+2

    public int addMinimum3(String word) {int n = word.length();int res = word.charAt(0) - word.charAt(n - 1) + 2;//合并处理开头和结尾的情况for (int i = 1; i < n; i++) {res += (word.charAt(i) - word.charAt(i - 1) + 2) % 3;}return res;}

1-11 生日快乐

点击移步博客主页,欢迎光临~

偷cyk的图

这篇关于【LeetCode每日一题】2645. 构造有效字符串的最少插入数(计算组数+动态规划+考虑相邻字母)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/597343

相关文章

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

C#如何动态创建Label,及动态label事件

《C#如何动态创建Label,及动态label事件》:本文主要介绍C#如何动态创建Label,及动态label事件,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#如何动态创建Label,及动态label事件第一点:switch中的生成我们的label事件接着,

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

MyBatis 动态 SQL 优化之标签的实战与技巧(常见用法)

《MyBatis动态SQL优化之标签的实战与技巧(常见用法)》本文通过详细的示例和实际应用场景,介绍了如何有效利用这些标签来优化MyBatis配置,提升开发效率,确保SQL的高效执行和安全性,感... 目录动态SQL详解一、动态SQL的核心概念1.1 什么是动态SQL?1.2 动态SQL的优点1.3 动态S

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

MySQL INSERT语句实现当记录不存在时插入的几种方法

《MySQLINSERT语句实现当记录不存在时插入的几种方法》MySQL的INSERT语句是用于向数据库表中插入新记录的关键命令,下面:本文主要介绍MySQLINSERT语句实现当记录不存在时... 目录使用 INSERT IGNORE使用 ON DUPLICATE KEY UPDATE使用 REPLACE

python中字符串拼接的几种方法及优缺点对比详解

《python中字符串拼接的几种方法及优缺点对比详解》在Python中,字符串拼接是常见的操作,Python提供了多种方法来拼接字符串,每种方法有其优缺点和适用场景,以下是几种常见的字符串拼接方法,需... 目录1. 使用 + 运算符示例:优缺点:2. 使用&nbsjsp;join() 方法示例:优缺点:3

java字符串数字补齐位数详解

《java字符串数字补齐位数详解》:本文主要介绍java字符串数字补齐位数,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java字符串数字补齐位数一、使用String.format()方法二、Apache Commons Lang库方法三、Java 11+的St

C++字符串提取和分割的多种方法

《C++字符串提取和分割的多种方法》在C++编程中,字符串处理是一个常见的任务,尤其是在需要从字符串中提取特定数据时,本文将详细探讨如何使用C++标准库中的工具来提取和分割字符串,并分析不同方法的适用... 目录1. 字符串提取的基本方法1.1 使用 std::istringstream 和 >> 操作符示

一文教你PyCharm如何有效地添加源与库

《一文教你PyCharm如何有效地添加源与库》在使用PyCharm进行Python开发的时候,很多时候我们需要添加库或者设置源,下面我们就来和大家详细介绍一下如何在PyCharm中添加源和库吧... 在使用PyCharm进行python开发的时候,很多时候我们需要添加库或者设置源。这些操作可以帮助我们更方便