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

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

🌟 求解思路&实现代码&运行结果


⚡ 贪心

🥦 求解思路
  1. 我们优先把左边的字母变成 a。想把当前的字符变成 a,可以把当前的位置,从左边不断减一到 a,从右边不断加一到 a,二者取最小值,得最小的操作距离返回。
  2. 因为题目限制s到t的distance小于等于k,所有在判断distance距离的时候,如果此时distance小于等于 k,当前位置减少到a,k减少此时distance的距离;否则,如果大于,当前位置直接减少k,直接结束。
  3. 最后返回此时的字符串。
  4. 有了基本的思路,接下来我们就来通过代码来实现一下的解法。
🥦 实现代码
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. 满足距离约束且字典序最小的字符串 + 贪心】

&#x1f680; 算法题 &#x1f680; &#x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 &#x1f340; &#x1f332; 越难的东西,越要努力坚持&#xff0c;因为它具有很高的价值&#xff0c;算法就是这样✨ &#x1f332; 作者简介&#xff1a;硕风和炜&#xff0c;…...

25 Python常用函数——reduce()

在 Python 3.x 中&#xff0c;reduce() 不是内置函数&#xff0c;而是放到了标准库 functools 中&#xff0c;需要先导入再使用。 标准库 functools 中的函数 reduce() 可以将一个接受两个参数的函数以迭代累积的方式从左到右依次作用到一个序列或迭代器对象的所有元素上&#…...

oracle登录报“ORA-27101: shared memory realm does not exist”

oracle登录报“ORA-27101: shared memory realm does not exist” 问题&#xff1a; 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个控件来创建美观、高性能的桌面应用程序&#xff0c;同时还能快速构建企业级办公WPF应用程序。UI for WPF支持MVVM、触摸等&#xff0c;创建的应用程序可靠且结构良好&#xff0c;非常容易维护&#xff0c;其直观的API将无缝地集成Visual Studio…...

IT服务运营过程中的资源要素管理(至简)

在IT服务运营管理过程中&#xff0c;所有资源要投入正式、连续、稳定运行&#xff0c;要保持规范化的管理和标准化的操作&#xff0c;具体包括工具管理、知识管理、服务台管理与评价、备件库管理等内容。 一、工具管理 1、工具的基本运营。见下表&#xff1a; 工具的基本运营…...

wodpress设置固定链接的方式和好处【SEO优化】

设置固定链接的好处 提高用户体验&#xff1a;固定链接使得网址更加直观和易于记忆&#xff0c;用户可以更容易地分享和访问文章。 优化SEO&#xff1a;搜索引擎更倾向于索引具有清晰结构的网址&#xff0c;固定链接有助于提高网站的SEO表现。 避免URL重复&#xff1a;固定链…...

【C#】 CancellationTokenSource 与Thread的启动、取消的区别?

1.Thread的使用 Thread的使用参考&#xff1a;【C#】Thread的使用 2.CancellationTokenSource 的使用 CancellationTokenSource在C#中用于取消长时间运行的操作&#xff0c;如异步或后台任务。它允许你从外部请求一个操作的取消&#xff0c;并且被取消的操作可以通过检查Ca…...

基于 HTML+ECharts 实现智慧运维数据可视化大屏(含源码)

智慧运维数据可视化大屏&#xff1a;基于 HTML 和 ECharts 的实现 在现代企业中&#xff0c;运维管理是确保系统稳定运行的关键环节。随着数据量的激增&#xff0c;如何高效地监控和分析运维数据成为了一个重要课题。本文将介绍如何利用 HTML 和 ECharts 实现一个智慧运维数据可…...

AIGC(Artificial Intelligence Generated Content)

随着人工智能技术的飞速发展&#xff0c;AIGC&#xff08;Artificial Intelligence Generated Content&#xff09;在各个领域的应用日益广泛&#xff0c;其中也包括前端开发的重要部分——CSS&#xff08;层叠样式表&#xff09;的优化。CSS作为网页设计中控制布局和样式的关键…...

02 MySQL数据库管理

目录 1.数据库的结构 sql语言主要由以下几部分组成 2. 数据库与表的创建和管理 1&#xff0c;创建数据库 2&#xff0c;创建表并添加数据 3&#xff0c;添加一条数据 4&#xff0c;查询数据 5&#xff0c;更新数据 6&#xff0c;删除数据 3.用户权限管理 1.创建用户 …...

