发表于 2024.07.27

• 本质上k就是最多可以操作的次数，其中由字符c1变换到字符c2需要操作的次数为min((ord(c1) - ord(c2) % 26, (ord(c1) - ord(c2)) % 26)(要么顺着变化，要么逆着)。为了得到字典序最小的结果，需要从左往右尽可能地将前面的字符翻转成a(两种操作方法中选取代价最小的方法)，如果剩余的次数不足以翻转到a，则往前翻转ASCII序更小的字符。

  为什么在剩余的次数无法到达a的情况下，只能往前翻转得到ASCII序更前的字符，而不尝试往后翻转呢？因为两种操作方法都无法到达a，而往后翻转的办法中，能到达的ASCII序比原字符小的、且所需代价最小的字符就是a，既然这样无法到达a，更不用说b、c等等了。

  class Solution:
      def getSmallestString(self, s: str, k: int) -> str:
          def distance(ch1: str, ch2: str) -> int:
              """ 求解两个字符之间的最小操作次数 """
              ord_ch1 = ord(ch1)
              ord_ch2 = ord(ch2)
              return min((ord_ch1 - ord_ch2) % 26, (ord_ch2 - ord_ch1) % 26)
              
          ans = []
          for ch in s:
              dis_to_a = distance('a', ch)
              if dis_to_a <= k:  # 剩余的次数足够翻转到a
                  k -= dis_to_a
                  ans.append('a')
              else:  # 否则，只能尽可能往前找ASCII序更小的字符
                  ans.append(chr(ord(ch) - k))
                  break
          ans.append(s[len(ans):])  # 将剩余的字符直接拼接到结果中
          return ''.join(ans)

  第一次的做法，在遍历每个位置的时候都从a到z枚举一遍，在操作次数不超过剩余次数的情况下尽可能找到ASCII序最小的字符。

  import string
  
  
  class Solution:
      def getSmallestString(self, s: str, k: int) -> str:
          def distance(ch1: str, ch2: str) -> int:
              ord_ch1 = ord(ch1)
              ord_ch2 = ord(ch2)
              return min((ord_ch1 - ord_ch2) % 26, (ord_ch2 - ord_ch1) % 26)
              
          ans = []
          for ch in s:
              if k == 0:
                  break
              for target in string.ascii_lowercase:  # 从a到z枚举一遍
                  dis = distance(target, ch)
                  if dis <= k:
                      # 操作的次数在剩余次数内, 直接使用该字符
                      ans.append(target)
                      k -= dis
                      break
          ans.append(s[len(ans):])
          return ''.join(ans)

• LC 题目链接