2025-08-10：变成好标题的最少代价。用go语言，给你一个长度为 n 的字符串 caption。我们把“好标题”定义为：字

福大大架构师每日一题

发布于 2025-08-13 14:17:13

13900

代码可运行

运行总次数：0

代码可运行

2025-08-10：变成好标题的最少代价。用go语言，给你一个长度为 n 的字符串 caption。我们把“好标题”定义为：字符串中每个字符都处在某个由至少 3 个相同字母连在一起的区段内（换句话说，字符串被若干长度至少为 3 的相同字母块覆盖）。

举例说明：

• "aaabbb" 和 "aaaaccc" 属于好标题；
• "aabbb"（前两个 a 只有两个）和 "ccccd"（末尾的 d 独自一位）不是好标题。

你可以对任意位置 i（0 ≤ i < n）重复执行以下操作：把该位置的字母改为其在字母表上的前一个字母（前提是不是 'a'），或改为后一个字母（前提是不是 'z'）。可以做任意次数的这样的单步改变。

任务是：用最少的这种单步改动次数把原字符串变为一个好标题。如果存在多个在操作次数上同样最优的好标题，选择在字典序上最小的那个作为答案；如果无法变成任何好标题，则返回空字符串 ""。

此外，字典序按常规定义比较：从左到右第一个不同字符处字母较靠前的字符串更小；若一字符串是另一字符串的前缀，则较短的那个更小。

1 <= caption.length <= 5 * 10000。

caption 只包含小写英文字母。

输入：caption = "cdcd"。

输出："cccc"。

解释：

无法用少于 2 个操作将字符串变为好标题。2 次操作得到好标题的方案包括：

"dddd" ：将 caption[0] 和 caption[2] 变为它们后一个字符 'd' 。

"cccc" ：将 caption[1] 和 caption[3] 变为它们前一个字符 'c' 。

由于 "cccc" 字典序比 "dddd" 小，所以返回 "cccc" 。

题目来自力扣3441。

分步骤描述 `minCostGoodCaption` 函数的大体过程

给定函数 minCostGoodCaption 的目标是将输入字符串转换为“好标题”，并最小化操作次数（操作定义为将字符改为其字母表前一个或后一个字母），如果存在多个操作次数相同的最优解，则选择字典序最小的字符串。以下是该函数的详细步骤描述，基于代码逻辑和题目要求。输入示例为 caption = "cdcd"，输出为 "cccc"。

1. 初始检查和边界处理

• 检查字符串长度 n：
- • 如果 n < 3，直接返回空字符串 ""，因为无法形成任何长度至少为 3 的相同字母区段（好标题的基本要求）。
• 示例："cdcd" 的长度 n = 4，大于 2，因此继续处理。

2. 初始化动态规划数组

• 创建三个数组，用于存储动态规划状态：
- • f：长度为 n+1 的整数数组。f[i] 表示从字符串位置 i 开始到末尾的子串转换为好标题所需的最小操作次数。初始时：
  - • f[n] 被隐式初始化为 0（表示空子串的代价为 0）。
  - • f[n-1] 和 f[n-2] 被设置为一个极大值（math.MaxInt/2），因为以位置 n-1 或 n-2 开始的子串长度不足 3，无法形成好标题区段。
- • t：长度为 n+1 的字节数组。t[i] 表示在位置 i 开始的区段所选择的字母（即该区段所有字符将被改为 t[i]）。
- • size：长度为 n 的字节数组。size[i] 表示从位置 i 开始的区段的长度（只能是 3、4 或 5）。
• 示例："cdcd" 中 n=4，初始化 f[4]=0（隐式），f[3] 和 f[2] 设置为极大值。

3. 倒序动态规划（从后向前处理）

• 从位置 i = n-3 开始向前遍历到 i = 0（即从字符串末尾向前处理）。
• 对于每个位置 i，考虑三种可能的区段长度：k = 3, 4, 5（要求 i+k <= n，即区段不能超出字符串末尾）。
• 对每个 k 执行以下步骤：
- • 提取子串并排序：取子串 s[i:i+k]，将其字符排序（升序）。排序是为了方便计算最小操作次数。
  - • 示例（i=0, k=4 时）：子串 "cdcd" 排序后为 ['c','c','d','d']。
- • 计算操作代价：根据区段长度 k 和排序后的字符，计算将该区段变为全相同字母的最小操作次数：
  - • k=3：排序后字符记为 a, b, c（a <= b <= c）。代价为 c - a（因为最优策略是将所有字符变为中位数 b，操作次数为 (b - a) + (c - b) = c - a）。
  - • k=4：排序后字符记为 a, b, c, d。代价为 (c - a) + (d - b)（因为最优策略是将所有字符变为 b 或 c，操作次数相同）。
  - • k=5：排序后字符记为 a, b, c, d, e。代价为 (d - a) + (e - b)（因为最优策略是将所有字符变为中位数 c，操作次数为 (c - a) + (c - b) + (d - c) + (e - c) = d + e - a - b）。
  - • 示例（i=0, k=4）：排序后 a='c', b='c', c='d', d='d'，代价 (d - c) + (d - c) = 1 + 1 = 2。