C++编程: 使用 Nanomsg 进行 PUB-SUB 模式基准测试

文章目录 0. 引言1. Nanomsg简介1.1 可扩展性协议类型1.2 支持的传输机制1.3 NanoMsg 架构与实现 2. PUB-SUB 模式基准测试 0. 引言 Nanomsg 作为一款高性能的通信库&#xff0c;支持多种消息传递模式&#xff0c;其中包括 PUB-SUB&#xff08;发布-订阅&#xff09;。 本篇文…...

【Unity2D 2022:Data】读取csv格式文件的数据

一、创建csv文件 1. 打开Excel&#xff0c;创建xlsx格式文件 2. 编辑卡牌数据&#xff1a;这里共写了两类卡牌&#xff0c;第一类是灵物卡&#xff0c;具有编号、卡名、生命、攻击四个属性&#xff1b;第二类是法术卡&#xff0c;具有编号、卡名、效果三个属性。每类卡的第一…...

美团测开面经整理大汇总!!

大厂测开面经&#xff0c;加油加油&#xff0c;一周看一篇 美团测开面经美团测开暑期实习面经第二弹美团-地图服务部测开一面面经&#xff08;70min&#xff09;美团-优选事业部测开一面面经美团-优选事业部测开二面面经&#xff08;82min&#xff09;美团第一次测开笔试美团测…...

微信公众号获取用户openid(PHP版,snsapi_base模式)

微信公众号获取用户openid的接口有2个&#xff1a;snsapi_base、snsapi_userinfo 详情见微信公众号开发文档&#xff1a;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嵌入式数据库&#xff0c;性能超级棒。它分为多个组件&#xff1a;解析器、逻辑规划器、优化器、物理规划器、执行器以及事务和存储管理层。其中解析器原语PgSQL的解析器&#xff1b;逻辑规划器…...

Vue如何让用户通过a链接点击下载一个excel文档

在Vue中&#xff0c;通过<a>标签让用户点击下载Excel文档&#xff0c;通常需要确保服务器支持直接下载该文件&#xff0c;并且你有一个可以直接访问该文件的URL。以下是一些步骤和示例&#xff0c;展示如何在Vue应用中实现这一功能。 1. 服务器端支持 首先&#xff0c;…...

美摄科技企业级视频拍摄与编辑SDK解决方案

在数字化浪潮汹涌的今天&#xff0c;视频已成为企业传递信息、塑造品牌、连接用户不可或缺的强大媒介。为了帮助企业轻松驾驭这一视觉盛宴的制作过程&#xff0c;美摄科技凭借其在影视级非编技术领域的深厚积累&#xff0c;推出了面向企业的专业视频拍摄与编辑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&#xff09; Redis 采用单线程为什么还这么快 之所以 Redis 采用单线程&#xff08;网络 I/O 和执行命令&#xff09;那么快&#xff0c;有如下几个原因&#xff1a; Redis 的大部分操作都在内存中完成&#xff0c;并且采用了高效的…...

云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?

大家好&#xff0c;欢迎来到《云原生核心技术》系列的第七篇&#xff01; 在上一篇&#xff0c;我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在&#xff0c;我们就像一个拥有了一块崭新数字土地的农场主&#xff0c;是时…...

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

大语言模型如何处理长文本?常用文本分割技术详解

为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的PPT布局自动…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...

sqlserver 根据指定字符 解析拼接字符串

DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...

什么是EULA和DPA

文章目录 EULA&#xff08;End User License Agreement&#xff09;DPA&#xff08;Data Protection Agreement&#xff09;一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA&#xff08;End User License Agreement&#xff09; 定义&#xff1a; EULA即…...

WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)

一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解&#xff0c;适合用作学习或写简历项目背景说明。 &#x1f9e0; 一、概念简介&#xff1a;Solidity 合约开发 Solidity 是一种专门为 以太坊&#xff08;Ethereum&#xff09;平台编写智能合约的高级编…...

uniapp中使用aixos 报错

问题&#xff1a; 在uniapp中使用aixos&#xff0c;运行后报如下错误&#xff1a; AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)

本期内容并不是很难&#xff0c;相信大家会学的很愉快&#xff0c;当然对于有后端基础的朋友来说&#xff0c;本期内容更加容易了解&#xff0c;当然没有基础的也别担心&#xff0c;本期内容会详细解释有关内容 本期用到的软件&#xff1a;yakit&#xff08;因为经过之前好多期…...