AJohn Blog

外观

10.3 字符串贪心

约 761 字大约 3 分钟

2025-05-26

10.3.1 字典序最小/最大

字典序的定义如下：

  • 对于两个字符串 a 和 b，从左到右依次比较 a[i] 和 b[i] 的字符 ASCII 值的大小。
  • a[i]!=b[i] 时，如果 a[i]<b[i]，那么 a 的字典序更小，否则 b 的字典序更小。
  • 如果没有出现 a[i]!=b[i]，则短的字符串字典序更小。
  • 如果两个字符串的长度和内容均相同，那么两个字符串的字典序一样。

字典序的定义也可以推广到数组上，按照上述方法比较两个数组的字典序。

  1. 1323. 6 和 9 组成的最大数字

    给你一个仅由数字 6 和 9 组成的正整数 num。你最多只能翻转一位数字，将 6 变成 9，或者把 9 变成 6 。请返回你可以得到的最大数字。
    示例 1：

    输入：num = 9669
    输出：9969
    解释：
    改变第一位数字可以得到 6669 。
    改变第二位数字可以得到 9969 。
    改变第三位数字可以得到 9699 。
    改变第四位数字可以得到 9666 。
    其中最大的数字是 9969 。

    提示

    思路：转换成字符串调用 replace 函数即可。

    class Solution:
def maximum69Number (self, num: int) -> int:
    return int(str(num).replace('6', '9', 1))

    时间复杂度：O(n)O(n)，其中 n 为 num 的长度。

    空间复杂度：O(n)O(n)。

  2. 3216. 交换后字典序最小的字符串

    给你一个仅由数字组成的字符串 s，在最多交换一次 相邻 且具有相同 奇偶性 的数字后，返回可以得到的字典序最小的字符串。如果两个数字都是奇数或都是偶数，则它们具有相同的奇偶性。例如，5 和 9、2 和 4 奇偶性相同，而 6 和 9 奇偶性不同。
    示例 1：

    输入： s = "45320"
    输出： "43520"
    解释：
    s[1] == '5' 和 s[2] == '3' 都具有相同的奇偶性，交换它们可以得到字典序最小的字符串。

    提示

    思路：从第二个数字开始遍历，如果比上一个数字小，且这两个数字奇偶性相同（相加为偶数），则交换位置，最后返回交换后的字符串。

    class Solution:
def getSmallestString(self, s: str) -> str:
    l = list(s)
    for i in range(1, len(l)):
        if l[i - 1] > l[i] and (int(l[i - 1]) + int(l[i])) % 2 == 0:
            l[i - 1], l[i] = l[i], l[i - 1]
            break
    return ''.join(l)

    时间复杂度：O(n)O(n)，其中 n 为 s 的长度。

    空间复杂度：O(n)O(n)。