网站系统关键字,直播开放平台,ui交互设计用什么软件,网络广告推广策划1. 用栈实现队列
232.用栈实现队列https://leetcode.cn/problems/implement-queue-using-stacks/description/
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作#xff08;push、pop、peek、empty#xff09;#xff1a;
实现 MyQueue 类#xf…1. 用栈实现队列
232.用栈实现队列https://leetcode.cn/problems/implement-queue-using-stacks/description/
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作push、pop、peek、empty
实现 MyQueue 类
void push(int x) 将元素 x 推到队列的末尾int pop() 从队列的开头移除并返回元素int peek() 返回队列开头的元素boolean empty() 如果队列为空返回 true 否则返回 fals
解题思路
队列是先进先出的栈是先进后出的要把栈底的元素拿到需要把栈进行逆序按照这个思路把出栈后放到一个新的栈内就行了。所以push就是放进入栈内pop和peek都是去出栈找如果出栈为空了就把入栈的元素压入出栈。
代码
class MyQueue {private StackInteger pushStack;private StackInteger popStack;private int size 0;public MyQueue() {pushStack new StackInteger();popStack new StackInteger();}public void push(int x) {pushStack.push(x);size;}public int pop() {if (popStack.isEmpty()) {transform();}size--;return popStack.pop();}public int peek() {if (popStack.isEmpty()) {transform();}return (int) popStack.peek();}public boolean empty() {return size 0;}private void transform() {int count size;while (count 0) {popStack.push(pushStack.pop());count--;}}
}
2. 用队列实现栈
225. 用队列实现栈https://leetcode.cn/problems/implement-stack-using-queues/description/
请你仅使用两个队列实现一个后入先出LIFO的栈并支持普通栈的全部四种操作push、top、pop 和 empty。
实现 MyStack 类
void push(int x) 将元素 x 压入栈顶。int pop() 移除并返回栈顶元素。int top() 返回栈顶元素。boolean empty() 如果栈是空的返回 true 否则返回 false 。
解题思路
先进先出的队列想要变成栈也就是说前面的要给最后一个让位置可以让前面的全部都重新排队重新进入队列。
代码
class MyStack {private QueueInteger queue;public MyStack() {queue new LinkedListInteger();}public void push(int x) {queue.add(x);}public int pop() {rePush();return queue.poll();}public int top() {rePush();int res queue.poll();queue.add(res);return res;}public boolean empty() {return queue.isEmpty();}private void rePush() {int count queue.size() - 1;while (count ! 0) {queue.add(queue.poll());count--;}}
}
3. 有效的括号
20. 有效的括号https://leetcode.cn/problems/valid-parentheses/description/
给定一个只包括 (){}[] 的字符串 s 判断字符串是否有效。
有效字符串需满足
左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。
示例 1
输入s ()
输出true
示例 2
输入s ()[]{}
输出true示例 3
输入s (]
输出false 解题思路
括号匹配是一个典型的栈操作后进的左括号一定先与后续的右括号进行匹配。所以可以使用一个栈进行字符的入栈当发现是左括号的时候就对放入对应的右括号当发现是右括号且栈不为空的时候就判断栈顶元素和当前右括号是不是一样不一样就false。如果一样就弹出栈顶元素。遍历完毕后如果栈内为空说明全都匹配成功了。
代码 public boolean isValid(String s) {DequeCharacter deque new LinkedList();char ch;for (int i 0; i s.length(); i) {ch s.charAt(i);if (ch () {deque.push());} else if (ch {) {deque.push(});} else if (ch [) {deque.push(]);} else if (deque.isEmpty() || deque.peek() ! ch) {return false;} else {deque.pop();}}return deque.isEmpty();}
4. 删除字符串中的所有相邻重复项
1047. 删除字符串中的所有相邻重复项https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/description/
给出由小写字母组成的字符串 S重复项删除操作会选择两个相邻且相同的字母并删除它们。
在 S 上反复执行重复项删除操作直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例
输入abbaca
输出ca
解释在 abbaca 中我们可以删除 bb 由于两字母相邻且相同。这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 aaca其中又只有 aa 可以执行重复项删除操作所以最后的字符串为 ca。
解题思路
执行重复删除也就是说长度为偶数的回文字符串会被删除可以考虑使用栈因为回文就是先进入的后判断。对一个字符进行判断如果和栈顶元素相等就弹出栈顶。最后栈内就是全部的字符串字符。
代码
class Solution {public String removeDuplicates(String s) {DequeCharacter stack new LinkedList();StringBuilder res new StringBuilder();for (int i 0; i s.length(); i) {if (!stack.isEmpty() stack.peek() s.charAt(i)) {stack.pop();} else {stack.push(s.charAt(i));}}while (!stack.isEmpty()) {res.append(stack.pollLast());}return String.valueOf(res);}
}
