数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++ 中去除重复字母
假设我们有一个只包含小写字母的字符串。我们需要去除所有重复的字母，使得所有字母只出现一次。并且我们需要以最小的字典序显示结果。所以如果输入是“abccb”，那么结果将是“abc”。
为了解决这个问题，我们将遵循以下步骤：
ans := 一个空字符串
定义一个栈 st
定义一个大小为 26 的数组 onStack
定义一个映射 m
n := s 的大小
初始化 i := 0，当 i < n 时，将 i 增加 1：
将 m[s[i]] 增加 1
初始化 i := 0，当 i < n 时，将 i 增加 1：
定义一个大小为 i 的数组 x = s
将 m[x] 减 1
如果 onStack[x - 'a'] 不为零，则：
跳到下一个迭代，忽略以下部分
当 st 不为空且 x < st.top() 时：
onStack[st 的顶部 - 'a'] := false
从 st 中删除元素
将 x 插入 st
onStack[x - 'a'] := true
当 (st 为空) 为假时：
x := st 的顶部元素
从 st 中删除元素
ans = ans + x
反转数组 rev
返回 ans
示例
让我们看看以下实现来更好地理解：
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
string removeDuplicateLetters(string s) {
string ans = "";
stack <char> st;
vector <int> onStack(26);
map <char, int> m;
int n = s.size();
for(int i = 0; i < n; i++){
m[s[i]]++;
}
for(int i = 0; i < n; i++){
char x = s[i];
m[x]--;
if(onStack[x - 'a'])continue;
while(!st.empty() && x < st.top() && m[st.top()]){
onStack[st.top() - 'a'] = false;
st.pop();
}
st.push(x);
onStack[x - 'a'] = true;
}
while(!st.empty()){
char x = st.top();
st.pop();
ans += x;
}
reverse(ans.begin(), ans.end());
return ans;
}
};
main(){
Solution ob;
cout << (ob.removeDuplicateLetters("abccb"));
}输入
“abccb”
输出
“abc”
更新于: 2020-05-27
152 次浏览
广告