【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

相关文章

SpringBoot基于配置实现短信服务策略的动态切换

《SpringBoot基于配置实现短信服务策略的动态切换》这篇文章主要为大家详细介绍了SpringBoot在接入多个短信服务商(如阿里云、腾讯云、华为云)后,如何根据配置或环境切换使用不同的服务商,需... 目录目标功能示例配置(application.yml)配置类绑定短信发送策略接口示例:阿里云 & 腾

Java中字符串转时间与时间转字符串的操作详解

《Java中字符串转时间与时间转字符串的操作详解》Java的java.time包提供了强大的日期和时间处理功能,通过DateTimeFormatter可以轻松地在日期时间对象和字符串之间进行转换,下面... 目录一、字符串转时间(一)使用预定义格式(二)自定义格式二、时间转字符串(一)使用预定义格式(二)自

Python实现特殊字符判断并去掉非字母和数字的特殊字符

《Python实现特殊字符判断并去掉非字母和数字的特殊字符》在Python中,可以通过多种方法来判断字符串中是否包含非字母、数字的特殊字符,并将这些特殊字符去掉,本文为大家整理了一些常用的,希望对大家... 目录1. 使用正则表达式判断字符串中是否包含特殊字符去掉字符串中的特殊字符2. 使用 str.isa

Java字符串操作技巧之语法、示例与应用场景分析

《Java字符串操作技巧之语法、示例与应用场景分析》在Java算法题和日常开发中,字符串处理是必备的核心技能,本文全面梳理Java中字符串的常用操作语法,结合代码示例、应用场景和避坑指南,可快速掌握字... 目录引言1. 基础操作1.1 创建字符串1.2 获取长度1.3 访问字符2. 字符串处理2.1 子字

一文详解如何在Python中从字符串中提取部分内容

《一文详解如何在Python中从字符串中提取部分内容》:本文主要介绍如何在Python中从字符串中提取部分内容的相关资料,包括使用正则表达式、Pyparsing库、AST(抽象语法树)、字符串操作... 目录前言解决方案方法一:使用正则表达式方法二:使用 Pyparsing方法三:使用 AST方法四:使用字

Java字符串处理全解析(String、StringBuilder与StringBuffer)

《Java字符串处理全解析(String、StringBuilder与StringBuffer)》:本文主要介绍Java字符串处理全解析(String、StringBuilder与StringBu... 目录Java字符串处理全解析:String、StringBuilder与StringBuffer一、St

MySQL中动态生成SQL语句去掉所有字段的空格的操作方法

《MySQL中动态生成SQL语句去掉所有字段的空格的操作方法》在数据库管理过程中,我们常常会遇到需要对表中字段进行清洗和整理的情况,本文将详细介绍如何在MySQL中动态生成SQL语句来去掉所有字段的空... 目录在mysql中动态生成SQL语句去掉所有字段的空格准备工作原理分析动态生成SQL语句在MySQL

MySQL更新某个字段拼接固定字符串的实现

《MySQL更新某个字段拼接固定字符串的实现》在MySQL中,我们经常需要对数据库中的某个字段进行更新操作,本文就来介绍一下MySQL更新某个字段拼接固定字符串的实现,感兴趣的可以了解一下... 目录1. 查看字段当前值2. 更新字段拼接固定字符串3. 验证更新结果mysql更新某个字段拼接固定字符串 -

Java String字符串的常用使用方法

《JavaString字符串的常用使用方法》String是JDK提供的一个类,是引用类型,并不是基本的数据类型,String用于字符串操作,在之前学习c语言的时候,对于一些字符串,会初始化字符数组表... 目录一、什么是String二、如何定义一个String1. 用双引号定义2. 通过构造函数定义三、St

golang获取当前时间、时间戳和时间字符串及它们之间的相互转换方法

《golang获取当前时间、时间戳和时间字符串及它们之间的相互转换方法》:本文主要介绍golang获取当前时间、时间戳和时间字符串及它们之间的相互转换,本文通过实例代码给大家介绍的非常详细,感兴趣... 目录1、获取当前时间2、获取当前时间戳3、获取当前时间的字符串格式4、它们之间的相互转化上篇文章给大家介