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

LeetCode-day27-3106. 满足距离约束且字典序最小的字符串

LeetCode-day27-3106. 满足距离约束且字典序最小的字符串

  • 题目描述
  • 示例
    • 示例1:
    • 示例2:
    • 示例3:
  • 思路
  • 代码

题目描述

给你一个字符串 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。
  2. 如果把 s[i] 变成 a 的操作次数 dis≤k,那么就把 s[i] 变成 a,同时 k 减少 dis。
  3. 否则无法变成 a,直接把 s[i] 减少 k,退出循环。

代码

class Solution:def getSmallestString(self, s: str, k: int) -> str:s = list(s)p = []for i in range(len(s)):p.append(ord(s[i]))for i,x in enumerate(p):dis = min(x- ord('a'),ord('z') - x + 1)if  dis > k:s[i] = chr(x-k)breaks[i] = 'a'k -= disreturn  ''.join(s)

相关文章:

LeetCode-day27-3106. 满足距离约束且字典序最小的字符串

LeetCode-day27-3106. 满足距离约束且字典序最小的字符串 题目描述示例示例1&#xff1a;示例2&#xff1a;示例3&#xff1a; 思路代码 题目描述 给你一个字符串 s 和一个整数 k 。 定义函数 distance(s1, s2) &#xff0c;用于衡量两个长度为 n 的字符串 s1 和 s2 之间的距…...

C++中的static_cast函数

static_cast 是 C 中的一个类型转换操作符&#xff0c;用于在编译时进行类型转换。它主要用于基本数据类型之间的转换&#xff0c;以及类的指针或引用之间的向上转换&#xff08;将派生类指针或引用转换为基类指针或引用&#xff09;和某些情况下的向下转换&#xff08;将基类指…...

从零开始学习网络安全渗透测试之基础入门篇——(二)Web架构前后端分离站Docker容器站OSS存储负载均衡CDN加速反向代理WAF防护

Web架构 Web架构是指构建和管理Web应用程序的方法和模式。随着技术的发展&#xff0c;Web架构也在不断演进。当前&#xff0c;最常用的Web架构包括以下几种&#xff1a; 单页面应用&#xff08;SPA&#xff09;&#xff1a; 特点&#xff1a;所有用户界面逻辑和数据处理都包含…...

2679. 矩阵中的和

两种方法&#xff1a; 第一种&#xff1a;先对二维列表的每一列进行排序&#xff0c;然后对每一列的数据进行逐个比较&#xff0c;找出最大值。 class Solution:def matrixSum(self, nums: list[list[int]]) -> int:result0mlen(nums)nlen(nums[0])for i in range(m):nums…...

Unity Playables:下一代动画与音频序列

Unity的Playables API是一种灵活的系统&#xff0c;用于创建和控制动画、音频以及其他形式的连续媒体序列。它为开发者提供了一种全新的方法来处理游戏中的时间序列&#xff0c;包括动画、音频、特效等。本文将探讨Playables的基本概念、如何使用Playables API实现动画&#xf…...

matlab仿真 模拟调制(下)

&#xff08;内容源自详解MATLAB&#xff0f;SIMULINK 通信系统建模与仿真 刘学勇编著第五章内容&#xff0c;有兴趣的读者请阅读原书&#xff09; clear all ts0.001; t0:ts:10-ts; fs1/ts; dffs/length(t); msgrandi([-3 3],100,1); msg1msg*ones(1,fs/10); msg2reshape(ms…...

RabbitMQ是什么?

RabbitMQ是一个开源的消息代理软件&#xff08;Message Broker&#xff09;&#xff0c;它实现了高级消息队列协议&#xff08;AMQP&#xff0c;Advanced Message Queuing Protocol&#xff09;&#xff0c;并支持多种消息传递协议。它最初由英国的Rabbit Technologies开发&…...

追问试面试系列:分布式id

hi 大家好,欢迎来到追问试面试系列:分布式id 面试中可能面试官不会直接问你分布式id问题,基本上都是因为你在某些面试题回答中提到了,所以就开始追问分布式id相关问题。 先看面试题 ● 面试官:什么是分布式id? ● 面试官:举个例子说说 ● 面试官:什么叫分库分表? ●…...

护网紧急情况应对指南:Linux 应急响应手册

继上一篇&#xff1a;护网紧急情况应对指南&#xff1a;Windows版v1.2全新升级版 之后 收到小伙伴后台要Linux应急手册&#xff0c;今天给大家安排上。 《Linux应急手册》是一本为Linux系统管理员和运维工程师量身打造的实用指南&#xff0c;旨在帮助他们快速应对各种突发状况…...

