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

LeetCode 3106.满足距离约束且字典序最小的字符串:模拟(贪心)

【LetMeFly】3106.满足距离约束且字典序最小的字符串:模拟(贪心)

力扣题目链接:https://leetcode.cn/problems/lexicographically-smallest-string-after-operations-with-constraint/

给你一个字符串 s 和一个整数 k

定义函数 distance(s1, s2) ,用于衡量两个长度为 n 的字符串 s1s2 之间的距离,即:

  • 字符 '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 只包含小写英文字母。

解题方法:贪心

首先需要明确,越靠前的位置越重要。所以要不惜一切代价将前面字符尽可能地变小

字符变小的方式有两种:

  1. 往小的方向变。每消耗一次操作次数字符就会变小一点,直到变成了a为止。
  2. 往大的方向变。这样做的前提是剩下的操作次数足够让当前字符变大到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.满足距离约束且字典序最小的字符串&#xff1a;模拟&#xff08;贪心&#xff09; 力扣题目链接&#xff1a;https://leetcode.cn/problems/lexicographically-smallest-string-after-operations-with-constraint/ 给你一个字符串 s 和一个整数 k 。 定义函…...

Elasticsearch 与 MySQL 在查询和插入性能上的深度剖析

在当今的数据处理领域&#xff0c;选择合适的数据库对于应用的性能和效率至关重要。Elasticsearch 和 MySQL 作为两款常用的数据库&#xff0c;它们在查询和插入操作上的性能表现各有千秋。本文将对这两款数据库在这两个关键操作上进行详细的对比分析。 一、引言 随着数据量的…...

day4 vue2以及ElementUI

创建vue2项目 可能用到的命令行们 vue create 项目名称 // 创建项目 cd 项目名称 // 只有进入项目下&#xff0c;才能运行 npm run serve // 运行项目 D: //切换盘符 cd .. // 返回到上一级目录 clear // 清空终端 更改 Vue项目的端口配置 基础语法 项目创建完成之后&#…...

把redis用在Java项目

1. Java连接redis Java连接redis的方式是通过jedis&#xff0c;连接redis需要遵循jedis协议。 1.1 引入依赖 <!--引入java连接redis的驱动--><dependency><groupId>redis.clients</groupId><artifactId>jedis</artifactId><version&…...

GORM:优雅的Go语言ORM库

文章目录 引言GORM原理基础使用安装GORM定义模型连接数据库CRUD操作 高级使用关联事务回调 优点结论 引言 在Go语言开发中&#xff0c;数据库操作是不可或缺的一部分。虽然直接使用SQL语句可以灵活地与数据库交互&#xff0c;但随着项目规模的扩大&#xff0c;SQL语句的编写、…...

Golang | Leetcode Golang题解之第279题完全平方数

题目&#xff1a; 题解&#xff1a; // 判断是否为完全平方数 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&#xff0c;当前系统表空间未加密&#xff1a; SQL> show con_nameCON_NAME ------------------------------ ORCLPDB1SQL> select TABLESPACE_NAME, STATUS, ENCRYPTED from dba_tablespaces;TABLESPACE_NAME STATUS …...

pytorch backbone

1 简介 在PyTorch深度学习中&#xff0c;预训练backbone&#xff08;骨干网络&#xff09;是一个常见的做法&#xff0c;特别是在处理图像识别、目标检测、图像分割等任务时。预训练backbone通常是指在大型数据集&#xff08;如ImageNet&#xff09;上预先训练好的卷积神经网络…...

uniapp 开发app使用renderjs操作dom

需求&#xff1a;把页面中的对话内容另存为一张图片保存到手机相册。 解决方案&#xff1a;这时我们需要使用到document对象创建一个dom对象计算对话内容的宽高、位置等&#xff0c;再利用canvas能力将内容绘制绘制成一张图保存。 现状&#xff1a;总所周知&#xff0c;非H5端&…...

【面试题】MySQL `EXPLAIN`的`Extra`字段:深入解析查询优化的隐藏信息

MySQL EXPLAIN的Extra字段&#xff1a;深入解析查询优化的隐藏信息 引言 在MySQL的EXPLAIN输出中&#xff0c;Extra字段提供了关于查询执行计划的额外信息。这些信息对于理解查询的内部工作机制和优化查询性能至关重要。本文将详细解析Extra字段中常见的几个关键指标&#xf…...

Jenkins持续部署

开发环境任务的代码只要有更新&#xff0c;Jenkins会自动获取新的代码并运行 1. pycharm和git本地集成 获取到下面的 Git可执行文件路径 2. pycharm和gitee远程仓库集成 先在pycharm中安装gitee插件 在设置中找到gitee&#xff0c;点击添加账户&#xff0c;并将自己的账户添…...

橙单前端项目下载编译遇到的问题与解决

