2024-05-04:用go语言,给定一个起始索引为0的字符串s和一个整数k。
要进行分割操作,直到字符串s为空:
选择s的最长前缀,该前缀最多包含k个不同字符;
删除该前缀,递增分割计数。如果有剩余字符,它们保持原来的顺序。
在操作之前,可以修改字符串s中的一个字符为另一个小写英文字母。
在最佳情况下修改至多一次字符后,返回操作结束时得到的最大分割数量。
输入:s = "accca", k = 2。
输出:3。
答案2024-05-04:
chatgpt
题目来自leetcode3003。
大体步骤如下:
1.创建一个递归函数,用于计算分割得到的最大数量。
dfs
2.函数中,首先检查是否到达字符串末尾,若是则返回 1(表示完成一个分割)。
3.使用记录中间结果,加快计算速度。
memo
4.对于当前处理的字符,如果不将其作为新的分割点,继续处理下一个字符。
s[i]
5.如果将作为新的分割点,并且新的字符数量不超过,则继续向后处理。
s[i]
k
6.如果未修改过字符,则尝试修改为其他26个小写字母,然后继续考虑分割带来的最大数量。
s[i]
7.在每一步中,根据是否修改过字符,记录当前的最大分割数量。
8.最终返回得到的最大分割数量。
总的时间复杂度为 $O(n \cdot 2^{26})$,其中$n$为字符串长度,$2^{26}$表示尝试修改字符的可能性数目。
总的额外空间复杂度为$O(n \cdot 2^{26})$,主要由中间结果记录所占用的空间引起。
memo
Go完整代码如下:
packagemain
import(
"fmt"
"math/bits"
)
funcmax(x,yint)int{
ifx>y{
returnx
}
returny
}
funcmaxPartitionsAfterOperations(sstring,kint)int{
n:=len(s)
typeargsstruct{
i,maskint
changedbool
}
memo:=map[args]int{}
vardfsfunc(int,int,bool)int
dfs=func(i,maskint,changedbool)(resint){
ifi==n{
return1
}
a:=args{i,mask,changed}
ifv,ok:=memo[a];ok{//之前计算过
returnv
}
//不改s[i]
bit:=1<<(s[i]-'a')
newMask:=mask|bit
ifbits.OnesCount(uint(newMask))>k{
//分割出一个子串,这个子串的最后一个字母在i-1
//s[i]作为下一段的第一个字母,也就是bit作为下一段的mask的初始值
res=dfs(i+1,bit,changed)+1
}else{//不分割
res=dfs(i+1,newMask,changed)
}
if!changed{
//枚举把s[i]改成a,b,c,...,z
forj:=0;j<26;j++{
newMask:=mask|1<ifbits.OnesCount(uint(newMask))>k{
//分割出一个子串,这个子串的最后一个字母在i-1
//j作为下一段的第一个字母,也就是1<
res=max(res,dfs(i+1,1<}else{//不分割
res=max(res,dfs(i+1,newMask,true))
}
}
}
memo[a]=res//记忆化
returnres
}
returndfs(0,0,false)
}
funcmain(){
s:="accca"
k:=2
result:=maxPartitionsAfterOperations(s,k)
fmt.Println(result)
}
Python完整代码如下:
#-*-coding:utf-8-*-
defmax_partitions_after_operations(s,k):
n=len(s)
memo={}
defdfs(i,mask,changed):
ifi==n:
return1
a=(i,mask,changed)
ifainmemo:
returnmemo[a]
res=0
bit=1<<(ord(s[i])-ord('a'))
new_mask=mask|bit
ifbin(new_mask).count('1')>k:
res=dfs(i+1,bit,changed)+1
else:
res=dfs(i+1,new_mask,changed)
ifnotchanged:
forjinrange(26):
new_mask=mask|1<ifbin(new_mask).count('1')>k:
res=max(res,dfs(i+1,1<else:
res=max(res,dfs(i+1,new_mask,True))
memo[a]=res
returnres
returndfs(0,0,False)
s="accca"
k=2
result=max_partitions_after_operations(s,k)
print(result)
特别声明:以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布,本平台仅提供信息存储服务。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.