首页 > 其他分享 >Leetcode每日一题 20240727 3106.满足约束且字典序最小的字符串

Leetcode每日一题 20240727 3106.满足约束且字典序最小的字符串

时间:2024-07-30 23:25:45浏览次数:17  
标签:示例 3106 aaaz aawcd 字符串 操作 Leetcode 20240727 字典

题目描述

给你一个字符串 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 只包含小写英文字母。

解题思路

分析题目
题目说的很绕,很难理解。读题的实厚需要抓住重点,如任意次操作,字典序最小,同时需要满足距离约束条件。
而距离约束条件是给定的一个值k,我们可以转变问题角度,对每次操作不断更新k,而不是去创建空字符串然后不断判断是否满足k。
观察示例
从案例1中可以发现,有点类似从左往右遍历,对于可以变换成a的位置,就变成a。(因为a的字典序最小)。
再看示例2,对于不能变成a的时候,如这个示例的第三个元素x,只能尽可能降低字典序,将x变成w。
代码实现
两步走:
① 拷贝一个相同的字符串。
② 然后遍历字符串,进行字典序的降低操作。
python

class Solution:
    def getSmallestString(self, s: str, k: int) -> str:
        ans = list(s)
        for i, c in enumerate(map(ord, s)):
            tmp = min(c - ord('a'), ord('z') - c + 1)
            if k >= tmp:
                k -= tmp
                ans[i] = 'a'
            else:
                ans[i] = chr(c - k)
                k = 0
        return ''.join(ans)

标签:示例,3106,aaaz,aawcd,字符串,操作,Leetcode,20240727,字典
From: https://blog.csdn.net/2301_76443687/article/details/140743502

相关文章

  • Leetcode每日一题 20240730 2961.双模幂运算
    题目描述给你一个下标从0开始的二维数组variables,其中variables[i]=[ai,bi,ci,mi],以及一个整数target。如果满足以下公式,则下标i是好下标:0<=i<variables.length((aibi%10)ci)%mi==target返回一个由好下标组成的数组,顺序不限。2961.双模幂......
  • 代码随想录算法训练营Day0| LeetCode704: 二分查找
    LeetCode704二分查找先看了一下数组理论基础:数组基础题目链接:704.二分查找啥也没看,凭感觉直接上手:classSolution(object): defsearch(self,nums,target): fornuminnums: ifnum==target: returnnums.index(num) break return-1通过倒是......
  • (nice!!!)LeetCode 2952. 需要添加的硬币的最小数量(贪心、数组)
    题目:2952.需要添加的硬币的最小数量思路:假设区间[1,s-1]的数都可组合得到,当遍历到x=coins[i]时,1、当x<=s时,可以组合的数就是区间[1,s-1]和区间[x,s-1+x]的交集,即区间[1,s-1+x]2、当x>s时,区间[1,s-1]和区间[x,s-1+x]没有交集,那我就只能通过添加一个数来实现了。在这里......
  • leetcode题目总结
    前言本文为leetcode上的题目简单分析总结,仅作记录,欢迎提出建议,共同学习交流。 390.消除游戏列表 arr 由在范围 [1,n] 中的所有整数组成,并按严格递增排序。请你对 arr 应用下述算法:从左到右,删除第一个数字,然后每隔一个数字删除一个,直到到达列表末尾。重复上面的步......
  • LeetCode15 三数之和
    前言题目:15.三数之和文档:代码随想录——三数之和编程语言:C++解题状态:没思路…思路不可包含重复三元组的条件是本题最大的难点,本题的一大思路在与排序后进行去重。代码双指针法classSolution{public:vector<vector<int>>threeSum(vector<int>&nums......
  • LeetCode-day30-2961. 双模幂运算
    LeetCode-day30-2961.双模幂运算题目描述示例示例1:示例2:思路代码题目描述给你一个下标从0开始的二维数组variables,其中variables[i]=[ai,bi,ci,mi],以及一个整数target。如果满足以下公式,则下标i是好下标:0<=i<variables.length((aibi%10)ci)......
  • LeetCode 756. Pyramid Transition Matrix
    原题链接在这里:https://leetcode.com/problems/pyramid-transition-matrix/description/题目:Youarestackingblockstoformapyramid.Eachblockhasacolor,whichisrepresentedbyasingleletter.Eachrowofblockscontains onelessblock thantherowbenea......
  • LeetCode面试150——121买卖股票的最佳时机
    题目难度:简单默认优化目标:最小化平均时间复杂度。Python默认为Python3。目录1题目描述2题目解析3算法原理及程序实现3.1暴力求解3.2动态规划参考文献1题目描述给定一个数组prices,它的第i个元素prices[i]表示一支给定股票第i天的价格。你只能选择......
  • 代码随想录——完全平方数(Leetcode 279)
    题目链接动态规划动态规划思路:状态定义:定义一个一维数组dp,其中dp[i]表示组成整数i所需的最少完全平方数的数量。状态初始化:将dp数组中的所有元素初始化为Integer.MAX_VALUE,表示初始状态下组成每个整数的完全平方数数量是无限大(即不可能)。但dp[0]需要初始化为0,因为组成......
  • 《LeetCode热题100》---<双指针篇四道>
    本篇博客讲解LeetCode热题100道双指针篇中的第一道:移动零(简单)第二道:盛最多水的容器(中等)第一道:移动零(简单)classSolution{publicvoidmoveZeroes(int[]nums){for(intcur=0,dest=-1;cur<nums.length;cur++){//采用双指针......