开刷，先过一下STL容器的使用规则
232. Implement Queue using Stacks
Solution:主要思路就是用两个开口方向的栈来模拟队列的过程
class MyQueue {
public:
stack<int> in;
stack<int> out;
MyQueue() {
}
void push(int x) {
in.push(x);
}
int pop() {
if(out.empty()){
while(!in.empty()){
out.push(in.top());
in.pop();
}
}
int result = out.top();
out.pop();
return result;
}
int peek() {
int res = this->pop(); // use pointer
out.push(res);
return res;
}
bool empty() {
return in.empty() && out.empty();
}
};
225. Implement Stack using Queues
Solution: 用一个队列就可以实现了
class MyStack {
public:
queue<int> que;
MyStack() {
}
void push(int x) {
que.push(x);
}
int pop() {
int size = que.size();
size--;
while(size--){
que.push(que.front());
que.pop();
}
int ans = que.front();
que.pop();
return ans;
}
int top() {
return que.back();
}
bool empty() {
return que.empty();
}
};Solution 1: #Stack
class Solution {
public:
bool isValid(string s) {
if(s.size() % 2 != 0) return false; // the length of s should be even
stack<char> st;
for(auto c : s){
if(c == '(') st.push(')');
else if(c == '[') st.push(']');
else if(c == '{') st.push('}');
else if(st.empty() || st.top() != c) return false;
else st.pop(); // case where c == st.top()
}
return st.empty();
}
};Solution 2: #Hash Table
class Solution {
public:
bool isValid(string s) {
stack<char> st;
unordered_map<char, char> mp = {{'(', ')'}, {'{', '}'}, {'[', ']'}}; // 建立一个映射
for(char c : s){
if(mp.find(c) != mp.end()){
st.push(c);
}
else if(!st.empty() && mp[st.top()] == c){
st.pop();
}
else return false;
}
return st.empty();
}
};1047. Remove All Adjacent Duplicates In String
Solution1: #Stack
class Solution {
public:
string removeDuplicates(string s) {
stack<char> st;
for(auto c : s){
if(st.empty() || st.top() != c) st.push(c);
else st.pop();
}
string ans = "";
while(!st.empty()){
ans += st.top();
st.pop();
}
reverse(ans.begin(), ans.end());
return ans;
}
};Solution2: #Simulation，直接用string类型模拟
class Solution {
public:
string removeDuplicates(string s) {
string result = "";
for(auto c : s){
if(result.empty() || result.back() != c) result.push_back(c);
else result.pop_back();
}
return result;
}
};150. Evaluate Reverse Polish Notation
Solution1: #Stack，用栈来模拟
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> st;
for(string c : tokens){
if(c == "+"|| c == "-" || c == "*" || c == "/"){
int nums2 = st.top(); st.pop();
int nums1 = st.top(); st.pop();
if (c == "+") st.push(nums1 + nums2);
else if (c == "-") st.push(nums1 - nums2);
else if (c == "*") st.push(nums1 * nums2);
else if (c == "/") st.push(nums1 / nums2);
}
else st.push(stoi(c));
}
return st.top();
}
};Solution1: 维护一个单调递减的双端队列
class Solution {
private:
// 保持单调队列里单调递减
class MyQueue{
public:
deque<int> dq;
// 每次弹出的时候，比较当前要弹出的数值是否等于队列出口元素的数值，如果相等则弹出。
void pop(int value){
if(!dq.empty() && value == dq.front()) dq.pop_front();
}
void push(int value){
while(!dq.empty() && value > dq.back()) dq.pop_back();
dq.push_back(value);
}
int front(){
return dq.front();
}
};
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
MyQueue dq;
vector<int> result;
for(int i = 0; i < k; i++) dq.push(nums[i]);
result.push_back(dq.front());
for(int i = k; i < nums.size(); i++){
dq.pop(nums[i - k]); // 滑动窗口移除最前面的元素
dq.push(nums[i]); // 加入当前的元素
result.push_back(dq.front());
}
return result;
}
};Solution2: #multiset
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> result;
multiset<int> ms;
for(int i = 0; i < nums.size(); i++){
//注意只删除一个元素，所以要嵌套一个.find
if(i > k - 1) ms.erase(ms.find(nums[i - k]));
ms.insert(nums[i]);
if(i >= k - 1) result.push_back(*ms.rbegin()); // 压入反向迭代器指向的元素
}
return result;
}
};Solution3: #deque，维护一个单调递减的队列
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> result;
deque<int> que;
for(int i = 0; i < nums.size(); i++){
// 检查前端元素是否过期
while(!que.empty() && que.front() <= i - k) que.pop_front();
// 维护一个队列的单调递减性质
while(!que.empty() && nums[que.back()] <= nums[i]) que.pop_back();
que.push_back(i);
// 一旦处理的元素足够构成一个窗口，将队列最大值添加到结果里
if(i >= k - 1) result.push_back(nums[que.front()]);
}
return result;
}
};Solution1: 直观的方法，想办法对频率进行排序
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
// 使用 unordered_map 来记录元素频率
unordered_map<int, int> frequency;
for (int num : nums) {
frequency[num]++;
}
// 将 map 中的元素复制到 vector 中以便排序
vector<pair<int, int>> elements(frequency.begin(), frequency.end());
// 定义比较函数，排序逻辑根据频率降序排序
auto cmp = [](const pair<int, int>& a, const pair<int, int>& b) {
return a.second > b.second || (a.second == b.second && a.first > b.first);
};
// 排序元素
sort(elements.begin(), elements.end(), cmp);
// 收集前 k 个频率最高的元素
vector<int> result;
for (int i = 0; i < k; i++) {
result.push_back(elements[i].first);
}
return result;
}
};Solution2: #priority_queue
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
priority_queue<pair<int, int>> pq;
unordered_map<int, int> mp;
for(auto num : nums) mp[num]++;
for(auto it : mp){
pq.push({it.second, it.first});
}
vector<int> ans;
while(k-- && !pq.empty()){
ans.push_back(pq.top().second);
pq.pop();
}
return ans;
}
};