后端秋招上岸字节刷题第一天(堆栈)多种语言实现
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档
文章目录
- 1.用两个栈实现队列
-
- 题目描述:
- 思路分析:
- 代码实现:
-
-
- java版本
- python3版本
-
- 2.包含min的栈
-
- 题目描述:
- 思路分析:
- 代码实现:
-
-
- Java版本
-
- 加入学习交流
前言:努力刷题,上岸上岸
1.用两个栈实现队列
题目描述:
思路分析:
使用两个栈,分别为添加A栈和删除R栈
💪删除元素时
- 先判断R栈中是否有元素:
- 如果没有元素则将A栈中的元素,依次添加到R栈中,完成一次元素的反转。将R栈的栈顶元素删除即可,
- 如果有元素则直接将R栈的栈顶元素删除即可,
- 若A栈和R栈都为空,返回-1;
以上为题目的思路:
代码实现:
java版本
class CQueue { LinkedList<Integer> stacka,stackd; public CQueue() { stacka = new LinkedList<Integer>(); stackd = new LinkedList<Integer>(); } public void appendTail(int value) { stacka.addLast(value); } public int deleteHead() { if(!stackd.isEmpty()) return stackd.removeLast(); if(stackd.isEmpty()&stacka.isEmpty()) return -1; while(!stacka.isEmpty()){ stackd.addLast(stacka.removeLast()); } return stackd.removeLast(); }}/** * Your CQueue object will be instantiated and called as such: * CQueue obj = new CQueue(); * obj.appendTail(value); * int param_2 = obj.deleteHead(); */
python3版本
class CQueue: def __init__(self): self.A, self.B = [], [] def appendTail(self, value: int) -> None: self.A.append(value) def deleteHead(self) -> int: if self.B: return self.B.pop() if not self.A: return -1 while self.A: self.B.append(self.A.pop()) return self.B.pop()
2.包含min的栈
题目描述:
思路分析:
首先创建两个栈
添加元素:
- 首先A栈中不用判断,直接插入
- B栈在插入时,先判断插入的元素与B栈栈顶的元素哪个值比较小
- 若插入的值小,则插入到B栈中
删除元素:
- A栈直接删除元素即可
- 若A栈删除的元素和B栈的栈顶的元素一样,则B栈也要删除
top():
直接查看A栈栈顶元素即可
min():
直接查看B栈栈顶元素即可
代码实现:
Java版本
//使用stack实现class MinStack { Stack<Integer> A, B; public MinStack() { A = new Stack<>(); B = new Stack<>(); } public void push(int x) { A.add(x); if(B.empty() || B.peek() >= x) B.add(x); } public void pop() { if(A.pop().equals(B.peek())) B.pop(); } public int top() { return A.peek(); } public int min() { return B.peek(); }}//使用LinkedList实现class MinStack { LinkedList<Integer> Astack,Bstack; /** initialize your data structure here. */ public MinStack() { Astack = new LinkedList<>(); Bstack = new LinkedList<>(); } public void push(int x) { Astack.addLast(x); if(Bstack.isEmpty()||Bstack.getLast()>=x)Bstack.addLast(x); } public void pop() { int val = Astack.removeLast(); if(val==Bstack.peekLast()) Bstack.removeLast(); } public int top() { return Astack.peekLast(); } public int min() { return Bstack.peekLast(); }}/** * Your MinStack object will be instantiated and called as such: * MinStack obj = new MinStack(); * obj.push(x); * obj.pop(); * int param_3 = obj.top(); * int param_4 = obj.min(); */