今天下载orange-admin前端项目&#xff0c;不过下载下来运行也出现一些问题。 1、运行出现下面一堆错误&#xff0c;如下&#xff1a; 2、对于下面这个错误 error Expected linebreaks to be LF but found CRLF linebreak-style 这就是eslint的报错了&#xff0c;可能是原作者…...

在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字面意思上下文&#xff0c;用于关联管理上下文&#xff0c;具体有如下几个作用 取消信号传递&#xff1a;可以用来传递取消信号&#xff0c;让一个正在执行的函数知道它应该提前终止。超时控制&#xff1a;可以设定一个超时时间&#xff0c;自动取消超过执行时间…...

Linus: vim编辑器的使用,快捷键及配置等周边知识详解

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 vim的安装创建新用户 adduser 用户名Linus是个多用户的操作系统是否有创建用户的权限查看当前用户身份:whoami** 怎么创建设置密码passwdsudo提权(sudo输入的是用户…...

数仓作业延时告警-基于关键路径预推

简介 作业延时告警&#xff0c;通常来说有两种方式&#xff1a; 其一&#xff0c;当作业到目标时间点还没完成触发告警&#xff1b;这类情况&#xff0c;对于目标作业而言&#xff0c;延时已经触发了&#xff0c;风险相对较大&#xff1b;有的是监控接口延时&#xff08;raw层…...

秋招复习笔记——八股文部分:网络TCP

TCP 三次握手和四次挥手 TCP 基本认识 序列号&#xff1a;在建立连接时由计算机生成的随机数作为其初始值&#xff0c;通过 SYN 包传给接收端主机&#xff0c;每发送一次数据&#xff0c;就「累加」一次该「数据字节数」的大小。用来解决网络包乱序问题。 确认应答号&#xf…...

麒麟桌面操作系统上配置Samba

原文链接&#xff1a;麒麟桌面操作系统上配置Samba Hello&#xff0c;大家好啊&#xff01;今天给大家带来一篇关于在麒麟桌面操作系统上配置Samba的文章。Samba是一种免费的软件&#xff0c;实现了SMB/CIFS网络协议&#xff0c;使得Linux和Windows系统之间可以共享文件和打印机…...

【Go】探索 Go 语言的内建函数 copy

山水间歌声回荡 回荡思念的滚烫 去年的家书两行 读来又热了眼眶 云水边静沐暖阳 烟波里久违的故乡 别来无恙 你在心上 &#x1f3b5; 张靓颖/张杰《燕归巢》 在 Go 语言中&#xff0c;copy 是一个用于在切片之间复制元素的内建函数。它提供了一种简单而高…...

C++:std::is_convertible

C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...

Java 8 Stream API 入门到实践详解

一、告别 for 循环&#xff01; 传统痛点&#xff1a; Java 8 之前&#xff0c;集合操作离不开冗长的 for 循环和匿名类。例如&#xff0c;过滤列表中的偶数&#xff1a; List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

ip子接口配置及删除

配置永久生效的子接口&#xff0c;2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...

python报错No module named ‘tensorflow.keras‘

是由于不同版本的tensorflow下的keras所在的路径不同&#xff0c;结合所安装的tensorflow的目录结构修改from语句即可。 原语句&#xff1a; from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后&#xff1a; from tensorflow.python.keras.lay…...

HDFS分布式存储 zookeeper

hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架&#xff0c;允许使用简单的变成模型跨计算机对大型集群进行分布式处理&#xff08;1.海量的数据存储 2.海量数据的计算&#xff09;Hadoop核心组件 hdfs&#xff08;分布式文件存储系统&#xff09;&a…...

软件工程 期末复习

瀑布模型&#xff1a;计划 螺旋模型&#xff1a;风险低 原型模型: 用户反馈 喷泉模型:代码复用 高内聚 低耦合&#xff1a;模块内部功能紧密 模块之间依赖程度小 高内聚&#xff1a;指的是一个模块内部的功能应该紧密相关。换句话说&#xff0c;一个模块应当只实现单一的功能…...

WEB3全栈开发——面试专业技能点P4数据库

一、mysql2 原生驱动及其连接机制 概念介绍 mysql2 是 Node.js 环境中广泛使用的 MySQL 客户端库&#xff0c;基于 mysql 库改进而来&#xff0c;具有更好的性能、Promise 支持、流式查询、二进制数据处理能力等。 主要特点&#xff1a; 支持 Promise / async-await&#xf…...

21-Oracle 23 ai-Automatic SQL Plan Management(SPM)

小伙伴们&#xff0c;有没有迁移数据库完毕后或是突然某一天在同一个实例上同样的SQL&#xff0c; 性能不一样了、业务反馈卡顿、业务超时等各种匪夷所思的现状。 于是SPM定位开始&#xff0c;OCM考试中SPM必考。 其他的AWR、ASH、SQLHC、SQLT、SQL profile等换作下一个话题…...