【LeetCode:3106. 满足距离约束且字典序最小的字符串 + 贪心】

| 🚀 算法题 🚀 |
🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀
🌲 越难的东西,越要努力坚持,因为它具有很高的价值,算法就是这样✨
🌲 作者简介:硕风和炜,CSDN-Java领域优质创作者🏆,保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎
🌲 恭喜你发现一枚宝藏博主,赶快收入囊中吧🌻
🌲 人生如棋,我愿为卒,行动虽慢,可谁曾见我后退一步?🎯🎯
| 🚀 算法题 🚀 |


🍔 目录
- 🚩 题目链接
- ⛲ 题目描述
- 🌟 求解思路&实现代码&运行结果
- ⚡ 贪心
- 🥦 求解思路
- 🥦 实现代码
- 🥦 运行结果
- 💬 共勉
🚩 题目链接
- 3106. 满足距离约束且字典序最小的字符串
⛲ 题目描述
给你一个字符串 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。想把当前的字符变成 a,可以把当前的位置,从左边不断减一到 a,从右边不断加一到 a,二者取最小值,得最小的操作距离返回。
- 因为题目限制s到t的distance小于等于k,所有在判断distance距离的时候,如果此时distance小于等于 k,当前位置减少到a,k减少此时distance的距离;否则,如果大于,当前位置直接减少k,直接结束。
- 最后返回此时的字符串。
- 有了基本的思路,接下来我们就来通过代码来实现一下的解法。
🥦 实现代码
class Solution {public String getSmallestString(String s, int k) {char[] t = s.toCharArray();for (int i = 0; i < t.length; i++) {int dis = Math.min(t[i] - 'a', 'z' - t[i] + 1);if (dis > k) {t[i] -= k;break;}t[i] = 'a';k -= dis;}return new String(t);}
}
🥦 运行结果

💬 共勉
| 最后,我想和大家分享一句一直激励我的座右铭,希望可以与大家共勉! |


