力扣每日一题 6/27 字符串 贪心

avatar
作者
猴君
阅读量:0
  • 博客主页:誓则盟约
  • 系列专栏:IT竞赛 专栏
  • 关注博主,后期持续更新系列文章
  • 如果有错误感谢请大家批评指出,及时修改
  • 感谢大家点赞👍收藏⭐评论✍ 

2734.执行子串操作后的字典序最小字符串【中等

题目:

给你一个仅由小写英文字母组成的字符串 s 。在一步操作中,你可以完成以下行为:

  • 选择 s 的任一非空子字符串,可能是整个字符串,接着将字符串中的每一个字符替换为英文字母表中的前一个字符。例如,'b' 用 'a' 替换,'a' 用 'z' 替换。

返回执行上述操作 恰好一次 后可以获得的 字典序最小 的字符串。

子字符串 是字符串中的一个连续字符序列。

现有长度相同的两个字符串 x 和 字符串 y ,在满足 x[i] != y[i] 的第一个位置 i 上,如果  x[i] 在字母表中先于 y[i] 出现,则认为字符串 x 比字符串 y 字典序更小 。

示例 1:

输入:s = "cbabc" 输出:"baabc" 解释:我们选择从下标 0 开始、到下标 1 结束的子字符串执行操作。  可以证明最终得到的字符串是字典序最小的。 

示例 2:

输入:s = "acbbc" 输出:"abaab" 解释:我们选择从下标 1 开始、到下标 4 结束的子字符串执行操作。 可以证明最终得到的字符串是字典序最小的。 

示例 3:

输入:s = "leetcode" 输出:"kddsbncd" 解释:我们选择整个字符串执行操作。 可以证明最终得到的字符串是字典序最小的。 

提示:

  • 1 <= s.length <= 3 * 10**5
  • s 仅由小写英文字母组成

分析问题:

        读题意,可以知道这道题就是在从前往后遍历把每个非a的字母都变成它之前的小写字母,这里可以用ASCLL码进行实现,并且只能选择一个子序列。什么意思呢? 就是只能选择在两个a中间夹着的一个子序列,或者是一个a前面的子序列,如果前面的子序列为空字符串,那么就是a后面的子序列。

        需要注意的是,这里必须要操作一次,也就是说如果s全是a的话,也必须要执行一次操作,那么当然是选最后的一个a将其变成z是字典序最小的情况。

        思路很简单,总的来说就是把字符串以‘a’为标志分隔,取最前面一个不空的字符串作为我们选择的子字符串来修改。

        这种思路虽然是正确的,但是复杂度太高,代码太复杂,需要处理的细节很多。所以我们可以对该代码进一步优化

优化思路如下:

  1. 首先获取输入字符串 s 的长度 n ,并初始化一个索引 i 为 0 。
  2. 通过一个 while 循环,从字符串的开头开始,找到第一个不是 'a' 的字符的位置 i 。
  3. 如果整个字符串都是 'a' (即 i == n ),那么将字符串的最后一个字符改为 'z' 并返回。
  4. 然后初始化另一个索引 j = i ,通过另一个 while 循环,从位置 i 开始找到第一个 'a' 的位置 j 。
  5. 对于从位置 i 到位置 j 的这部分子串,将每个字符的 ASCII 值减 1 ,得到新的子串。
  6. 最后将原始字符串的前 i 个字符、新生成的子串和位置 j 之后的字符拼接起来返回。

代码实现:

优化前:
class Solution:     def smallestString(self, s: str) -> str:         # 如果字符串中没有 'a'         if s.count('a')==0:             # 将字符串转换为列表以便修改元素             s,v = list(s),''             # 遍历列表,将每个字符的 ASCII 值减 1             for i in range(len(s)):                 s[i] = chr(ord(s[i]) - 1)              # 将修改后的列表元素重新组合成字符串             for l in s:                  v += l         else:             # 计算字符串中 'a' 的个数             n = s.count('a')             # 按 'a' 分割字符串并转换为列表             ls = list(s.split('a'))             key = ''             b = ''             # 找到第一个非空的子串             for k in ls:                 if k!= '':                     key = k                     b = k                     break             # 如果没有找到非空子串             if key == '':                  return s[:-1] + 'z'             # 将非空子串转换为列表             key = list(key)             # 遍历非空子串列表,将每个字符的 ASCII 值减 1             for j in range(len(key)):                 key[j] = chr(ord(key[j]) - 1)             p = ''             # 将修改后的非空子串列表元素重新组合成字符串             for l in key:                  p += l             # 将修改后的非空子串放回原列表中             ls[ls.index(b)] = p             v = ''             # 重新组合处理后的列表为字符串,并在适当位置插入 'a'             for j in ls:                 if j == '' and n > 0:                     v += 'a'                     n -= 1                 else:                      v += j                     if n > 0:                         v += 'a'                         n -= 1         # 如果处理后的字符串与原始字符串不同         if v!= s:             return v         # 如果处理后的字符串与原始字符串相同,将最后一个字符改为 'z' 并返回         return v[:-1] + 'z'


优化后: 
class Solution:     def smallestString(self, s: str) -> str:         n = len(s)         i = 0         while i < n and s[i] =='a':             i +=1         if i == n:             return s[:-1] + "z"         j = i         while j< n and s[j] != 'a':             j+=1         return s[:i] + "".join(chr(ord(c) - 1) for c in s[i:j]) + s[j:]


  总结:

考点

  1. 字符串的遍历和索引操作。
  2. 条件判断(while 循环的条件)。
  3. 字符的 ASCII 值操作(通过 ord 和 chr 函数)。

收获

  1. 加深了对字符串处理的理解,包括如何遍历和根据条件提取子串。
  2. 学会了使用 ord 和 chr 函数来操作字符的 ASCII 值,实现对字符的修改。
  3. 掌握了通过多个索引和循环来处理字符串中特定部分的技巧。
  4. 提高了在处理复杂字符串问题时的逻辑思维和代码实现能力。

“恋爱本质不是走向婚姻,而是探究最真实的自己。” ——《青春杂货铺》

广告一刻

为您即时展示最新活动产品广告消息,让您随时掌握产品活动新动态!