- • 计算总代价：候选总代价为 cost + f[i+k]，其中 f[i+k] 是从位置 i+k 开始到末尾的子串的最小代价（已提前计算，因为处理顺序是倒序）。
  - • 示例（i=0, k=4）：f[4] = 0，总代价为 2 + 0 = 2。
- • 创建掩码（mask）：在操作代价相同时，掩码用于选择字典序最小的区段序列。掩码是一个 32 位整数，被解释为 4 个字节（从高位到低位：byte3, byte2, byte1, byte0），其构造方式如下：
  - • byte3 总是当前区段的字符（即 t[i]），根据 k 选择：
    - • k=3 或 k=4：取排序后的中位数（k=3 的 b 或 k=4 的 b）。
    - • k=5：取排序后的第三个字符 c。
  - • 低位字节的设置取决于 k，目的是编码后续字符信息以比较字典序：
    - • k=3：byte2, byte1, byte0 都设置为 t[i+3]（即下一个区段的字符）。
    - • k=4：byte2 设置为当前区段字符（b），byte1, byte0 设置为 t[i+4]（即下一个区段的字符）。
    - • k=5：byte2, byte1 设置为当前区段字符（c），byte0 设置为 t[i+5]（即下一个区段的字符）。
  - • 掩码比较规则：作为整数比较，较小的掩码对应字典序较小的字符串（因为高位字节影响更大）。
  - • 示例（i=0, k=4）：排序后 b='c'，假设 t[4] = 0（初始值），掩码为 int('c')<<24 | int('c')<<16 | 0<<8 | 0。
• 选择最佳候选：对于位置 i，比较所有有效 k 的候选（总代价和掩码）：
- • 优先选择总代价最小的候选。
- • 如果总代价相同，选择掩码最小的候选（以得到字典序最小的字符串）。
- • 记录最佳结果到数组：f[i] = best_cost, size[i] = best_k, t[i] = best_character（来自掩码的 byte3）。
• 示例（"cdcd"）：
- • 位置 i=1：只考虑 k=3（因为 i+4=5>4）。子串 "dcd" 排序为 ['c','d','d']，代价 'd' - 'c' = 1，总代价 1 + f[4] = 1。掩码：byte3 = 'd', byte2, byte1, byte0 = t[4] = 0。设置 f[1]=1, size[1]=3, t[1]='d'。
- • 位置 i=0：考虑 k=3 和 k=4（k=5 无效）。
  - • k=3：子串 "cdc" 排序为 ['c','c','d']，代价 'd' - 'c' = 1，但 f[3] 是极大值，总代价无效。
  - • k=4：子串 "cdcd" 排序为 ['c','c','d','d']，代价 2，总代价 2 + f[4] = 2。掩码：byte3 = 'c', byte2 = 'c', byte1, byte0 = t[4]=0。选择此候选。设置 f[0]=2, size[0]=4, t[0]='c'。

4. 构建结果字符串

• 如果 f[0] 为极大值（在代码中未显式检查，但通过初始化隐含），表示无法形成好标题，应返回空字符串。但在处理中，如果 f[0] 有效则继续。
• 使用 t 和 size 数组构建结果字符串：
- • 从位置 i=0 开始。
- • 重复以下直到覆盖整个字符串：
  - • 取 size[i] 个 t[i] 字符，添加到结果缓冲区。
  - • 更新 i = i + size[i]（跳到下一个区段起始位置）。
• 示例（"cdcd"）：i=0, size[0]=4, t[0]='c'，添加 "cccc"，覆盖整个字符串，返回 "cccc"。

5. 处理字典序和最优性

• 在动态规划过程中，掩码确保在操作代价相同时选择字典序最小的区段序列：
- • 掩码的高位字节（byte3）直接对应当前位置的字符，影响字符串的字典序。
- • 低位字节编码后续字符信息，使比较更偏向于较早位置的不同字符。
• 示例："cdcd" 有多个 2 次操作的解（如 "dddd"），但 "cccc" 的掩码更小（'c' < 'd'），因此被选中。

时间复杂度和额外空间复杂度

• 时间复杂度：O(n)。
- • 理由：循环遍历字符串的每个位置（n 次）。每次迭代处理常数个区段长度（3、4、5），每个区段的排序和操作代价计算时间复杂度为 O(1)（因为区段最大长度为 5，排序可视为常数时间）。构建结果字符串也是 O(n)。
- • 总体：O(n) * O(1) = O(n)。
• 额外空间复杂度：O(n)。
- • 理由：使用了三个数组 f（n+1 长度）、t（n+1 长度）、size（n 长度），每个占用 O(n) 空间。排序子串的临时空间可忽略（最大长度 5）。结果缓冲区占用 O(n)。
- • 总体：O(n)。

