算法笔记|Day9栈与队列
- ☆☆☆☆☆leetcode 232.用栈实现队列
- ☆☆☆☆☆leetcode 225. 用队列实现栈
- ☆☆☆☆☆leetcode 20. 有效的括号
- ☆☆☆☆☆leetcode 1047. 删除字符串中的所有相邻重复项
☆☆☆☆☆leetcode 232.用栈实现队列
题目链接:leetcode 232.用栈实现队列
题目分析
1.需要输入栈和输出栈两个栈,push时只需放入输入栈,pop时需要考虑输出栈是否为空,若不为空直接弹出输出栈,若为空需将输入栈数据全部弹出导入到输出栈后再弹出输出栈,peek可以在pop基础上push弹出元素并返回,判断是否为empty只需判断输入栈和输出栈是否均为空;
2.push和empty的时间复杂度为O(1),pop和peek的时间复杂度为O(n),空间复杂度为O(n)。
代码
class MyQueue {
Stack<Integer> stackIn;
Stack<Integer> stackOut;
public MyQueue() {
stackIn=new Stack<>();
stackOut=new Stack<>();
}
public void push(int x) {
stackIn.push(x);
}
public int pop() {
if(stackOut.isEmpty()){
while(!stackIn.isEmpty()){
stackOut.push(stackIn.pop());
}
}
return stackOut.pop();
}
public int peek() {
int res=pop();
stackOut.push(res);
return res;
}
public boolean empty() {
return stackIn.isEmpty()&&stackOut.isEmpty();
}
}
/**
* 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();
* boolean param_4 = obj.empty();
*/
☆☆☆☆☆leetcode 225. 用队列实现栈
题目链接:leetcode 225. 用队列实现栈
题目分析
1.采用一个队列,push只需在队列添加,pop则需将队列除最后一个元素外的元素依次弹出并添加到队尾再弹出,top可以在pop基础上push并返回pop值,判断是否为empty只需判断队列是否为空;
2.push和empty的时间复杂度为O(1),pop和top的时间复杂度为O(n),空间复杂度为O(n)。
代码
class MyStack {
Queue<Integer> queue;
public MyStack() {
queue=new LinkedList<>();
}
public void push(int x) {
queue.add(x);
}
public int pop() {
int size=queue.size();
size--;
while(size>0){
queue.add(queue.poll());
size--;
}
return queue.poll();
}
public int top() {
int res=pop();
push(res);
return res;
}
public boolean empty() {
return queue.isEmpty();
}
}
/**
* 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();
* boolean param_4 = obj.empty();
*/
☆☆☆☆☆leetcode 20. 有效的括号
题目链接:leetcode 20. 有效的括号
题目分析
1.依次遍历各个元素,出现左括号时将对应的右括号入栈,直到出现右括号,需要判断是否与栈顶元素相同或者栈是否为空,依次考虑各种情况即可;
2.时间复杂度为O(n),空间复杂度为O(n)。
代码
class Solution {
public boolean isValid(String s) {
Deque<Character> deque=new LinkedList();
for(int i=0;i<s.length();i++){
if(s.charAt(i)=='(')
deque.push(')');
else if(s.charAt(i)=='[')
deque.push(']');
else if(s.charAt(i)=='{')
deque.push('}');
else if(deque.isEmpty()||s.charAt(i)!=deque.peek())
return false;
else
deque.pop();
}
return deque.isEmpty();
}
}
☆☆☆☆☆leetcode 1047. 删除字符串中的所有相邻重复项
题目链接:leetcode 1047. 删除字符串中的所有相邻重复项
题目分析
1.依次遍历各个元素,若与前一个元素相等则pop,若不等则继续push,最后将数组转为字符串;
2.本题还可以采用双指针法,fast指针遍历各个元素,slow指针指向删除后该元素对应的下标,若slow指针指向元素和上一个元素相等需要slow减一以覆盖该元素,否则slow加一继续遍历;
3.时间复杂度为O(n),空间复杂度为O(n)。
代码
1.使用栈
class Solution {
public String removeDuplicates(String s) {
Deque<Character> deque=new LinkedList<>();
for(int i=0;i<s.length();i++){
if(deque.isEmpty()||deque.peek()!=s.charAt(i))
deque.push(s.charAt(i));
else
deque.pop();
}
String str="";
while(!deque.isEmpty()){
str=deque.pop()+str;
}
return str;
}
}
2.双指针法
class Solution {
public String removeDuplicates(String s) {
char ch[]=s.toCharArray();
int slow=0,fast=0;
for(;fast<s.length();fast++){
ch[slow]=ch[fast];
if(slow>0&&ch[slow]==ch[slow-1]){
slow--;
}else{
slow++;
}
}
return new String(ch,0,slow);
}
}
标签:deque,slow,Day9,队列,pop,int,算法,push,public
From: https://blog.csdn.net/m0_57632621/article/details/140737979