首页 > 其他分享 >2024-09-21:用go语言,给定一个字符串 s,字符串中的每个字符要么是小写字母,要么是问号‘?‘。对于一个仅包含小写字母的字符串t,我们定义cost(i)为在t的前i个字符中与t[i]相同的字

2024-09-21:用go语言,给定一个字符串 s,字符串中的每个字符要么是小写字母,要么是问号‘?‘。对于一个仅包含小写字母的字符串t,我们定义cost(i)为在t的前i个字符中与t[i]相同的字

时间:2024-09-21 14:35:15浏览次数:12  
标签:字符 小写字母 要么 cost limit 字符串 freq

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
	}
	return string(ans)
}

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

在这里插入图片描述

标签:字符,小写字母,要么,cost,limit,字符串,freq
From: https://www.cnblogs.com/moonfdd/p/18423993

相关文章

  • 华为OD机试真题-字符串统计及重排-2024年OD统一考试(E卷)
     最新华为OD机试考点合集:华为OD机试2024年真题题库(E卷+D卷+C卷)_华为od机试题库-CSDN博客     每一题都含有详细的解题思路和代码注释,精编c++、JAVA、Python三种语言解法。帮助每一位考生轻松、高效刷题。订阅后永久可看,持续跟新。题目描述给出一个仅包含字母的字符串......
  • Acwing题解系列——841. 字符串哈希
    #include<iostream>usingnamespacestd;constintN=100010;constintP=131;/*题解https://www.acwing.com/solution/content/24738/可以 把字符串变成一个p进制数字(哈希值),实现不同的字符串映射到不同的数字。采用字符的ascii码乘上P的次方来计算哈希值。X1X2X......
  • Leetcode:交替合并字符串
    问题陈述1768.交替合并字符串给定两个字符串,word1和word2,任务是通过交替字符来合并它们。该过程从word1开始,一直持续到一个字符串用完为止。较长字符串中的任何剩余字符都将附加到合并字符串的末尾。我的思考过程考虑到问题的简单性,我立即认识到两指针方法是最合适的......
  • 字符串匹配——KMP算法
    目录题目描述输入格式输出格式数据范围输入样例输出样例思路解析 纯享版代码题目描述给定一个字符串S,以及一个模式串P,所有字符串中只包含大小写英文字母以及阿拉伯数字。模式串P在字符串S中多次作为子串出现。求出模式串P在字符串S中所有出现的位置的起......
  • python字符串
    字符串string使用单引号''或者双引号""来创建字符串。字符串表达符为:“”str="abcdefcnamceaca"print(str[0:3]):输出abc,从索引0到3(不含)。print(str[1:3]):输出bc,从索引1到3(不含)。print(str[:-1]):输出abcdefghjk,从开头到倒数第一个字符(不含)。print(str[2:-1]):输出cdefghjk,......
  • java 正则表达式 匹配日期格式的字符串
    这个正则表达式 ^\d{4}-\d{2}-\d{2}$ 用于匹配特定格式的字符串,具体来说,它匹配一个由四位数字、一个短横线(-)、接着是两位数字、再一个短横线、最后是两位数字组成的字符串。这种格式通常用于表示日期(年-月-日),但需要注意的是,它并不验证日期的有效性(比如,它不会检查月份是否超过12或......
  • 字符串哈希
    ###&#x20;前置知识字符串hash是指将一个字符串s映射为一个整数,使得该整数尽可能唯一地代表字符串s。涉及知识:进制转换、秦九韶算法。原理秦九韶算法原理对于一个字符串s,其哈希值可以用以下公式计算:其中: s_i表示字符串s的第(i)个字符的ASCII值。 p是......
  • 截取字符串
    在JavaScript中,截取字符串可以通过多种方法实现,主要包括slice()、substring()和substr()方法。以下是对这些方法的详细说明及示例:使用slice()方法函数说明:slice()方法通过指定的开始和结束位置,提取字符串的某个部分,并以新的字符串返回被提取的部分。注意事项:如果star......
  • java基础练习--字符串之罗马数字转换--两种转换方法
    方法1:查表法//数字-->罗马字符publicstaticStringchangeLuoMa(intnumber){String[]arr={"","Ⅰ","Ⅱ","Ⅲ","Ⅳ","Ⅴ","Ⅵ","Ⅶ","Ⅷ","Ⅸ",};return......
  • 字符串指南
    kmpkmp是模式串匹配的算法,本来最坏时间复杂度可以达到$\operatorname{O}(n\timesm)$,但是kmp可以将复杂度优化到$\operatorname{O}(n+m)$。kmp有个很重要的东西,叫做$nxt$失配数组。比如对于一个字符串$s$,它的失配数组$nxt_n$就是$s$的最大前缀等于后缀的长度。$\op......