此方法高效地解决了问题，确保最小操作次数和字典序最优性。

Go完整代码如下：

package main

import (
    "fmt"
    "math"
    "slices"
    "bytes"
)

func minCostGoodCaption(s string)string {
    n := len(s)
    if n < 3 {
        return""
    }

    f := make([]int, n+1)
    f[n-1], f[n-2] = math.MaxInt/2, math.MaxInt/2
    t := make([]byte, n+1)
    size := make([]uint8, n)

    for i := n - 3; i >= 0; i-- {
        sub := []byte(s[i : i+3])
        slices.Sort(sub)
        a, b, c := sub[0], sub[1], sub[2]
        s3 := int(t[i+3])
        res := f[i+3] + int(c-a)
        mask := int(b)<<24 | s3<<16 | s3<<8 | s3 // 4 个 byte 压缩成一个 int，方便比较字典序
        size[i] = 3

        if i+4 <= n {
            sub := []byte(s[i : i+4])
            slices.Sort(sub)
            a, b, c, d := sub[0], sub[1], sub[2], sub[3]
            s4 := int(t[i+4])
            res4 := f[i+4] + int(c-a+d-b)
            mask4 := int(b)<<24 | int(b)<<16 | s4<<8 | s4
            if res4 < res || res4 == res && mask4 < mask {
                res, mask = res4, mask4
                size[i] = 4
            }
        }

        if i+5 <= n {
            sub := []byte(s[i : i+5])
            slices.Sort(sub)
            a, b, c, d, e := sub[0], sub[1], sub[2], sub[3], sub[4]
            res5 := f[i+5] + int(d-a+e-b)
            mask5 := int(c)<<24 | int(c)<<16 | int(c)<<8 | int(t[i+5])
            if res5 < res || res5 == res && mask5 < mask {
                res, mask = res5, mask5
                size[i] = 5
            }
        }

        f[i] = res
        t[i] = byte(mask >> 24)
    }

    ans := make([]byte, 0, n)
    for i := 0; i < n; i += int(size[i]) {
        ans = append(ans, bytes.Repeat([]byte{t[i]}, int(size[i]))...)
    }
    returnstring(ans)
}

func main() {
    caption := "cdcd"
    result := minCostGoodCaption(caption)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

from typing import List

def min_cost_good_caption(s: str) -> str:
    """
    将输入字符串 s 当作字节流处理（按 s.encode('latin1')），
    返回与 Go 版本等价的结果字符串（使用 latin1 解码以保持字节不变）。
    """
    b = s.encode('latin1')  # 以 byte 处理，与 Go 的 []byte 行为一致
    n = len(b)
    if n < 3:
        return""

    INF = 10**9
    f: List[int] = [0] * (n + 1)
    # 模拟 Go 中 f[n-1], f[n-2] = math.MaxInt/2
    f[n-1] = INF
    f[n-2] = INF

    t: List[int] = [0] * (n + 1)  # 存储每段选定的字符（最高字节）
    size: List[int] = [0] * n    # 存储每个位置选的段长（3/4/5）

    for i in range(n - 3, -1, -1):
        # 长度为3的候选
        sub3 = sorted(b[i:i+3])
        a, bb, c = sub3[0], sub3[1], sub3[2]
        s3 = t[i+3]
        res = f[i+3] + (c - a)
        mask = (bb << 24) | (s3 << 16) | (s3 << 8) | s3
        size[i] = 3

        # 长度为4的候选（如果可行）
        if i + 4 <= n:
            sub4 = sorted(b[i:i+4])
            a, bb, c, d = sub4[0], sub4[1], sub4[2], sub4[3]
            s4 = t[i+4]
            res4 = f[i+4] + (c - a + d - bb)
            mask4 = (bb << 24) | (bb << 16) | (s4 << 8) | s4
            if res4 < res or (res4 == res and mask4 < mask):
                res, mask = res4, mask4
                size[i] = 4

        # 长度为5的候选（如果可行）
        if i + 5 <= n:
            sub5 = sorted(b[i:i+5])
            a, bb, c, d, e = sub5[0], sub5[1], sub5[2], sub5[3], sub5[4]
            s5 = t[i+5]
            res5 = f[i+5] + (d - a + e - bb)
            mask5 = (c << 24) | (c << 16) | (c << 8) | s5
            if res5 < res or (res5 == res and mask5 < mask):
                res, mask = res5, mask5
                size[i] = 5

        f[i] = res
        t[i] = (mask >> 24) & 0xFF

    # 重建答案
    ans_bytes = bytearray()
    i = 0
    while i < n:
        seg_len = size[i]
        ch = t[i]
        ans_bytes.extend([ch] * seg_len)
        i += seg_len

    return ans_bytes.decode('latin1')


if __name__ == "__main__":
    caption = "cdcd"
    result = min_cost_good_caption(caption)
    print(result)