写点什么

2023-11-29:用 go 语言,给你一个字符串 s ,请你去除字符串中重复的字母,使得每个字母只出现一次。 需保证 返回结果的字典序最小。 要求不能打乱其他字符的相对位置)。 输入:s = “cba

  • 2023-11-29
    北京
  • 本文字数:2392 字

    阅读完需:约 8 分钟

2023-11-29:用 go 语言,给你一个字符串 s ,请你去除字符串中重复的字母,使得每个字母只出现一次。


需保证 返回结果的字典序最小。


要求不能打乱其他字符的相对位置)。


输入:s = "cbacdcbc"。


输出:"acdb"。


来自左程云


答案 2023-11-29:


所有的代码用灵捷3.5编写,感觉有点抽风了,生成的代码需要修改才能运行。

大体过程如下:

1.初始化一个长度为 26 的整数数组 cnts,用于记录字符串中每个字母出现的次数。


2.初始化一个长度为 26 的布尔数组 enter,用于标记字母是否已经入栈。


3.遍历字符串 s 中的每个字符,统计每个字母出现的次数,并更新到 cnts 数组中。


4.初始化一个长度为 26 的字节数组 stack 作为栈,用于存储最终的结果。


5.初始化一个整数变量 size,表示当前栈的大小,初始值为 。


6.遍历字符串 s 中的每个字符:


6.1.将当前字符存储在变量 cur 中。


6.2.如果 cur 还未入栈,则执行以下操作:


6.2.1.判断栈是否为空或者栈顶元素小于等于 cur,或者栈顶元素在剩余字符中不再出现时退出循环。


6.2.2.将栈顶元素标记为未入栈(即 enter[stack[size-1]-'a'] 设为 false)。


6.2.3.将栈顶元素出栈。


6.2.4.更新栈的大小(即 size--)。


6.3.将 cur 入栈。


6.4.将 cur 标记为已入栈(即 enter[cur-'a'] 设为 true)。


6.5.将 cur 的出现次数减一。


7.根据栈中的元素构造移除重复字母后的结果字符串,并将其返回。


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


总的额外空间复杂度:O(1),因为使用了固定长度的数组和栈,与输入规模无关。

go 完整代码如下:

package main
import "fmt"
func removeDuplicateLetters(s string) string {
cnts := make([]int, 26) enter := make([]bool, 26)
for _, ch := range s { cnts[ch-'a']++ }
stack := make([]byte, 26) size := 0
for i := 0; i < len(s); i++ { cur := s[i] if !enter[cur-'a'] { for size > 0 && stack[size-1] > cur && cnts[stack[size-1]-'a'] > 0 { enter[stack[size-1]-'a'] = false size-- } stack[size] = cur size++ enter[cur-'a'] = true } cnts[cur-'a']-- }
return string(stack[:size])}
func main() { s := "cbacdcbc" result := removeDuplicateLetters(s) fmt.Println(result)}
复制代码


rust 完整代码如下:

fn remove_duplicate_letters(s: String) -> String {    let mut cnts: [i32; 26] = [0; 26];    let mut enter: [bool; 26] = [false; 26];    let mut stack: Vec<u8> = Vec::new();
for ch in s.chars() { cnts[(ch as u8 - b'a') as usize] += 1; }
for cur in s.bytes() { let cur_index = (cur - b'a') as usize; if !enter[cur_index] { while let Some(&top) = stack.last() { let top_index = (top - b'a') as usize; if top > cur && cnts[top_index] > 0 { enter[top_index] = false; stack.pop(); } else { break; } } stack.push(cur); enter[cur_index] = true; } cnts[cur_index] -= 1; }
String::from_utf8(stack).unwrap()}
fn main() { let s = String::from("cbacdcbc"); let result = remove_duplicate_letters(s); println!("{}", result);}
复制代码


c++完整代码如下:

#include <iostream>#include <string>#include <vector>#include <cstring>
std::string removeDuplicateLetters(std::string s) { std::vector<int> cnts(26, 0); std::vector<bool> enter(26, false); std::vector<char> stack(26, '\\'); int size = 0;
for (char ch : s) { cnts[ch - 'a']++; }
for (char cur : s) { int curIndex = cur - 'a'; if (!enter[curIndex]) { while (size > 0&& stack[size - 1] > cur && cnts[stack[size - 1] - 'a'] > 0) { enter[stack[size - 1] - 'a'] = false; size--; } stack[size] = cur; size++; enter[curIndex] = true; } cnts[curIndex]--; }
return std::string(stack.begin(), stack.begin() + size);}
int main() { std::string s = "cbacdcbc"; std::string result = removeDuplicateLetters(s); std::cout << result << std::endl; return 0;}
复制代码


c 完整代码如下:

#include <stdio.h>#include <stdlib.h>#include <string.h>
char* removeDuplicateLetters(char* s) { int cnts[26] = {0}; int enter[26] = {0}; char stack[26]; int size = 0;
for (int i = 0; s[i] != '\\'; i++) { cnts[s[i] - 'a']++;}
for (int i = 0; s[i] != '\\'; i++) { char cur = s[i]; if (!enter[cur - 'a']) { while (size > 0&& stack[size - 1] > cur && cnts[stack[size - 1] - 'a'] > 0) { enter[stack[size - 1] - 'a'] = 0; size--; } stack[size] = cur; size++; enter[cur - 'a'] = 1; }cnts[cur - 'a']--; }
char* result = (char*)malloc(sizeof(char) * (size + 1)); memcpy(result, stack, size); result[size] = '\\';
return result;}
int main() { char* s = "cbacdcbc"; char* result = removeDuplicateLetters(s); printf("%s\n", result); free(result); return 0;}
复制代码



发布于: 刚刚阅读数: 4
用户头像

公众号:福大大架构师每日一题 2021-02-15 加入

公众号:福大大架构师每日一题

评论

发布
暂无评论
2023-11-29:用go语言,给你一个字符串 s ,请你去除字符串中重复的字母,使得每个字母只出现一次。 需保证 返回结果的字典序最小。 要求不能打乱其他字符的相对位置)。 输入:s = “cba_福大大架构师每日一题_福大大架构师每日一题_InfoQ写作社区