WEB攻防-通用漏洞-SQL 读写注入-MYSQLMSSQLPostgreSQL

什么是高权限注入 高权限注入指的是攻击者通过SQL注入漏洞&#xff0c;利用具有高级权限的数据库账户&#xff08;如MYSQL的root用户、MSSQL的sa用户、PostgreSQL的dba用户&#xff09;执行恶意SQL语句。这些高级权限账户能够访问和修改数据库中的所有数据&#xff0c;甚至执行…...

【前端学习笔记】CSS基础一

一、什么是CSS 1.CSS 介绍 CSS&#xff08;Cascading Style Sheets&#xff0c;层叠样式表&#xff09;是一种用来控制网页布局和设计外观的样式语言。它使得开发者可以分离网页的内容&#xff08;HTML&#xff09;和表现形式&#xff08;样式&#xff09;&#xff0c;提高了…...

Github遇到的问题解决方法总结(持续更新...)

1.github每次push都需要输入用户名和token的解决方法 push前&#xff0c;执行下面命令 &#xff1a; git config --global credential.helper store 之后再输入一次用户名和token之后&#xff0c;就不用再输入了。 2.git push时遇到“fatal: unable to access https://githu…...

数字信封+数字签名工具类测试样例(Java实现)

加解密过程 加密&#xff1a; 生成加密方SM2密钥对用于签名使用生成的SM2私钥生成数字签名生成SM4对称密钥对明文进行对称加密使用与解密方提前约定好的SM2公钥对第三步中的SM4对称密钥进行非对称加密把【加密方SM2公钥】、【数字签名】、【SM4对称加密后的密文】和【SM2非对…...

The Schematic workflow failed. See above.

在使用 ng new 新建Angular项目的时候会报一个错误&#xff1a;The Schematic workflow failed. See above. 解决办法&#xff1a; 只需要在后面加上 --skip-install 参数&#xff0c;就不会报错了。 ng new myapp --skip-install...

操作系统面试知识点总结4

#来自ウルトラマンメビウス&#xff08;梦比优斯&#xff09; 1 文件系统基础 1.1 文件的相关概念 文件是以计算机硬盘为载体的存储在计算机上的信息集合&#xff0c;可以是文本文档、图片、程序。 文件的结构&#xff1a;数据项、记录、文件&#xff08;有结构文件、无结构式…...

Lua实现面向对象以及类的继承

0.简单前言 1、面向对象主要四个特征&#xff1a;封装&#xff0c;继承&#xff0c;多态&#xff0c;抽象 2、Lua是种简单精致小巧的语言&#xff0c;其本质是个表&#xff08;table&#xff09;&#xff0c;变量和方法皆可看作为该表的元素。 P.S. 该博客和代码为个人编写习…...

机器学习课程学习周报五

机器学习课程学习周报五 文章目录 机器学习课程学习周报五摘要Abstract一、机器学习部分1.1 向量序列作为模型输入1.1.1 文字的向量表达1.1.2 语音的向量表达 1.2 自注意力机制原理1.2.1 自注意力机制理论1.2.2 矩阵运算自注意力机制 1.3 多头自注意力1.4 位置编码1.5 截断自注…...

vue3.0学习笔记(二)——生命周期与响应式数据(ref,reactive,toRef,toRefs函数)

1. 组合API-setup函数 使用细节&#xff1a; setup 是一个新的组件选项&#xff0c;作为组件中使用组合API的起点。从组件生命周期来看&#xff0c;它的执行在组件实例创建之前vue2.x的beforeCreate执行。这就意味着在setup函数中 this 还不是组件实例&#xff0c;this 此时是…...

C++——QT:保姆级教程,从下载到安装到用QT写出第一个程序

登录官网&#xff0c;在官网选择合适的qt版本进行下载 这里选择5.12.9版本 点击exe文件下载&#xff0c;因为服务器在国外&#xff0c;国内不支持&#xff0c;所以可以从我的网盘下载 链接: https://pan.baidu.com/s/1XMILFS1uHTenH3mH_VlPLw 提取码: 1567 --来自百度网盘超级…...

掌握互联网路由选择协议:从基础入门到实战

文章目录 路由选择协议的基本概念路由选择算法的分类分层次的路由选择协议路由信息协议&#xff08;RIP&#xff09;内部网关协议&#xff1a;OSPF外部网关协议&#xff1a;BGP互联网中的实际应用总结 互联网的路由选择协议是网络通信的核心&#xff0c;它决定了数据包如何在网…...

