写一个代码解决给Jim一个字符串s(1<= s.length <= 104,s由小写英文字母组成),请Jim去除字符串中重复的字母,使得每个字母只出现一次。需保证返回结果的字典序最小(要求不能打乱其他字符的相对位置),涉及基本数据结构和容器的,需自行编写相应的类,禁止直接使用STL的数据容器类。
时间: 2023-06-27 08:01:43 浏览: 38
以下是使用 C++ 实现的代码,使用了栈和哈希表来实现去重和保证字典序最小:
```c++
#include <iostream>
#include <string>
#include <stack>
#include <unordered_map>
using namespace std;
string removeDuplicateLetters(string s) {
unordered_map<char, bool> visited; // 判断字符是否已经在栈中
unordered_map<char, int> lastOccur; // 记录字符最后出现的位置
// 先遍历一遍字符串,记录每个字符最后出现的位置
for (int i = 0; i < s.length(); i++) {
lastOccur[s[i]] = i;
}
stack<char> st;
for (int i = 0; i < s.length(); i++) {
char c = s[i];
if (visited[c]) { // 如果字符已经在栈中,则跳过
continue;
}
// 如果栈顶字符比当前字符大,并且栈顶字符在后面还有出现,则弹出栈顶字符
while (!st.empty() && st.top() > c && lastOccur[st.top()] > i) {
visited[st.top()] = false;
st.pop();
}
st.push(c); // 当前字符入栈
visited[c] = true;
}
string result = "";
while (!st.empty()) {
result = st.top() + result;
st.pop();
}
return result;
}
int main() {
string s = "bcabc";
cout << removeDuplicateLetters(s) << endl; // 输出 "abc"
s = "cbacdcbc";
cout << removeDuplicateLetters(s) << endl; // 输出 "acdb"
return 0;
}
```