当前位置: 首页 > 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 是一个用于在切片之间复制元素的内建函数。它提供了一种简单而高…...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

7.4.分块查找

一.分块查找的算法思想&#xff1a; 1.实例&#xff1a; 以上述图片的顺序表为例&#xff0c; 该顺序表的数据元素从整体来看是乱序的&#xff0c;但如果把这些数据元素分成一块一块的小区间&#xff0c; 第一个区间[0,1]索引上的数据元素都是小于等于10的&#xff0c; 第二…...

django filter 统计数量 按属性去重

在Django中&#xff0c;如果你想要根据某个属性对查询集进行去重并统计数量&#xff0c;你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求&#xff1a; 方法1&#xff1a;使用annotate()和Count 假设你有一个模型Item&#xff0c;并且你想…...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...

排序算法总结(C++)

目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指&#xff1a;同样大小的样本 **&#xff08;同样大小的数据&#xff09;**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...

MySQL JOIN 表过多的优化思路

当 MySQL 查询涉及大量表 JOIN 时&#xff0c;性能会显著下降。以下是优化思路和简易实现方法&#xff1a; 一、核心优化思路 减少 JOIN 数量 数据冗余&#xff1a;添加必要的冗余字段&#xff08;如订单表直接存储用户名&#xff09;合并表&#xff1a;将频繁关联的小表合并成…...

接口自动化测试:HttpRunner基础

相关文档 HttpRunner V3.x中文文档 HttpRunner 用户指南 使用HttpRunner 3.x实现接口自动化测试 HttpRunner介绍 HttpRunner 是一个开源的 API 测试工具&#xff0c;支持 HTTP(S)/HTTP2/WebSocket/RPC 等网络协议&#xff0c;涵盖接口测试、性能测试、数字体验监测等测试类型…...

android13 app的触摸问题定位分析流程

一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...