前往小程序,Get更优阅读体验!
立即前往
发布
社区首页 >专栏 >2025-01-07:删除星号以后字典序最小的字符串。用go语言,给定一个字符串 s,其中可能包含任意数量的 ‘*‘ 字符。 我

2025-01-07:删除星号以后字典序最小的字符串。用go语言,给定一个字符串 s,其中可能包含任意数量的 ‘*‘ 字符。 我

作者头像
福大大架构师每日一题
发布2025-01-08 14:51:38
发布2025-01-08 14:51:38
410
举报
文章被收录于专栏:福大大架构师每日一题

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 中的每个字符,如果字符不是 '*',则执行以下步骤:

  • • 将该字符转换为索引值(a对应0,b对应1,以此类推)。
  • • 在 st 中记录该字符出现的索引位置。
  • • 将相应的字母位置的比特位设置为1,更新 mask

4.如果当前字符是 '*',则执行以下步骤:

  • • 找到 mask 中最低位的字母索引 k
  • • 从 st 中取出最后一个索引位置 p
  • • 将 s 中索引位置为 p 的字符替换为 '*'。
  • • 在 st 中更新该字母的索引,删除最后一个索引位置。
  • • 如果该字母的索引位置为空,将相应的比特位从 mask 中移除。

5.创建一个新的空字节切片 t,用于存储处理后的字符串。

6.遍历处理后的字符串 s,如果字符不是 '*',则将其添加到 t 中。

7.返回 t 组成的字符串。

总的时间复杂度为 O(n),其中 n 是字符串的长度。

额外空间复杂度为 O(n),其中 n 是字符串的长度,主要用来存储 stt 这两个辅助数组。

Go完整代码如下:

代码语言:javascript
复制
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)
}

C++完整代码如下:

代码语言:javascript
复制
#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;
}

Python完整代码如下:

代码语言:javascript
复制
# -*-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

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2025-01-07,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 福大大架构师每日一题 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 大体步骤如下:
  • Go完整代码如下:
  • C++完整代码如下:
  • Python完整代码如下:
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档