資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
廣告