对以下是使用 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; }每一行代码进行解释及备注
时间: 2023-06-27 13:01:38 浏览: 77
C++ 字符串去重排序实例代码
5星 · 资源好评率100%
```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;
}
```
代码解释及备注:
1. 头文件引入
```c++
#include <iostream>
#include <string>
#include <stack>
#include <unordered_map>
```
引入了 `iostream`、`string`、`stack` 和 `unordered_map` 头文件。
2. 命名空间
```c++
using namespace std;
```
使用 `std` 命名空间。
3. 函数定义
```c++
string removeDuplicateLetters(string s) {
```
定义了一个函数 `removeDuplicateLetters`,参数为字符串 `s`,返回值为字符串。
4. 变量定义
```c++
unordered_map<char, bool> visited; // 判断字符是否已经在栈中
unordered_map<char, int> lastOccur; // 记录字符最后出现的位置
```
定义了两个哈希表 `visited` 和 `lastOccur`,用于判断字符是否已经在栈中和记录字符最后出现的位置。
5. 遍历字符串
```c++
for (int i = 0; i < s.length(); i++) {
lastOccur[s[i]] = i;
}
```
遍历字符串 `s`,记录每个字符最后出现的位置。
6. 使用栈去重
```c++
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;
}
```
使用栈对字符串去重,并保证字典序最小。如果当前字符已经在栈中,则跳过。如果栈顶字符比当前字符大,并且栈顶字符在后面还有出现,则弹出栈顶字符。最后将当前字符入栈,并将其标记为已访问。
7. 输出结果
```c++
string result = "";
while (!st.empty()) {
result = st.top() + result;
st.pop();
}
return result;
```
将栈中元素依次弹出,组成去重后的字符串,并返回结果。
8. `main` 函数
```c++
int main() {
string s = "bcabc";
cout << removeDuplicateLetters(s) << endl; // 输出 "abc"
s = "cbacdcbc";
cout << removeDuplicateLetters(s) << endl; // 输出 "acdb"
return 0;
}
```
在 `main` 函数中测试 `removeDuplicateLetters` 函数的效果。
阅读全文