3分钟掌握AnythingLLM浏览器扩展:将任意网页变成AI知识库的终极指南

3分钟掌握AnythingLLM浏览器扩展&#xff1a;将任意网页变成AI知识库的终极指南 【免费下载链接】anything-llm 这是一个全栈应用程序&#xff0c;可以将任何文档、资源&#xff08;如网址链接、音频、视频&#xff09;或内容片段转换为上下文&#xff0c;以便任何大语言模型&a…...

InnoDB的“身体结构”:页、Buffer Pool与Redo Log的底层奥秘

欢迎来到MySQL InnoDB存储引擎的“解剖室”&#xff1b;很多人每天都在写SQL&#xff0c;却从未见过数据在磁盘上真正的模样。当面试官问&#xff1a;“为什么InnoDB比MyISAM快&#xff1f;”或者“数据库宕机了&#xff0c;数据是怎么恢复的&#xff1f;”如果你只能回答“因为…...

5分钟搞定Netdata监控面板汉化:最新GitHub汉化包一键安装教程

Netdata监控面板极速汉化指南&#xff1a;从零到精通的完整解决方案 对于国内开发者而言&#xff0c;英文界面始终是技术工具使用中的一道隐形门槛。Netdata作为一款功能强大的实时监控工具&#xff0c;其全英文的仪表盘让不少运维人员望而却步。本文将带你彻底解决这一痛点&am…...

OpenClaw+Qwen3-VL:30B:低成本智能助手方案

OpenClawQwen3-VL:30B&#xff1a;低成本智能助手方案 1. 为什么选择本地部署的智能助手 去年我在团队内部推动了一个小实验&#xff1a;用公有云的对话API搭建了一个智能助手。三个月后收到账单时&#xff0c;那个数字让我意识到——对于长期运行的自动化任务&#xff0c;按…...

Stable Yogi 模型 Java 开发实战:SpringBoot 微服务集成指南

Stable Yogi 模型 Java 开发实战&#xff1a;SpringBoot 微服务集成指南 最近在做一个智能客服项目&#xff0c;后端用的是 SpringBoot 微服务架构&#xff0c;需要集成一个图像理解模型来处理用户上传的截图。选型的时候&#xff0c;Stable Yogi 模型进入了我们的视野。它不仅…...

深入解析OpenWrt无线初始化:mac80211.sh脚本核心功能与实战应用

1. 初识mac80211.sh&#xff1a;OpenWrt无线初始化的核心引擎 当你第一次刷入OpenWrt固件时&#xff0c;有没有好奇过路由器是如何自动创建无线网络的&#xff1f;这一切的秘密都藏在/lib/wifi/mac80211.sh这个脚本中。作为OpenWrt无线子系统的"大脑"&#xff0c;这个…...

解锁游戏性能新境界:OptiScaler跨平台升级技术深度指南

解锁游戏性能新境界&#xff1a;OptiScaler跨平台升级技术深度指南 【免费下载链接】OptiScaler DLSS replacement for AMD/Intel/Nvidia cards with multiple upscalers (XeSS/FSR2/DLSS) 项目地址: https://gitcode.com/GitHub_Trending/op/OptiScaler 在游戏图形技术…...

记一次 uni-app开发微信小程序 textarea 的“伪遮挡”踩坑实录

文章目录1. 问题描述2. 出现原因3. 解决办法3.1. 给下单按钮添加z-index3.2. 调整textarea的z-index4. 问题解决1. 问题描述 在订单页面中&#xff0c;我使用了 textarea 作为备注输入框&#xff0c;底部有一个固定定位的“下单”按钮。当页面滚动时&#xff0c;textarea 会与…...

ROG游戏本色彩修复与配置还原完全指南

ROG游戏本色彩修复与配置还原完全指南 【免费下载链接】g-helper Lightweight Armoury Crate alternative for Asus laptops. Control tool for ROG Zephyrus G14, G15, G16, M16, Flow X13, Flow X16, TUF, Strix, Scar and other models 项目地址: https://gitcode.com/Git…...

自己搭建永磁同步电机参数变动模块:为预测控制助力

永磁同步电机参数不确定/参数变化/参数失配/参数摄动模块 其中直交轴电感,电阻,磁链&#xff0c;转动惯量&#xff0c;粘滞摩擦系数可设置为自己所需的时变工况 适合做预测控制的同志们 由于MATLAB封装模块不可改动&#xff0c;于是自己搭建了这个模块,默认版本为2021b最近在研…...