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 是字符串的长度，主要用来存储 st 和 t 这两个辅助数组。

Go完整代码如下：package mainimport ( "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] if len(st[k]) == 0 { mask ^= 1 << k } } } t := s[:0] for _, c := range s { if c != '*' { t = append(t, c) } } return string(t)}func main() { s := "aaba*" result := clearStars(s) fmt.Println(result)}

C++完整代码如下：#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; // 输出结果 return 0;}

Python完整代码如下：# -*-coding:utf-8-*-def clear_stars(S: str) -> str: s = list(S) st = [[] for _ in range(26)] # 存放每个字符的位置 mask = 0 for i, c in enumerate(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] = '*' # 将该位置的字符替换为 '*' if not st[k]: mask ^= (1 << k) # 如果没有字符残留，则清除对应位 # 过滤掉所有的 '*' 字符 result = ''.join(c for c in s if c != '*') # 将不等于 '*' 的字符添加到结果中 return resultdef main(): s = "aaba*" result = clear_stars(s) print(result) # 输出结果if __name__ == "__main__": main()

引用链接

[1] chatgpt: https://chatbotsplace.com/?rc=nnNWSCJ7EP