2025-08-10:变成好标题的最少代价。用go语言,给你一个长度为 n 的字符串 caption。我们把“好标题”定义为:字
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]))...)
}
return string(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)
- 点赞
- 收藏
- 关注作者
评论(0)