首页 > 编程语言 >算法笔记|Day9栈与队列

算法笔记|Day9栈与队列

时间:2024-07-28 17:00:12浏览次数:19  
标签:deque slow Day9 队列 pop int 算法 push public

算法笔记|Day9栈与队列

☆☆☆☆☆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

相关文章

  • java的几种算法结构
    顺序结构1.java的最基本的结构就是顺序结构除非特别指明,否则就按照顺序一句一句执行2.顺序结构是最简单的算法结构3.语句与语句之间.框与框之间是按从上到下的顺序进行的,他是由若干个依次执行的处理步骤组成的,它是任何算法的离不开的一种基本算法结构选择结构if单选择结构......
  • 代码随想录算法训练营第25天 | 回溯问题完结
    2024年7月27日题46.全排列继续回溯。classSolution{List<List<Integer>>res;List<Integer>path;int[]used;int[]nums;publicList<List<Integer>>permute(int[]nums){//用一个used存//0表示还没有用,1表示用了......
  • 3次样条轨迹曲线算法推导(博途SCL完整源代码)
    理解3次样条插值之前,大家需要先理解3次多项式轨迹,3次多项式轨迹介绍请参考下面文章链接:3次多项式轨迹规划(PLCSCL代码)_plc按照时间轨迹规划-CSDN博客文章浏览阅读741次。机器人、运动控制等常用的轨迹规划有三次多项式、五次多项式、梯形速度规划,S型速度规划,今天我们主要介......
  • 代码随想录算法训练营第50天 | 单调栈01
    代码随想录算法训练营第天|739.每日温度https://leetcode.cn/problems/daily-temperatures/description/代码随想录https://programmercarl.com/0739.每日温度.html#其他语言版本496.下一个更大元素Ihttps://leetcode.cn/problems/next-greater-element-i/description/......
  • JUC并发编程:基于Condition实现一个阻塞队列
    Condition方法概述await():当前线程进入等待状态,直到被通知(siginal)或中断【和wait方法语义相同】。awaitUninterruptibly():当前线程进入等待状态,直到被通知,对中断不敏感。awaitNanos(longtimeout):当前线程进入等待状态直到被通知(siginal),中断或超时。awaitUnit......
  • 代码随想录算法训练营第49天 | 动态规划总结
    代码随想录算法训练营第天|647.回文子串https://leetcode.cn/problems/palindromic-substrings/description/代码随想录https://programmercarl.com/0647.回文子串.html#思路516.最长回文子序列https://leetcode.cn/problems/longest-palindromic-subsequence/代码随想录......
  • Java----CAS算法与AtomicInteger源码解读
    CAS介绍:为了确保对数据操作的原子性,在java.util.concurrent.atomic下定义许多关于各种基本类型数据的提供原子操作的类。这里我们以AtomicInteger为例子。AtomicInteger的本质:自旋锁+CAS算法CAS的全称是:CompareAndSwap(比较再交换);是现代CPU广泛支持的一种对内存中的......
  • 【算法】浅析遗传算法【附完整示例】
    遗传算法:模拟自然选择,优化问题求解1.引言在计算机科学和优化问题求解中,遗传算法是一种借鉴生物进化理论的启发式搜索算法。它模拟自然选择和遗传机制,通过迭代搜索最优解。本文将介绍遗传算法的原理、步骤及其在实际应用中的重要性,并通过代码示例和图示帮助大家更好地理解......
  • 好书推荐 -- 《精通推荐算法》
    新书发布,京东限时15天内5折优惠,半天即可送到。图书封底有读者微信群,作者也在群里,任何技术、offer选择和职业规划的问题,都可以咨询。《精通推荐算法》,限时半价,半日达https://u.jd.com/VbCJsCz1作者介绍、本书内容、Q&A、业内人士好评和图书实拍本书不仅适合推荐算法工程......
  • 最优化(11):信赖域算法、非线性最小问题二乘算法
    4.6信赖域算法——第一小节给出了信赖域算法的框架,第二小节讨论了信赖域子问题的求解方法(迭代法、截断共轭梯度法),第三小节主要介绍算法收敛性;4.7非线性最小二乘问题算法——第一小节给出了非线性最小二乘问题的一般形式,第二小节主要介绍高斯-牛顿算法,第三小节主要介绍Leve......