当前位置: 首页 > 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;它决定了数据包如何在网…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩

目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...

23-Oracle 23 ai 区块链表(Blockchain Table)

小伙伴有没有在金融强合规的领域中遇见&#xff0c;必须要保持数据不可变&#xff0c;管理员都无法修改和留痕的要求。比如医疗的电子病历中&#xff0c;影像检查检验结果不可篡改行的&#xff0c;药品追溯过程中数据只可插入无法删除的特性需求&#xff1b;登录日志、修改日志…...

Qt Widget类解析与代码注释

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码&#xff0c;写上注释 当然可以&#xff01;这段代码是 Qt …...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

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 解决方案&…...

Fabric V2.5 通用溯源系统——增加图片上传与下载功能

fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...

JVM 内存结构 详解

内存结构 运行时数据区&#xff1a; Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器&#xff1a; ​ 线程私有&#xff0c;程序控制流的指示器&#xff0c;分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 ​ 每个线程都有一个程序计数…...

提升移动端网页调试效率:WebDebugX 与常见工具组合实践

在日常移动端开发中&#xff0c;网页调试始终是一个高频但又极具挑战的环节。尤其在面对 iOS 与 Android 的混合技术栈、各种设备差异化行为时&#xff0c;开发者迫切需要一套高效、可靠且跨平台的调试方案。过去&#xff0c;我们或多或少使用过 Chrome DevTools、Remote Debug…...