2024-09-21:用go语言,给定一个字符串 s,字符串中的每个字符要么是小写字母,要么是问号'?'。对于一个仅包含小写字母的字符串t,我们定义cost(i)为在t的前i个字符中与t[i]相同的字符的出现次数。
字符串 t 的分数是所有位置i的cost(i)之和。
现在的任务是用小写字母替换所有的问号'?',使得字符串s的分数最小。如果有多个替换方案使得分数最小,那么返回字典序最小的一个。
输入:s = "???"。
输出: "abc"。
解释:这个例子中,我们将 s 中的问号 '?' 替换得到 "abc" 。
对于字符串 "abc" ,cost(0) = 0 ,cost(1) = 0 和 cost(2) = 0 。
"abc" 的分数为 0 。
其他修改 s 得到分数 0 的字符串为 "cba" ,"abz" 和 "hey" 。
这些字符串中,我们返回字典序最小的。
大体步骤如下:
1.初始化一个大小为27的整型数组freq,用于记录每个字符出现的次数,初始全部为0,26号位作为哨兵。
2.遍历字符串s,若字符不是'?',则在freq相应位置累加。
3.对freq数组进行排序,得到排序后的数组f。
4.统计字符串s中问号'?'的个数q,初始化limit和extra为0。
5.从1开始遍历数组f,计算每个字符值变化产生的增加的字符数sum。
6.若问号数量小于等于sum,则更新limit和extra,并跳出循环。
7.根据limit和extra更新目标替换数组target,将出现次数不超过limit的字符值更新为limit,如果extra大于0,则额外分配给字符值较小的字符。
8.遍历字符串s,遇到问号'?'时用目标数组target替换,替换顺序为字典序最小。
9.返回替换后的字符串作为最终结果。
总体复杂度分析
-
时间复杂度:遍历字符串s的时间复杂度为O(n),排序时间复杂度为O(nlogn),整体时间复杂度为O(nlogn)。
-
空间复杂度:除了字符串s本身外,额外使用了大小为27的整型数组freq和target,以及一些辅助变量,总的额外空间复杂度较小,为O(1)。
答案2024-09-21:
题目来自leetcode3081。
go完整代码如下:
package main
import (
"fmt"
"math"
"slices"
"strings"
)
func minimizeStringValue(s string) string {
freq := [27]int{26: math.MaxInt / 26} // 哨兵
for _, c := range s {
if c != '?' {
freq[c-'a']++
}
}
f := freq
slices.Sort(f[:])
var limit, extra int
q := strings.Count(s, "?")
for i := 1; ; i++ {
sum := i * (f[i] - f[i-1])
if q <= sum {
limit, extra = f[i-1]+q/i, q%i
break
}
q -= sum
}
target := freq
for i, c := range freq[:26] {
if c > limit {
continue
}
target[i] = limit
if extra > 0 { // 还可以多分配一个
extra--
target[i]++
}
}
ans := []byte(s)
j := byte(0)
for i, c := range ans {
if c != '?' {
continue
}
for freq[j] == target[j] {
j++
}
freq[j]++
ans[i] = 'a' + j
}
return string(ans)
}
func main() {
s := "???"
fmt.Println(minimizeStringValue(s))
}
标签:字符,小写字母,要么,cost,limit,字符串,freq
From: https://www.cnblogs.com/moonfdd/p/18423993