LeetCode 3106.满足距离约束且字典序最小的字符串:模拟(贪心)
【LetMeFly】3106.满足距离约束且字典序最小的字符串:模拟(贪心)
力扣题目链接:https://leetcode.cn/problems/lexicographically-smallest-string-after-operations-with-constraint/
给你一个字符串 s
和一个整数 k
。
定义函数 distance(s1, s2)
,用于衡量两个长度为 n
的字符串 s1
和 s2
之间的距离,即:
- 字符
'a'
到'z'
按 循环 顺序排列,对于区间[0, n - 1]
中的i
,计算所有「s1[i]
和s2[i]
之间 最小距离」的 和 。
例如,distance("ab", "cd") == 4
,且 distance("a", "z") == 1
。
你可以对字符串 s
执行 任意次 操作。在每次操作中,可以将 s
中的一个字母 改变 为 任意 其他小写英文字母。
返回一个字符串,表示在执行一些操作后你可以得到的 字典序最小 的字符串 t
,且满足 distance(s, t) <= k
。
示例 1:
输入:s = "zbbz", k = 3 输出:"aaaz" 解释:在这个例子中,可以执行以下操作: 将 s[0] 改为 'a' ,s 变为 "abbz" 。 将 s[1] 改为 'a' ,s 变为 "aabz" 。 将 s[2] 改为 'a' ,s 变为 "aaaz" 。 "zbbz" 和 "aaaz" 之间的距离等于 k = 3 。 可以证明 "aaaz" 是在任意次操作后能够得到的字典序最小的字符串。 因此,答案是 "aaaz" 。
示例 2:
输入:s = "xaxcd", k = 4 输出:"aawcd" 解释:在这个例子中,可以执行以下操作: 将 s[0] 改为 'a' ,s 变为 "aaxcd" 。 将 s[2] 改为 'w' ,s 变为 "aawcd" 。 "xaxcd" 和 "aawcd" 之间的距离等于 k = 4 。 可以证明 "aawcd" 是在任意次操作后能够得到的字典序最小的字符串。 因此,答案是 "aawcd" 。
示例 3:
输入:s = "lol", k = 0 输出:"lol" 解释:在这个例子中,k = 0,更改任何字符都会使得距离大于 0 。 因此,答案是 "lol" 。
提示:
1 <= s.length <= 100
0 <= k <= 2000
s
只包含小写英文字母。
解题方法:贪心
首先需要明确,越靠前的位置越重要。所以要不惜一切代价将前面字符尽可能地变小。
字符变小的方式有两种:
- 往小的方向变。每消耗一次操作次数字符就会变小一点,直到变成了
a
为止。 - 往大的方向变。这样做的前提是剩下的操作次数足够让当前字符变大到
z
再变成a
。
因此贪心思路出来了:
在还剩有操作次数时,从前到后开始变化字符:
对于当前字符,如果剩余操作次数足够往大的方向变到
a
,且这样做比往小的方向变到a
所需次数更少,则往大的方向变到a
为止;否则,往小的方向变,直到变到
a
或用完了操作次数为止。
- 时间复杂度 O ( l e n ( s ) ) O(len(s)) O(len(s))
- 空间复杂度 O ( 1 ) O(1) O(1)
AC代码
C++
class Solution {
public:string getSmallestString(string s, int k) {for (char &c : s) {int left = c - 'a', right = 'z' - c + 1;if (k >= right && right < left) {c = 'a';k -= right;}else {int move = min(left, k);c -= move;k -= move;}if (k == 0) {break;}}return s;}
};
同步发文于CSDN和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/140758056
相关文章:
LeetCode 3106.满足距离约束且字典序最小的字符串:模拟(贪心)
【LetMeFly】3106.满足距离约束且字典序最小的字符串:模拟(贪心) 力扣题目链接:https://leetcode.cn/problems/lexicographically-smallest-string-after-operations-with-constraint/ 给你一个字符串 s 和一个整数 k 。 定义函…...
Elasticsearch 与 MySQL 在查询和插入性能上的深度剖析
在当今的数据处理领域,选择合适的数据库对于应用的性能和效率至关重要。Elasticsearch 和 MySQL 作为两款常用的数据库,它们在查询和插入操作上的性能表现各有千秋。本文将对这两款数据库在这两个关键操作上进行详细的对比分析。 一、引言 随着数据量的…...
day4 vue2以及ElementUI
创建vue2项目 可能用到的命令行们 vue create 项目名称 // 创建项目 cd 项目名称 // 只有进入项目下,才能运行 npm run serve // 运行项目 D: //切换盘符 cd .. // 返回到上一级目录 clear // 清空终端 更改 Vue项目的端口配置 基础语法 项目创建完成之后&#…...
把redis用在Java项目
1. Java连接redis Java连接redis的方式是通过jedis,连接redis需要遵循jedis协议。 1.1 引入依赖 <!--引入java连接redis的驱动--><dependency><groupId>redis.clients</groupId><artifactId>jedis</artifactId><version&…...
GORM:优雅的Go语言ORM库
文章目录 引言GORM原理基础使用安装GORM定义模型连接数据库CRUD操作 高级使用关联事务回调 优点结论 引言 在Go语言开发中,数据库操作是不可或缺的一部分。虽然直接使用SQL语句可以灵活地与数据库交互,但随着项目规模的扩大,SQL语句的编写、…...
Golang | Leetcode Golang题解之第279题完全平方数
题目: 题解: // 判断是否为完全平方数 func isPerfectSquare(x int) bool {y : int(math.Sqrt(float64(x)))return y*y x }// 判断是否能表示为 4^k*(8m7) func checkAnswer4(x int) bool {for x%4 0 {x / 4}return x%8 7 }func numSquares(n int) i…...
Oracle系统表空间的加解密
实验环境 数据库选择的是orclpdb1,当前系统表空间未加密: SQL> show con_nameCON_NAME ------------------------------ ORCLPDB1SQL> select TABLESPACE_NAME, STATUS, ENCRYPTED from dba_tablespaces;TABLESPACE_NAME STATUS …...
pytorch backbone
1 简介 在PyTorch深度学习中,预训练backbone(骨干网络)是一个常见的做法,特别是在处理图像识别、目标检测、图像分割等任务时。预训练backbone通常是指在大型数据集(如ImageNet)上预先训练好的卷积神经网络…...
uniapp 开发app使用renderjs操作dom
需求:把页面中的对话内容另存为一张图片保存到手机相册。 解决方案:这时我们需要使用到document对象创建一个dom对象计算对话内容的宽高、位置等,再利用canvas能力将内容绘制绘制成一张图保存。 现状:总所周知,非H5端&…...
【面试题】MySQL `EXPLAIN`的`Extra`字段:深入解析查询优化的隐藏信息
MySQL EXPLAIN的Extra字段:深入解析查询优化的隐藏信息 引言 在MySQL的EXPLAIN输出中,Extra字段提供了关于查询执行计划的额外信息。这些信息对于理解查询的内部工作机制和优化查询性能至关重要。本文将详细解析Extra字段中常见的几个关键指标…...
Jenkins持续部署
开发环境任务的代码只要有更新,Jenkins会自动获取新的代码并运行 1. pycharm和git本地集成 获取到下面的 Git可执行文件路径 2. pycharm和gitee远程仓库集成 先在pycharm中安装gitee插件 在设置中找到gitee,点击添加账户,并将自己的账户添…...
橙单前端项目下载编译遇到的问题与解决
今天下载orange-admin前端项目,不过下载下来运行也出现一些问题。 1、运行出现下面一堆错误,如下: 2、对于下面这个错误 error Expected linebreaks to be LF but found CRLF linebreak-style 这就是eslint的报错了,可能是原作者…...
在android中怎么处理后端返回列表中包含图片id,如何将列表中的图片id转化成url
在 Android 中实现从包含图片 ID 的列表获取实际图片 URL 并显示图片,你可以使用以下步骤: 定义数据模型:创建一个 Java 或 Kotlin 类来表示列表中的对象。 网络请求:使用 Retrofit 或其他网络库来获取图片 URL。 异步处理:使用 AsyncTask、RxJava 或 Kotlin 协程来处理网…...
IM聊天代码
客户端 Headers inet inet.h #pragma once #include<Winsock2.h>//#pragma comment(lib,"Ws2_32.lib")class INetMediator; class INet { public:INet(){}virtual ~INet(){}//初始化网络virtual bool initNet() 0;//接收数据virtual void recvData() 0;…...
【Go - context 速览,场景与用法】
作用 context字面意思上下文,用于关联管理上下文,具体有如下几个作用 取消信号传递:可以用来传递取消信号,让一个正在执行的函数知道它应该提前终止。超时控制:可以设定一个超时时间,自动取消超过执行时间…...
Linus: vim编辑器的使用,快捷键及配置等周边知识详解
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 vim的安装创建新用户 adduser 用户名Linus是个多用户的操作系统是否有创建用户的权限查看当前用户身份:whoami** 怎么创建设置密码passwdsudo提权(sudo输入的是用户…...
数仓作业延时告警-基于关键路径预推
简介 作业延时告警,通常来说有两种方式: 其一,当作业到目标时间点还没完成触发告警;这类情况,对于目标作业而言,延时已经触发了,风险相对较大;有的是监控接口延时(raw层…...
秋招复习笔记——八股文部分:网络TCP
TCP 三次握手和四次挥手 TCP 基本认识 序列号:在建立连接时由计算机生成的随机数作为其初始值,通过 SYN 包传给接收端主机,每发送一次数据,就「累加」一次该「数据字节数」的大小。用来解决网络包乱序问题。 确认应答号…...
麒麟桌面操作系统上配置Samba
原文链接:麒麟桌面操作系统上配置Samba Hello,大家好啊!今天给大家带来一篇关于在麒麟桌面操作系统上配置Samba的文章。Samba是一种免费的软件,实现了SMB/CIFS网络协议,使得Linux和Windows系统之间可以共享文件和打印机…...
【Go】探索 Go 语言的内建函数 copy
山水间歌声回荡 回荡思念的滚烫 去年的家书两行 读来又热了眼眶 云水边静沐暖阳 烟波里久违的故乡 别来无恙 你在心上 🎵 张靓颖/张杰《燕归巢》 在 Go 语言中,copy 是一个用于在切片之间复制元素的内建函数。它提供了一种简单而高…...
【React】JSX:从基础语法到高级用法的深入解析
文章目录 一、什么是 JSX?1. 基础语法2. 嵌入表达式3. 使用属性4. JSX 是表达式 二、JSX 的注意事项1. 必须包含在单个父元素内2. JSX 中的注释3. 避免注入攻击 三、JSX 的高级用法1. 条件渲染2. 列表渲染3. 内联样式4. 函数作为子组件 四、最佳实践 在 React 开发中…...
JMeter 使用
1.JMeter 是什么? JMeter 是一款广泛使用的开源性能测试工具,由 Apache 软件基金会维护。它主要用于测试 Web 应用程序的负载能力和性能,但也支持其他类型的测试,如数据库、FTP、JMS、LDAP、SOAP web services 等。 2.特点&#x…...
20240724----安装git和配置git的环境变量/如何用命令git项目到本地idea
备注参考博客: 1)可以参考博客,用git把项目git到本地 2)可以参考博客vcs没有git 3)git版本更新,覆盖安装 (一)安装git (1)官网下载的链接 https://git-scm.com/downlo…...
JavaScript实战 - 用Canvas画一个心形
作者:逍遥Sean 简介:一个主修Java的Web网站\游戏服务器后端开发者 主页:https://blog.csdn.net/Ureliable 觉得博主文章不错的话,可以三连支持一下~ 如有疑问或建议,请私信或评论留言! 前言: 如…...
vim gcc
vim 使用 vs filename 分屏 ctrl ww 切窗口 shift zz 快速提出vim vim配置 vim启动时自动读取当前用户的家目录的.vimrc文件 vim配置只影响本用户 其他用户观看同一文件不受影响 gcc指令 & c文件编译过程 动态库 静态库 & 链接方式 有相应库才能进行…...
Symfony 表单构建器:创建和管理表单的最佳实践
Symfony 表单构建器:创建和管理表单的最佳实践 Symfony 是一个流行的 PHP 框架,以其强大的功能和灵活性闻名。表单构建器是 Symfony 中一个非常重要的组件,它提供了简单且高效的方式来创建和管理表单。本文将详细介绍 Symfony 表单构建器的最…...
Intel电脑CPU的选择
酷睿 i5/i7/i9 系列至强 Xeon 系列应用场景家用消费级电脑企业服务器工作站PCIe通道数 16X 最多识别到2张显卡,且每张降速为8X 64X 最多支持8张显卡同时使用 内存信道2通道8通道内存容量最大128GB最大6TB工作时长不建议长期不间断连续使用专为365*24不断电使用而设…...
MySQL字段设置的varchar长度小于数据长度自动截取丢弃超出的长度而不是报错?
MySQL字段设置的varchar长度小于数据长度自动截取丢弃超出的长度而不是报错? 事情是这样的,我们一个订单表存放了商品的快照信息其中快照信息存储的是json格式商品信息,当查看订单是报错了,发现我们后端服务查询到订单的快照信息…...
Linux|多线程(三)
线程池 线程池是一种多线程处理形式,处理过程中它将被提交的任务分配给预先创建好的多个线程中的一个去执行。 线程池的实现 #pragma once #include <pthread.h> #include <vector> #include <string> #include <unistd.h> #include <…...
智能合约中如何返回mapping
在 Solidity 中,直接返回一个 mapping 的所有数据是不可能的,因为 mapping 本身不支持直接遍历。但是,可以使用一些技巧来实现这一目标,例如通过维护一个额外的数组来跟踪 mapping 中的键,并通过这个数组来返回所有的键…...
nginx的学习(二):负载均衡和动静分离
简介 nginx的负载均衡和动静分离的简单使用 负载均衡配置 外部访问linux的ip地址:80/edu/a.html地址,会轮询访问Tomcat8080和Tomcat8081服务。 Tomcat的准备 准备两个Tomcat,具体准备步骤在nginx的学习一的反向代理例子2中,在Tomcat8080…...
普中51单片机:DS1302时钟芯片讲解与应用(十)
文章目录 引言基本特性什么是RAM?什么是涓流充电? 电路图和引脚说明通信协议以及工作流程寄存器控制寄存器日历/时钟寄存器 DS1302读写时序代码演示——数码管显示时分秒 引言 DS1302 是一款广泛使用的实时时钟 (RTC) 芯片,具有低功耗、内置…...
Preact:轻量级替代React的选择
Preact是一个轻量级的JavaScript库,它提供了与React相似的API,但体积更小,性能更优。Preact的核心理念是尽可能地保持与React的兼容性,同时去除不必要的部分,使其成为一个理想的替代品,尤其是在对性能和包大…...
全栈嵌入式C++、STM32、Modbus、FreeRTOS和MQTT协议:工业物联网(IIoT)可视化系统设计思路(附部分代码解析)
项目概述 随着工业4.0时代的到来,工业物联网(IIoT)在提高生产效率、降低运营成本和实现智能制造方面得到了广泛应用。本项目旨在开发一个全面的工业物联网监控系统,能够实时监测设备的温度、压力、振动和电流等参数,并…...
Greenplum数据库中的数据倾斜问题及处理方法
一、数据倾斜问题的原因 数据分布不均匀:当数据在表的分区或分片中不均匀分布时,会导致某些分区或分片的数据量较大,从而引发数据倾斜问题。连接键存在热点数据:如果连接操作中使用的键值存在热点数据,即某些键值出现…...
缓存设计理论
缓存设计理论是一个涉及多个方面的复杂主题,主要目标是优化数据访问速度,减少数据访问延迟,提高系统性能,并同时保持数据的一致性和系统的稳定性。以下是从几个关键方面对缓存设计理论的概述: 一、缓存的作用与目的 …...
IDEA-安装插件 驼峰下划线转换
第一步:安装 file-settings-plugins-在marketplace搜索“CamelCase”-点击安装 第二步:设置 file-settings-editor-camel_case 第三步:使用 选中想转换的遍历 使用快捷键 Alt Shift U...
乾坤: 微前端项目切换时样式闪动(从无样式变为正常样式需要等 css chunk 文件加载完成, 加载延时受网速影响)
背景: 点击基座项目页面左侧目录, 进入微前端子项目页面, 会有短暂的样式未加载效果一闪而过, 造成页面闪烁或更严重的其他样式错位问题 定位: 同事查了 qiankun git 项目的 issue: https://github.com/umijs/qiankun/issues/219 , 找到解决方案 解决: 项目 webpack 打包配…...
《电子元器件之固态电容》
固态电容全称是固态铝质电解电容,它与普通液态铝质电解电容的最大差别在于采用了不同的介电材料。液态铝电容介电材料为电解液,而固态电容的介电材料是固态的导电性高分子材料。 固态电容和液态电容,从外观上区分,就是固态电容顶…...
PLC 远程下载网关
一、 产品概述 SSF-BOX-100 是三石峰科技有限公司推出的工业级 PLC 远程下载网关,主 要用于 PLC 远程调试、程序上下载,为用户提供一种简单可靠的远程维护方案。 1.1 SGBOX 软件 SGBOX 软件是 SSF-BOX-100 网关的配套软件,可以查看设备状态…...
【Django】 读取excel文件并在前端以网页形式显示-安装使用Pandas
文章目录 安装pandas写views写urls安装openpyxl重新调试 安装pandas Pandas是一个基于NumPy的Python数据分析库,可以从各种文件格式如CSV、JSON、SQL、Excel等导入数据,并支持多种数据运算操作,如归并、再成形、选择等。 更换pip源 pip co…...
自动控制:带死区的PID控制算法
带死区的PID控制算法 在计算机控制系统中,为了避免控制动作过于频繁,消除因频繁动作所引起的振荡,可采用带死区的PID控制。带死区的PID控制通过引入一个死区,使得在误差较小的范围内不进行控制动作,从而减少控制系统的…...
橙单后端项目下载编译遇到的问题与解决
今天下载orange-admin项目,不过下载下来运行出现一些问题。 1、涉及到XMLStreamException的几个类都出现下面的错误 The package javax.xml.stream is accessible from more than one module: <unnamed>, java.xml ctrl-shift-t 可以找到这个引入是哪些包里…...
EasyExcel 初使用—— Java 实现多种写入 Excel 功能
前言 大家好,我是雪荷。之前有一篇博客(EasyExcel 初使用—— Java 实现读取 Excel 功能_java easyexcel.read-CSDN博客)介绍了 Java 如何读取 Excel 表格,那么此篇博客就和大家介绍下 Java 如何利用 EasyExcel 写入 Excel。 Ea…...
MySQL 和 SQL Server 中的连表更新 UPDATE JOIN 写法比较
MySQL 和 SQL Server 中的连表更新 UPDATE JOIN 写法比较 一、前言1. MySQL 写法1.1 解释 2. SQL Server 写法2.1 解释 二、总结 一、前言 在关系型数据库管理系统(RDBMS)中,使用 UPDATE 语句进行表格更新是非常常见的操作。特别是当需要根据…...
手把手教你FL Studio 24.1.1.4234中文破解安装激活图文激活教程
在数字化音乐制作的浪潮中,FL Studio 24.1.1.4234中文破解版的发布无疑又掀起了一股新的热潮。这款由Image-Line公司开发的数字音频工作站(DAW)软件,以其强大的功能和易用的界面,赢得了全球无数音乐制作人的青睐。本文…...
使用Spring Boot与Spire.Doc实现Word文档的多样化操作
博客主页: 南来_北往 系列专栏:Spring Boot实战 前言 使用Spring Boot与Spire.Doc实现Word文档的多样化操作具有以下优势: 强大的功能组合:Spring Boot提供了快速构建独立和生产级的Spring应用程序的能力,而Spire.Doc则…...
从食堂采购系统源码到成品:打造供应链采购管理平台实战详解
本篇文章,笔者将详细介绍如何从食堂采购系统的源码开始,逐步打造一个完备的供应链采购管理平台,帮助企业实现采购流程的智能化和高效化。 一、需求分析与规划 一般来说,食堂采购系统需要具备以下基本功能: 1.供应商…...
在window将Redis注册为服务
将redis注册为系统服务,开启自启动 安装服务 默认注册完之后会自动启动,在window中的服务看一下,如果启动类型为自动,状态是自动运行则启动完成。如果是手动,需要右键属性调整为自动,在点击启动,…...
PHP商城案例
http://www.e9933.com/...