栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

<Java>手把手带你刷leetcode(栈和队列篇)

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

<Java>手把手带你刷leetcode(栈和队列篇)


文章目录
  • 一、栈
    • 1.leetcode20.有效的括号
      • 1.1.题目描述
      • 1.2.思路分析
      • 1.3.代码实现
    • 2.leetcode155.最小栈
      • 2.1.题目描述
      • 2.2.思路分析
      • 2.3.代码实现
  • 二、队列
    • 1.leetcode225.用队列实现栈
      • 1.1.题目描述
      • 1.2.思路分析
      • 1.3.代码实现
    • 2.leetcode232.用栈实现队列
      • 2.1题目描述
      • 2.2.思路分析
      • 2.3.代码实现


一、栈 1.leetcode20.有效的括号 1.1.题目描述

1.2.思路分析

找反例
1.给定一个字符串,首先要把字符串转为字符数组一个个的判断
2.找到不满足闭合条件的反例即可
使用栈这个结构:
1.转为字符数组一个个的判断
2.碰到左括号就入栈
3.碰到右括号就把栈顶的左括号出栈,与右括号比较,查看是否匹配,若匹配则继续向下判断,若不匹配则找到反例,返回false;当整个字符串走完,且栈为空,则说明字符串是符合条件的

1.3.代码实现
public boolean isValid(String s) {
        Stack stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(' || c == '[' || c == '{'){
                stack.push(c);
            }else{
                if (stack.isEmpty()){
                    return false;
                }
                char top = stack.pop();
                //找反例
                if (c == ')' && top != '('){
                    return false;
                }
                if (c == ']' && top != '['){
                    return false;
                }
                if (c == '}' && top != '{'){
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
2.leetcode155.最小栈 2.1.题目描述

2.2.思路分析

题目需要我们在栈的基础上拓展一个getMin方法,可以立即取得当前栈的最小值,时间复杂度为O(1),
双栈思想:
我们可以使用两个栈,s1和s2,s1保存实际元素,s2永远保存最小元素

s1和s2同时入元素
整个操作的核心在于
当s2为空时,直接入栈
当s2栈顶的元素 > 当前元素,也是直接入栈
当s2栈顶的元素 < 当前元素,就把栈顶的元素在入一次栈(保证s2的元素个数和s1的元素个数保持一致);如果不一致,同步出栈后,s2为空了,s1还有元素,就无法判断了,元素个数相同,入栈和出栈操作都是同步的,那么s2的栈顶就永远保存了当前数据的最小元素。
那么此时的s2的栈顶元素一定是最小元素,只用调用s2.peek();即可

2.3.代码实现
class MinStack {

    public MinStack() {

    }
    
   //s1永远保存实际元素
    private Stack s1 = new Stack<>();
    //s2顶部永远保存最小元素
    private Stack s2 = new Stack<>();
    
    public void push(int val) {
        s1.push(val);
        if (s2.isEmpty()){
            s2.push(val);
        }else{
            int peek = s2.peek();
            s2.push(Math.min(val,peek));
        }
    }

    public void pop() {
        s1.pop();
        s2.pop();
    }

    public int top() {
        return s1.peek();
    }

    public int getMin() {
        return s2.peek();
    }
}


二、队列 1.leetcode225.用队列实现栈 1.1.题目描述

1.2.思路分析

上一题采用了双栈思想,一个栈保存实际元素,另一个栈作为辅助作用,本题也可以采用相同的思路,其中一个队列q1永远都是实际存储元素的队列,栈的pop就是q1的poll,栈的peek就是q1的peek,栈的push就是q1的offer,保证q1和栈的操作保持一致
另外一个队列q2作为辅助

一定记住,q1永远是储存元素的队列,栈和队列的出队顺序刚好是相反的,先让新元素入q2,然后让q1的所有元素出队再入q2,然后我们只需要将q1和q2的引用交换一下即可,那么q1还是储存元素的队列

1.3.代码实现
class MyStack {

    public MyStack() {

    }
    
 //queue永远是实际保存元素的队列
    private Queue queue1 = new LinkedList<>();
    //queue作为辅助
    private Queue queue2 = new LinkedList<>();
    public void push(int x) {
        //新元素直接入队2
         queue2.offer(x);
        //将旧元素依次出队1,入队2
        while(!queue1.isEmpty()){
            queue2.offer(queue1.poll());
        }
        //交换queue1和queue2
        Queue temp;
        temp = queue1;
        queue1 = queue2;
        queue2 = temp;
    }

    public int pop() {
        return queue1.poll();
    }

    public int top() {
        return queue1.peek();
    }

    public boolean empty() {
        return queue1.isEmpty();
    }
}


2.leetcode232.用栈实现队列 2.1题目描述

2.2.思路分析

同样的思路,双栈思路

s1永远是保存元素的栈
1.先将s1中的元素依次弹出放入s2中
2.将新元素放入s1中 – – > 此时这个元素就是s1的栈底(队尾元素)
3.再将s2中的元素依次弹回到s1(此时s1就是先进先出的队列)

2.3.代码实现
class MyQueue {

    public MyQueue() {

    }
    
   //s1永远保存实际元素
    private Stack s1 = new Stack<>();
    private Stack s2 = new Stack<>();
    public void push(int x) {
        while(!s1.isEmpty()){
            s2.push(s1.pop());
        }
        s1.push(x);
        while (!s2.isEmpty()){
            s1.push(s2.pop());
        }
    }

    public int pop() {
        return s1.pop();
    }

    public int peek() {
        return s1.peek();
    }

    public boolean empty() {
        return s1.isEmpty();
    }
}


转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/975207.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号