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

举报
福大大架构师每日一题 发表于 2025/08/10 08:19:02 2025/08/10
【摘要】 2025-08-10:变成好标题的最少代价。用go语言,给你一个长度为 n 的字符串 caption。我们把“好标题”定义为:字符串中每个字符都处在某个由至少 3 个相同字母连在一起的区段内(换句话说,字符串被若干长度至少为 3 的相同字母块覆盖)。举例说明:“aaabbb” 和 “aaaaccc” 属于好标题;“aabbb”(前两个 a 只有两个)和 “ccccd”(末尾的 d 独自一位)...

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-1n-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, ca <= b <= c)。代价为 c - a(因为最优策略是将所有字符变为中位数 b,操作次数为 (b - a) + (c - b) = c - a)。
      • k=4:排序后字符记为 a, b, c, d。代价为 (c - a) + (d - b)(因为最优策略是将所有字符变为 bc,操作次数相同)。
      • 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=3k=4:取排序后的中位数(k=3bk=4b)。
        • k=5:取排序后的第三个字符 c
      • 低位字节的设置取决于 k,目的是编码后续字符信息以比较字典序:
        • k=3byte2, byte1, byte0 都设置为 t[i+3](即下一个区段的字符)。
        • k=4byte2 设置为当前区段字符(b),byte1, byte0 设置为 t[i+4](即下一个区段的字符)。
        • k=5byte2, 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=3k=4k=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] 有效则继续。
  • 使用 tsize 数组构建结果字符串:
    • 从位置 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)
    • 理由:使用了三个数组 fn+1 长度)、tn+1 长度)、sizen 长度),每个占用 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)

在这里插入图片描述

【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。