对class Solution{ public: string removeDuplicateLetters(string s) { vector<int> count(26, 0); vector<bool> inStack(26, false); stack<char> st; for (char c : s) { count[c - 'a']++; } for (char c : s) { count[c - 'a']--; if (inStack[c - 'a']) { continue; } while (!st.empty() && st.top() > c && count[st.top() - 'a'] > 0) { inStack[st.top() - 'a'] = false; st.pop(); } st.push(c); inStack[c - 'a'] = true; } string ans = ""; while (!st.empty()) { ans += st.top(); st.pop(); } reverse(ans.begin(), ans.end()); return ans; } };进行封装,涉及基本数据结构和容器的,需自行编写相应的类,禁止直接使用STL的数据容器类。
时间: 2023-06-25 07:07:34 浏览: 128
#include<vector> 的用法
好的,对于该题解的代码进行封装的话,我们可以自己实现栈和向量容器类,也可以使用已有的容器类进行封装。以下是使用已有的容器类进行封装的代码:
```cpp
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
class Solution{
public:
std::string removeDuplicateLetters(std::string s){
MyVector<int> count(26, 0);
MyVector<bool> inStack(26, false);
MyStack<char> st;
for (char c : s){count[c - 'a']++;}
for (char c : s){
count[c - 'a']--;
if (inStack[c - 'a']){continue;}
while (!st.empty() && st.top() > c && count[st.top() - 'a'] > 0){
inStack[st.top() - 'a'] = false; st.pop();
}
st.push(c);
inStack[c - 'a'] = true;
}
std::string ans = "";
while (!st.empty()){ans += st.top(); st.pop();}
std::reverse(ans.begin(), ans.end());
return ans;
}
private:
template <typename T>
class MyVector{
public:
MyVector(): size(0), capacity(1), data(new T[capacity]){}
MyVector(int initCapacity, T initValue): size(initCapacity), capacity(initCapacity), data(new T[capacity]){
for (int i = 0; i < size; i++){
data[i] = initValue;
}
}
MyVector(const MyVector& other): size(other.size), capacity(other.capacity), data(new T[capacity]){
for (int i = 0; i < size; i++){
data[i] = other.data[i];
}
}
~MyVector(){delete[] data;}
void push_back(T value){
if (size == capacity){
capacity *= 2;
T* newData = new T[capacity];
for (int i = 0; i < size; i++){
newData[i] = data[i];
}
delete[] data;
data = newData;
}
data[size++] = value;
}
bool empty(){return size == 0;}
int size(){return size;}
T& operator[](int index){return data[index];}
private:
int size;
int capacity;
T* data;
};
template <typename T>
class MyStack{
public:
MyStack(): size(0), capacity(1), data(new T[capacity]){}
~MyStack(){delete[] data;}
void push(T value){
if (size == capacity){
capacity *= 2;
T* newData = new T[capacity];
for (int i = 0; i < size; i++){
newData[i] = data[i];
}
delete[] data;
data = newData;
}
data[size++] = value;
}
void pop(){size--;}
T top(){return data[size - 1];}
bool empty(){return size == 0;}
private:
int size;
int capacity;
T* data;
};
};
```
在这里,我们使用了模板类来实现自己的向量和栈容器类,这样可以方便地适用于不同类型的数据。同时,我们也将向量和栈容器类的实现放在了类内部,防止了与其他代码的命名空间冲突。
阅读全文