2025-01-07:删除星号以后字典序最小的字符串。用go语言,给定一个字符串 s,其中可能包含任意数量的 '*' 字符。
我们的目标是移除所有的 '*' 字符。
在字符串中只要还有至少一个 '*' 字符,我们可以执行以下操作:
1.删除最左侧的 '*' 字符。
2.同时,删除一个字典序最小的字符。如果存在多个字典序最小的字符,任选其一删除。
最终,我们需要返回在删除所有 '*' 字符后,剩余字符连接成的字典序最小的字符串。
1 <= s.length <= 100000。
s 只含有小写英文字母和 '*' 字符。
输入保证操作可以删除所有的 '*' 字符。
输入:s = "aaba*"。
输出:"aab"。
解释:
删除 '*' 号和它左边的其中一个 'a' 字符。如果我们选择删除 s[3] ,s 字典序最小。
答案2025-01-07:
chatgpt[1]
题目来自leetcode3170。
1.创建一个空字节切片 s
,将给定字符串 S
转换为字节数组存储在 s
中,并初始化一个空的二维切片 st
,用来记录字符串中每个字母的索引位置。
2.初始化一个整数 mask
,用来表示当前字符串中存在的字母,初始值为0。
3.遍历字符串 s
中的每个字符,如果字符不是 '*',则执行以下步骤:
st
中记录该字符出现的索引位置。mask
。4.如果当前字符是 '*',则执行以下步骤:
mask
中最低位的字母索引 k
。st
中取出最后一个索引位置 p
。s
中索引位置为 p
的字符替换为 '*'。st
中更新该字母的索引,删除最后一个索引位置。mask
中移除。5.创建一个新的空字节切片 t
,用于存储处理后的字符串。
6.遍历处理后的字符串 s
,如果字符不是 '*',则将其添加到 t
中。
7.返回 t
组成的字符串。
总的时间复杂度为 O(n),其中 n 是字符串的长度。
额外空间复杂度为 O(n),其中 n 是字符串的长度,主要用来存储 st
和 t
这两个辅助数组。
package main
import(
"fmt"
"math/bits"
)
func clearStars(S string)string{
s :=[]byte(S)
st :=make([][]int,26)
mask :=0
for i, c :=range s {
if c !='*'{
c -='a'
st[c]=append(st[c], i)
mask |=1<< c
}else{
k := bits.TrailingZeros(uint(mask))
p := st[k]
s[p[len(p)-1]]='*'
st[k]= p[:len(p)-1]
iflen(st[k])==0{
mask ^=1<< k
}
}
}
t := s[:0]
for _, c :=range s {
if c !='*'{
t =append(t, c)
}
}
returnstring(t)
}
func main(){
s :="aaba*"
result := clearStars(s)
fmt.Println(result)
}
#include <iostream>
#include <vector>
#include <string>
#include <bitset>
std::string clearStars(std::string S) {
std::vector<std::vector<int>>st(26);
int mask =0;
for(size_t i =0; i < S.size(); i++){
char c = S[i];
if(c !='*'){
c -='a';// 转换字符为对应索引
st[c].push_back(i);// 存储字符的位置
mask |=(1<< c);// 更新掩码
}else{
// 找到最低位的字符
int k = __builtin_ctz(mask);// GCC的内置函数,计算尾随零的个数
if(st[k].empty())continue;// 如果没有该字符就跳过
// 替换最后一个索引的字符为 '*'
int pos = st[k].back();
S[pos]='*';// 将该位置的字符替换为 '*'
st[k].pop_back();// 移除该位置
if(st[k].empty()){
mask ^=(1<< k);// 如果没有字符残留,则清除对应位
}
}
}
// 过滤掉所有的 '*' 字符
std::string result;
for(char c : S){
if(c !='*'){
result += c;// 将不等于 '*' 的字符添加到结果中
}
}
return result;
}
int main() {
std::string s ="aaba*";
std::string result =clearStars(s);
std::cout << result << std::endl;// 输出结果
return0;
}
# -*-coding:utf-8-*-
defclear_stars(S: str)->str:
s =list(S)
st =[[]for _ inrange(26)]# 存放每个字符的位置
mask =0
for i, c inenumerate(s):
if c !='*':
index =ord(c)-ord('a')# 转换字符为对应索引
st[index].append(i)# 存储字符的位置
mask |=(1<< index)# 更新掩码
else:
# 找到最低位的字符
k =(mask &-mask).bit_length()-1# 计算最低位的索引
if st[k]:
pos = st[k].pop()# 替换最后一个索引的字符
s[pos]='*'# 将该位置的字符替换为 '*'
ifnot st[k]:
mask ^=(1<< k)# 如果没有字符残留,则清除对应位
# 过滤掉所有的 '*' 字符
result =''.join(c for c in s if c !='*')# 将不等于 '*' 的字符添加到结果中
return result
defmain():
s ="aaba*"
result = clear_stars(s)
print(result)# 输出结果
if __name__ =="__main__":
main()
[1]
chatgpt: https://chatbotsplace.com/?rc=nnNWSCJ7EP