2024-09-21：用go语言，给定一个字符串 s，字符串中的每个字符要么是小写字母，要么是问号‘?‘。对于一个仅包含小写字母

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：

chatgpt

题目来自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
}
returnstring(ans)
}

func main(){
    s :="???"
    fmt.Println(minimizeStringValue(s))
}