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

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

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

文章目录

  • 解题思路
  • 解决方法
  • 复杂度分析
  • 代码实现

解题思路

解决此问题需要确定如何以最小的插入次数构造一个有效的字符串。首先,我们需要确定开头的差距,然后决定中间的补足,最后决定末尾的差距。

解决方法

在确定开头的差距时,我们可以对字符a不进行任何处理,b增加1,c增加2。

对于中间位置的补足,如果当前位置是a,且下一个位置是b,则不进行任何处理;如果是c则增加1;如果是a则增加2。同理,如果当前位置是b,且下一个位置是a,+1,b,+2;如果是c,则b,+1,c,+2。

对于末尾的差距,c不处理,b增加1,a增加2。

复杂度分析

时间复杂度: O ( n ) O(n) O(n),其中n是字符串的长度。这是因为我们需要遍历整个字符串来确定每个位置的最小插入次数。

空间复杂度: O ( 1 ) O(1) O(1)。这是因为我们只使用了几个变量来存储中间结果,这些变量的大小是常数,所以空间复杂度为O(1)。

代码实现

class Solution {
public:int addMinimum(string word) {int len = word.size();int aMinimum = 0;aMinimum += abs('a' - word[0]); // 开头a不处理aMinimum += 'c' - word[len - 1]; // 末尾c不处理for (int i = 1; i < len; ++i) { // 遍历中间字符if (word[i - 1] - word[i] == -2 || word[i - 1] - word[i] == 1) { // 下一个字符与当前字符相差-2或1,不处理aMinimum += 1;} else if (word[i - 1] == word[i]) { // 下一个字符与当前字符相同,需要增加2或者1aMinimum += 2;} else { // 下一个字符与当前字符不同且相差大于1,需要增加1aMinimum += 1;}}return aMinimum; // 返回最小插入次数}
};

相关文章:

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

Problem: 2645. 构造有效字符串的最少插入数 文章目录 解题思路解决方法复杂度分析代码实现 解题思路 解决此问题需要确定如何以最小的插入次数构造一个有效的字符串。首先&#xff0c;我们需要确定开头的差距&#xff0c;然后决定中间的补足&#xff0c;最后决定末尾的差距。…...

C#,快速排序算法(Quick Sort)的非递归实现与数据可视化

排序算法是编程的基础。 常见的四种排序算法是&#xff1a;简单选择排序、冒泡排序、插入排序和快速排序。其中的快速排序的优势明显&#xff0c;一般使用递归方式实现&#xff0c;但遇到数据量大的情况则无法适用。实际工程中一般使用“非递归”方式实现。 快速排序(Quick Sor…...

【操作系统xv6】学习记录2 -RISC-V Architecture

说明&#xff1a;看完这节&#xff0c;不会让你称为汇编程序员&#xff0c;知识操作系统的前置。 ref&#xff1a;https://binhack.readthedocs.io/zh/latest/assembly/mips.html https://www.bilibili.com/video/BV1w94y1a7i8/?p7 MIPS MIPS的意思是 “无内部互锁流水级的微…...

C++力扣题目111--二叉树的最小深度

力扣题目链接(opens new window) 给定一个二叉树&#xff0c;找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明: 叶子节点是指没有子节点的节点。 示例: 给定二叉树 [3,9,20,null,null,15,7], 返回它的最小深度 2 思路 看完了这篇104.二…...

【图像拼接】源码精读:Adaptive As-Natural-As-Possible Image Stitching(AANAP/ANAP)

第一次来请先看这篇文章:【图像拼接(Image Stitching)】关于【图像拼接论文源码精读】专栏的相关说明,包含专栏内文章结构说明、源码阅读顺序、培养代码能力、如何创新等(不定期更新) 【图像拼接论文源码精读】专栏文章目录 【源码精读】As-Projective-As-Possible Imag…...

解决docker run报错:Error response from daemon: No command specified.

将docker镜像export/import之后&#xff0c;对新的镜像执行docker run时报错&#xff1a; docker: Error response from daemon: No command specified. 解决方法&#xff1a; 方案1&#xff1a; 查看容器的command&#xff1a; docker ps --no-trunc 在docker run命令上增加…...

算法第十二天-最大整除子集

最大整除子集 题目要求 解题思路 来自[宫水三叶] 根据题意&#xff1a;对于符合要求的[整除子集]中的任意两个值&#xff0c;必然满足[较大数]是[较小数]的倍数 数据范围是 1 0 3 10^3 103&#xff0c;我们不可能采取获取所有子集&#xff0c;再检查子集是否合法的暴力搜解法…...

简单易懂的PyTorch 损失函数:优化机器学习模型的关键

目录 torch.nn子模块Loss Functions详解 nn.L1Loss 用途 用法 使用技巧 注意事项 代码示例 nn.MSELoss 用途 用法 使用技巧 注意事项 代码示例 nn.CrossEntropyLoss 用途 用法 使用技巧 注意事项 代码示例 使用类别索引 使用类别概率 nn.CTCLoss 用途 …...

Kubernetes/k8s的存储卷/数据卷

k8s的存储卷/数据卷 容器内的目录和宿主机的目录挂载 容器在系统上的生命周期是短暂的&#xff0c;delete&#xff0c;k8s用控制创建的pod&#xff0c;delete相当于重启&#xff0c;容器的状态也会回复到初始状态 一旦回到初始状态&#xff0c;所有的后天编辑的文件都会消失…...

【漏洞复现】锐捷RG-UAC统一上网行为管理系统信息泄露漏洞

Nx01 产品简介 锐捷网络成立于2000年1月&#xff0c;原名实达网络&#xff0c;2003年更名&#xff0c;自成立以来&#xff0c;一直扎根行业&#xff0c;深入场景进行解决方案设计和创新&#xff0c;并利用云计算、SDN、移动互联、大数据、物联网、AI等新技术为各行业用户提供场…...

Android - 串口通讯(SerialPort)

最早的博客Android 模拟串口通信过程_launch virtual serial port driver pro-CSDN博客里就是用过 Google 提供的 demo&#xff0c;最近想再写个其他的demo发现用起来有点麻烦&#xff0c;还需要导入其他 module&#xff0c;因此在网上找到了Android-SerialPort-API: https://g…...

如何使用設置靜態住宅IP

靜態住宅IP就是一種靜態的、分配給住宅用戶的IP地址。與動態IP地址不同&#xff0c;靜態住宅IP一旦分配給用戶&#xff0c;就會一直保持不變&#xff0c;除非ISP&#xff08;Internet Service Provider&#xff0c;互聯網服務提供商&#xff09;進行手動更改。那麼&#xff0c;…...

在学习爬虫前的准备

1. 写一个爬虫程序需要分几步 获取网页内容。 我们会通过代码给一个网站服务器发送请求&#xff0c;它会返回给我们网页上的内容。 在我们平时使用浏览器访问服务器内容是&#xff0c;本质上也是向服务器发送一个请求&#xff0c;然后服务器返回网页上的内容。只不过浏览器还会…...

windows下安装oracle-win-64-11g超详细图文步骤

官方下载地址&#xff1a;点这里 1.根据自己电脑情况&#xff0c;解压64或者32位客户端&#xff0c;以及database压缩包 2.解压后双击执行database文件夹下的setup.exe 3.详细的安装步骤 &#xff08;1&#xff09;数据库安装 一、配置安全更新 电子邮件可写可不写&#xf…...

Go模板后端渲染时vue单页面冲突处理

go后端模版语法是通过 {{}} &#xff0c;vue也是通过双花括号来渲染的&#xff0c;如果使用go渲染vue的html页面的时候就会报错&#xff0c;因为分别不出来哪个是vue的&#xff0c;哪个是go的&#xff0c;既可以修改go的模板语法 template.New("output").Delims(&qu…...

笔记本摄像头模拟监控推送RTSP流

使用笔记本摄像头模拟监控推送RTSP流 一、基础安装软件准备 本文使用软件下载链接:下载地址 FFmpeg软件: Download ffmpeg 选择Windows builds by BtbN 一个完整的跨平台解决方案&#xff0c;用于录制、转换和流式传输音频和视频。 EasyDarwin软件&#xff1a;Download Easy…...

鸿蒙开发已解决-ArkTS编译时遇到arkts-no-obj-literals-as-types错误

文章目录 项目场景:问题描述原因分析:解决方案:解决方案1解决方案2此Bug解决方案总结项目场景: 在开发鸿蒙项目过程中,遇到了arkts-no-obj-literals-as-types,总结了自己和网上人的解决方案,故写下这篇文章。 遇到问题: rkTS编译时遇到arkts-no-obj-literals-as-type…...

实现目标检测中的数据格式自由(labelme json、voc、coco、yolo格式的相互转换)

在进行目标检测任务中&#xff0c;存在labelme json、voc、coco、yolo等格式。labelme json是由anylabeling、labelme等软件生成的标注格式、voc是通用目标检测框&#xff08;mmdetection、paddledetection&#xff09;所支持的格式&#xff0c;coco是通用目标检测框&#xff0…...

一文读懂JVS逻辑引擎如何调用规则引擎:含详细步骤与场景示例

在当今的数字化时代&#xff0c;业务逻辑和规则的复杂性不断增加&#xff0c;这使得逻辑引擎和规则引擎在处理业务需求时显得尤为重要。逻辑引擎和规则引擎通过定义、解析和管理业务逻辑和规则&#xff0c;能够帮助企业提高工作效率、降低运营成本&#xff0c;并增强决策的科学…...

苹果应用上架是否需要软件著作权?

苹果应用上架是否需要软件著作权&#xff1f; 摘要 随着移动互联网的发展&#xff0c;苹果应用在市场上占据了很大份额。但是&#xff0c;很多开发者在上传苹果应用到App Store时&#xff0c;都会遇到一个问题&#xff0c;即是否需要进行软著申请&#xff1f;本文将深入探讨这…...

良心推荐!阿贝云免费云服务器,新手小白也能轻松上手

最近在折腾个人网站&#xff0c;想找个免费的云服务器练练手&#xff0c;试了好几家都不太满意。后来朋友推荐了阿贝云&#xff0c;体验下来感觉真的不错。 首先&#xff0c;阿贝云的免费云服务器配置很实在&#xff1a;1核CPU、1GB内存、5M带宽&#xff0c;还带独立公网IP。对…...

MID360+单目实现差速小车重定位、导航避障与自动充电

实现的功能&#xff1a;建图、重定位、导航、避障、自动充电 MID360单目实现差速小车重定位、导航避障与自动充电 视频演示 github链接&#xff1a;Github仓库地址 &#x1f680; ArduRover-Mid360: 移动机器人系统 本项目是一个基于APM飞控、NVIDIA Jetson Orin NX 算力平台…...

YOLO X Layout部署教程:CentOS 7离线环境安装ONNX Runtime 1.16兼容包

YOLO X Layout部署教程&#xff1a;CentOS 7离线环境安装ONNX Runtime 1.16兼容包 1. 引言 如果你正在CentOS 7服务器上部署YOLO X Layout文档理解模型&#xff0c;可能会遇到一个常见问题&#xff1a;系统自带的ONNX Runtime版本太旧&#xff0c;而YOLO X Layout需要1.16或更…...

Janus-Pro-7B在CNN图像识别中的增强应用

Janus-Pro-7B在CNN图像识别中的增强应用 1. 引言 图像识别技术正在经历一场革命性的变革。传统的CNN模型虽然在图像分类任务上表现出色&#xff0c;但在复杂场景和多模态理解方面仍存在局限。今天我们要介绍的Janus-Pro-7B&#xff0c;作为一个统一的多模态理解和生成框架&am…...

Qwen3-14B向量数据库集成:Chroma/Milvus接入与混合检索配置

Qwen3-14B向量数据库集成&#xff1a;Chroma/Milvus接入与混合检索配置 1. 引言&#xff1a;为什么需要向量数据库集成 当你部署了强大的Qwen3-14B大模型后&#xff0c;很快会发现一个关键问题&#xff1a;如何让模型记住并快速检索大量知识&#xff1f;这就是向量数据库的价…...

GLM-4.1V-9B-Base实战教程:批量图片队列处理与异步结果回调机制实现

GLM-4.1V-9B-Base实战教程&#xff1a;批量图片队列处理与异步结果回调机制实现 1. 引言 在实际业务场景中&#xff0c;我们经常需要处理大量图片的分析任务。GLM-4.1V-9B-Base作为一款强大的视觉多模态理解模型&#xff0c;虽然提供了便捷的Web界面&#xff0c;但面对批量图…...

【C++27 constexpr革命性突破】:5大新增约束与3类不可逆性能跃迁,资深编译器工程师亲授落地实践

第一章&#xff1a;C27 constexpr革命性突破的底层动因与标准演进全景C27 将首次允许 constexpr 函数完整支持动态内存分配&#xff08;std::allocator 与 new/delete&#xff09;、虚函数调用、异常处理&#xff08;try/catch&#xff09;及完整 I/O 流子集&#xff0c;其根本…...

Hunyuan-MT-7B性能实测:像素语言传送门在单卡A10上并发10路翻译的延迟与稳定性报告

Hunyuan-MT-7B性能实测&#xff1a;像素语言传送门在单卡A10上并发10路翻译的延迟与稳定性报告 1. 测试背景与目标 像素语言传送门&#xff08;Pixel Language Portal&#xff09;是基于腾讯Hunyuan-MT-7B模型构建的创新翻译工具&#xff0c;其独特的16-bit像素冒险界面设计为…...

PyTorch版本升级踩坑实录:从1.10.0到1.10.1为何导致CUDA不兼容?

PyTorch小版本升级的隐秘陷阱&#xff1a;CUDA兼容性深度解析与实战解决方案 当你满怀期待地执行pip install --upgrade torch命令&#xff0c;将PyTorch从1.10.0升级到1.10.1时&#xff0c;可能不会想到这个看似无害的小版本更新会让你的GPU突然"罢工"。这不是个例…...

电子元器件失效分析与预防实战指南

1. 电子元器件失效的底层逻辑剖析 电子元器件失效的本质是材料特性、环境应力与时间因素共同作用的结果。作为一名硬件工程师&#xff0c;我处理过数百例元器件失效案例&#xff0c;发现失效模式往往遵循"应力-损伤-失效"的因果链。理解这个链条&#xff0c;才能从根…...