前十大证券公司排名k=5：排序后字符记为 a
来源：配资谈谈网论坛
网站：配资平台选择
日期：2025-08-11 06:13:18
查看：50
2025-08-10：变成好标题的最少代价。用go语言，给你一个长度为 n 的字符串 caption。我们把“好标题”定义为：字符串中每个字符都处在某个由至少 3 个相同字母连在一起的区段内（换句话说，字符串被若干长度至少为 3 的相同字母块覆盖）。
举例说明：
• "aaabbb" 和 "aaaaccc" 属于好标题；
• "aabbb"（前两个 a 只有两个）和 "ccccd"（末尾的 d 独自一位）不是好标题。
你可以对任意位置 i（0 ≤ i
任务是：用最少的这种单步改动次数把原字符串变为一个好标题。如果存在多个在操作次数上同样最优的好标题，选择在字典序上最小的那个作为答案；如果无法变成任何好标题，则返回空字符串 ""。
此外，字典序按常规定义比较：从左到右第一个不同字符处字母较靠前的字符串更小；若一字符串是另一字符串的前缀，则较短的那个更小。
1
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
• 示例："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
• 对每个 k 执行以下步骤：
提取子串并排序：取子串 s[i:i+k]，将其字符排序（升序）。排序是为了方便计算最小操作次数。
示例（i=0, k=4 时）：子串 "cdcd" 排序后为 ['c','c','d','d']。
计算操作代价：根据区段长度 k 和排序后的字符，计算将该区段变为全相同字母的最小操作次数：
k=3：排序后字符记为 a, 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')
• 选择最佳候选：对于位置 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'
时间复杂度和额外空间复杂度
• 时间复杂度：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
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)
size[i] = 3
if i+4
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)
if res4
res, mask = res4, mask4
size[i] = 4
}
}
if i+5
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)
if res5
res, mask = res5, mask5
size[i] = 5
}
}
f[i] = res
t[i] = byte(mask >> 24)
}
ans := make([]byte, 0, n)
for i := 0; 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
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)
size[i] = 3
# 长度为4的候选（如果可行）
if i + 4
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)
if res4
res, mask = res4, mask4
size[i] = 4
# 长度为5的候选（如果可行）
if i + 5
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)
if res5
res, mask = res5, mask5
size[i] = 5
f[i] = res
t[i] = (mask >> 24) & 0xFF
# 重建答案
ans_bytes = bytearray
i = 0
while i
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)
·
我们相信Go语言和算法为普通开发者提供了困境的“面试利器”，并致力于分享全面的编程知识。在这里，您可以找到最新的Go语言教程、算法解析、提升面试竞争力的秘籍以及行业动态。
欢迎关注“福大规模架构师每日一题”，让 Go 语言和算法助力您的职业发展
配资平台选择提示：文章来自网络，不代表本站观点。
- 上一篇：股票如何配资但那些能和学员“深度连接”的讲师
- 下一篇：没有了
