代码随想录leetcode200题之栈与队列

1 介绍

本博客用来记录代码随想录leetcode200题中栈与队列部分的题目。

2 训练

题目1：232. 用栈实现队列

C++代码如下，

#include <stack>class MyQueue {
private:stack<int> a;stack<int> b; //辅助栈
public:MyQueue() {a = stack<int>();b = stack<int>();}void push(int x) {//先把a中的内容转移到bwhile (!a.empty()) {b.push(a.top());a.pop();}//再将x推入a中a.push(x);//最后将b中的内容转移回awhile (!b.empty()) {a.push(b.top());b.pop();}return;}int pop() {int t = a.top();a.pop();return t;}int peek() {return a.top();}bool empty() {return a.empty();}
};/*** Your MyQueue object will be instantiated and called as such:* MyQueue* obj = new MyQueue();* obj->push(x);* int param_2 = obj->pop();* int param_3 = obj->peek();* bool param_4 = obj->empty();*/

python3代码如下，

class MyQueue:def __init__(self):self.a = []self.b = [] def push(self, x: int) -> None:#将a中内容转移到bwhile len(self.a) > 0:self.b.append(self.a[-1])self.a.pop()#将x推入到a中self.a.append(x)#将b中内容转移回awhile len(self.b) > 0:self.a.append(self.b[-1])self.b.pop()def pop(self) -> int:return self.a.pop()def peek(self) -> int:return self.a[-1]def empty(self) -> bool:return len(self.a) == 0# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()

题目2：225. 用队列实现栈

C++代码如下，

class MyStack {
private:queue<int> a;queue<int> b; //辅助队列 public:MyStack() {a = queue<int>();b = queue<int>();}void push(int x) {//将a中内容转移到bwhile (!a.empty()) {b.push(a.front());a.pop();}//将x推入a中a.push(x);//将b中内容转移回awhile (!b.empty()) {a.push(b.front());b.pop();}return;}int pop() {int t = a.front();a.pop();return t;}int top() {return a.front();}bool empty() {return a.empty();}
};/*** Your MyStack object will be instantiated and called as such:* MyStack* obj = new MyStack();* obj->push(x);* int param_2 = obj->pop();* int param_3 = obj->top();* bool param_4 = obj->empty();*/

python3代码如下，

import queueclass MyStack:def __init__(self):self.a = queue.Queue()self.b = queue.Queue() #辅助队列def push(self, x: int) -> None:#将a中的内容转移到bwhile not self.a.empty():self.b.put(self.a.get())#往a中推入xself.a.put(x)#将b中的内容转移回awhile not self.b.empty():self.a.put(self.b.get())returndef pop(self) -> int:return self.a.get()def top(self) -> int:t = self.a.get()self.push(t)return tdef empty(self) -> bool:return self.a.empty()# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()

题目3：20. 有效的括号

C++代码如下，

class Solution {
public:bool isValid(string s) {stack<char> stk;for (auto c : s) {if (c == '(' || c == '[' || c == '{') {stk.push(c);} else {if (!stk.empty()) {char t = stk.top();stk.pop();if ((t == '(' && c == ')') || (t == '[' && c == ']') || (t == '{' && c == '}')) {//} else {return false;}} else {return false;}}}return stk.empty();}
};

python3代码如下，

class Solution:def isValid(self, s: str) -> bool:stk = []for c in s:if c in "([{":stk.append(c)else:if len(stk) == 0:return Falseelse:t = stk.pop()if (t == '(' and c == ')') or \(t == '[' and c == ']') or \(t == '{' and c == '}'):passelse:return Falsereturn len(stk) == 0

题目4：1047. 删除字符串中的所有相邻重复项

C++代码如下，

class Solution {
public:string removeDuplicates(string s) {stack<char> stk;for (auto c : s) {if (stk.empty() || stk.top() != c) {stk.push(c);} else {stk.pop();}}string t;while (!stk.empty()) {t += stk.top();stk.pop();}reverse(t.begin(), t.end());return t;}
};

python3代码如下，

class Solution:def removeDuplicates(self, s: str) -> str:stk = []for c in s:if len(stk) == 0 or stk[-1] != c:stk.append(c)else:stk.pop()res = "".join(stk)return res

题目5：150. 逆波兰表达式求值

C++代码如下，

class Solution {
public:int evalRPN(vector<string>& tokens) {stack<int> stk;string operations = "+-*/";for (auto token : tokens) {if (operations.find(token) == string::npos) {stk.push(stoi(token));} else {int b = stk.top();stk.pop();int a = stk.top();stk.pop();         if (token == "+") stk.push(a+b);else if (token == "-") stk.push(a-b);else if (token == "*") stk.push(a*b);else stk.push(a/b);}}return stk.top();}
};

python3代码如下，

class Solution:def evalRPN(self, tokens: List[str]) -> int:stk = []for token in tokens:if token not in ["+", "-", "*", "/"]:stk.append(int(token))else:b = stk[-1]stk.pop()a = stk[-1]stk.pop()if token == "+":stk.append(a+b)elif token == "-":stk.append(a-b)elif token == "*":stk.append(int(a*b))else:stk.append(int(a/b)) #注意a//b与int(a/b)的区别return stk[-1]

题目6：239. 滑动窗口最大值

C++代码如下，

class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {vector<int> res;deque<int> q;for (int i = 0; i < nums.size(); ++i) {if (!q.empty() && q.front() < i - k + 1) q.pop_front();while (!q.empty() && nums[q.back()] <= nums[i]) q.pop_back();q.push_back(i);if (i >= k - 1) res.emplace_back(nums[q.front()]);}return res;}
};

python3代码如下，

from collections import dequeclass Solution:def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:res = []q = deque()for i in range(len(nums)):if len(q) != 0 and q[0] < i - k + 1:q.popleft()while len(q) != 0 and nums[q[-1]] <= nums[i]:q.pop()q.append(i)if i >= k - 1:res.append(nums[q[0]])return res

题目7：347. 前 K 个高频元素

C++代码如下，

typedef pair<int,int> PII;class Solution {
public:vector<int> topKFrequent(vector<int>& nums, int k) {unordered_map<int,int> cnt;for (auto x : nums) cnt[x]++;vector<PII> a;for (auto [k, v] : cnt) a.emplace_back(v, k);sort(a.begin(), a.end());reverse(a.begin(), a.end());vector<int> res;for (int i = 0; i < k; ++i) res.emplace_back(a[i].second);return res;}
};

python3代码如下，

from collections import Counterclass Solution:def topKFrequent(self, nums: List[int], k: int) -> List[int]:cnt = Counter(nums)a = cnt.most_common(k)res = [x[0] for x in a]return res

3 参考

代码随想录官网