相关文章:
【LeetCode:3106. 满足距离约束且字典序最小的字符串 + 贪心】
🚀 算法题 🚀 🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀 🌲 越难的东西,越要努力坚持,因为它具有很高的价值,算法就是这样✨ 🌲 作者简介:硕风和炜,…...
25 Python常用函数——reduce()
在 Python 3.x 中,reduce() 不是内置函数,而是放到了标准库 functools 中,需要先导入再使用。 标准库 functools 中的函数 reduce() 可以将一个接受两个参数的函数以迭代累积的方式从左到右依次作用到一个序列或迭代器对象的所有元素上&#…...
oracle登录报“ORA-27101: shared memory realm does not exist”
oracle登录报“ORA-27101: shared memory realm does not exist” 问题: 1、使用ip:1521/服务名方式连库报错" ORA-27101: shared memory realm does not exist Linux-x86_64 Error: 2: No such file or directory" 2、sqlplus XX/密码 可以登录数据库 …...
界面控件Telerik UI for WPF 2024 Q2亮点 - 全新的AIPrompt组件
Telerik UI for WPF拥有超过100个控件来创建美观、高性能的桌面应用程序,同时还能快速构建企业级办公WPF应用程序。UI for WPF支持MVVM、触摸等,创建的应用程序可靠且结构良好,非常容易维护,其直观的API将无缝地集成Visual Studio…...
IT服务运营过程中的资源要素管理(至简)
在IT服务运营管理过程中,所有资源要投入正式、连续、稳定运行,要保持规范化的管理和标准化的操作,具体包括工具管理、知识管理、服务台管理与评价、备件库管理等内容。 一、工具管理 1、工具的基本运营。见下表: 工具的基本运营…...
wodpress设置固定链接的方式和好处【SEO优化】
设置固定链接的好处 提高用户体验:固定链接使得网址更加直观和易于记忆,用户可以更容易地分享和访问文章。 优化SEO:搜索引擎更倾向于索引具有清晰结构的网址,固定链接有助于提高网站的SEO表现。 避免URL重复:固定链…...
【C#】 CancellationTokenSource 与Thread的启动、取消的区别?
1.Thread的使用 Thread的使用参考:【C#】Thread的使用 2.CancellationTokenSource 的使用 CancellationTokenSource在C#中用于取消长时间运行的操作,如异步或后台任务。它允许你从外部请求一个操作的取消,并且被取消的操作可以通过检查Ca…...
基于 HTML+ECharts 实现智慧运维数据可视化大屏(含源码)
智慧运维数据可视化大屏:基于 HTML 和 ECharts 的实现 在现代企业中,运维管理是确保系统稳定运行的关键环节。随着数据量的激增,如何高效地监控和分析运维数据成为了一个重要课题。本文将介绍如何利用 HTML 和 ECharts 实现一个智慧运维数据可…...
AIGC(Artificial Intelligence Generated Content)
随着人工智能技术的飞速发展,AIGC(Artificial Intelligence Generated Content)在各个领域的应用日益广泛,其中也包括前端开发的重要部分——CSS(层叠样式表)的优化。CSS作为网页设计中控制布局和样式的关键…...
02 MySQL数据库管理
目录 1.数据库的结构 sql语言主要由以下几部分组成 2. 数据库与表的创建和管理 1,创建数据库 2,创建表并添加数据 3,添加一条数据 4,查询数据 5,更新数据 6,删除数据 3.用户权限管理 1.创建用户 …...
C++编程: 使用 Nanomsg 进行 PUB-SUB 模式基准测试
文章目录 0. 引言1. Nanomsg简介1.1 可扩展性协议类型1.2 支持的传输机制1.3 NanoMsg 架构与实现 2. PUB-SUB 模式基准测试 0. 引言 Nanomsg 作为一款高性能的通信库,支持多种消息传递模式,其中包括 PUB-SUB(发布-订阅)。 本篇文…...
【Unity2D 2022:Data】读取csv格式文件的数据
一、创建csv文件 1. 打开Excel,创建xlsx格式文件 2. 编辑卡牌数据:这里共写了两类卡牌,第一类是灵物卡,具有编号、卡名、生命、攻击四个属性;第二类是法术卡,具有编号、卡名、效果三个属性。每类卡的第一…...
美团测开面经整理大汇总!!
大厂测开面经,加油加油,一周看一篇 美团测开面经美团测开暑期实习面经第二弹美团-地图服务部测开一面面经(70min)美团-优选事业部测开一面面经美团-优选事业部测开二面面经(82min)美团第一次测开笔试美团测…...
微信公众号获取用户openid(PHP版,snsapi_base模式)
微信公众号获取用户openid的接口有2个:snsapi_base、snsapi_userinfo 详情见微信公众号开发文档:https://developers.weixin.qq.com/doc/offiaccount/OA_Web_Apps/Wechat_webpage_authorization.html 本文介绍用PHP方式调用snsapi_base接口获取微信用户…...
DuckDB核心模块揭秘 | 第1期 | 向量化执行引擎之Pipeline
DuckDB核心模块揭秘 | 第1期 | 向量化执行引擎之Pipeline DuckDB是一款非常火的OLAP嵌入式数据库,性能超级棒。它分为多个组件:解析器、逻辑规划器、优化器、物理规划器、执行器以及事务和存储管理层。其中解析器原语PgSQL的解析器;逻辑规划器…...
Vue如何让用户通过a链接点击下载一个excel文档
在Vue中,通过<a>标签让用户点击下载Excel文档,通常需要确保服务器支持直接下载该文件,并且你有一个可以直接访问该文件的URL。以下是一些步骤和示例,展示如何在Vue应用中实现这一功能。 1. 服务器端支持 首先,…...
美摄科技企业级视频拍摄与编辑SDK解决方案
在数字化浪潮汹涌的今天,视频已成为企业传递信息、塑造品牌、连接用户不可或缺的强大媒介。为了帮助企业轻松驾驭这一视觉盛宴的制作过程,美摄科技凭借其在影视级非编技术领域的深厚积累,推出了面向企业的专业视频拍摄与编辑SDK解决方案&…...
MySQL:增删改查、临时表、授权相关示例
目录 概念 数据完整性 主键 数据类型 精确数字 近似数字 字符串 二进制字符串 日期和时间 MySQL常用语句示例 SQL结构化查询语言 显示所有数据库 显示所有表 查看指定表的结构 查询指定表的所有列 创建一个数据库 创建表和列 插入数据记录 查询数据记录 修…...
初识git工具~~上传代码到gitee仓库的方法
目录 1.背景~~其安装 2.gitee介绍 2.1新建仓库 2.2进行相关配置 3.拉取仓库 4.服务器操作 4.1克隆操作 4.2查看本地仓库 4.3代码拖到本地仓库 4.4关于git三板斧介绍 4.4.1add操作 4.4.2commit操作 4.4.3push操作 5.一些其他说明 5.1.ignore说明 5.2git log命令 …...
Redis知识点总价
1 redis的数据结构 2 redis的线程模型 1) Redis 采用单线程为什么还这么快 之所以 Redis 采用单线程(网络 I/O 和执行命令)那么快,有如下几个原因: Redis 的大部分操作都在内存中完成,并且采用了高效的…...
golang循环变量捕获问题
在 Go 语言中,当在循环中启动协程(goroutine)时,如果在协程闭包中直接引用循环变量,可能会遇到一个常见的陷阱 - 循环变量捕获问题。让我详细解释一下: 问题背景 看这个代码片段: fo…...
SciencePlots——绘制论文中的图片
文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了:一行…...
Admin.Net中的消息通信SignalR解释
定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...
【入坑系列】TiDB 强制索引在不同库下不生效问题
文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...
css3笔记 (1) 自用
outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size:0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格ÿ…...
管理学院权限管理系统开发总结
文章目录 🎓 管理学院权限管理系统开发总结 - 现代化Web应用实践之路📝 项目概述🏗️ 技术架构设计后端技术栈前端技术栈 💡 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 🗄️ 数据库设…...
HybridVLA——让单一LLM同时具备扩散和自回归动作预测能力:训练时既扩散也回归,但推理时则扩散
前言 如上一篇文章《dexcap升级版之DexWild》中的前言部分所说,在叠衣服的过程中,我会带着团队对比各种模型、方法、策略,毕竟针对各个场景始终寻找更优的解决方案,是我个人和我司「七月在线」的职责之一 且个人认为,…...
Redis上篇--知识点总结
Redis上篇–解析 本文大部分知识整理自网上,在正文结束后都会附上参考地址。如果想要深入或者详细学习可以通过文末链接跳转学习。 1. 基本介绍 Redis 是一个开源的、高性能的 内存键值数据库,Redis 的键值对中的 key 就是字符串对象,而 val…...
python可视化:俄乌战争时间线关键节点与深层原因
俄乌战争时间线可视化分析:关键节点与深层原因 俄乌战争是21世纪欧洲最具影响力的地缘政治冲突之一,自2022年2月爆发以来已持续超过3年。 本文将通过Python可视化工具,系统分析这场战争的时间线、关键节点及其背后的深层原因,全面…...
[QMT量化交易小白入门]-六十二、ETF轮动中简单的评分算法如何获取历史年化收益32.7%
本专栏主要是介绍QMT的基础用法,常见函数,写策略的方法,也会分享一些量化交易的思路,大概会写100篇左右。 QMT的相关资料较少,在使用过程中不断的摸索,遇到了一些问题,记录下来和大家一起沟通,共同进步。 文章目录 相关阅读1. 策略概述2. 趋势评分模块3 代码解析4 木头…...
