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;
}
复制代码
评论