Leetcode 题解 - 栈和队列

用栈实现队列

232. Implement Queue using Stacks (Easy)

栈的顺序为后进先出,而队列的顺序为先进先出。使用两个栈实现队列,一个元素需要经过两个栈才能出队列,在经过第一个栈时元素顺序被反转,经过第二个栈时再次被反转,此时就是先进先出顺序。

class MyQueue {

    private Stack<Integer> in = new Stack<>();
    private Stack<Integer> out = new Stack<>();

    public void push(int x) {
        in.push(x);
    }

    public int pop() {
        in2out();
        return out.pop();
    }

    public int peek() {
        in2out();
        return out.peek();
    }

    private void in2out() {
        if (out.isEmpty()) {
            while (!in.isEmpty()) {
                out.push(in.pop());
            }
        }
    }

    public boolean empty() {
        return in.isEmpty() && out.isEmpty();
    }
}

用队列实现栈

225. Implement Stack using Queues (Easy)

在将一个元素 x 插入队列时,为了维护原来的后进先出顺序,需要让 x 插入队列首部。而队列的默认插入顺序是队列尾部,因此在将 x 插入队列尾部之后,需要让除了 x 之外的所有元素出队列,再入队列。

class MyStack {

    private Queue<Integer> queue;

    public MyStack() {
        queue = new LinkedList<>();
    }

    public void push(int x) {
        queue.add(x);
        int cnt = queue.size();
        while (cnt-- > 1) {
            queue.add(queue.poll());
        }
    }

    public int pop() {
        return queue.remove();
    }

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

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

最小值栈

155. Min Stack (Easy)

class MinStack {

    private Stack<Integer> dataStack;
    private Stack<Integer> minStack;
    private int min;

    public MinStack() {
        dataStack = new Stack<>();
        minStack = new Stack<>();
        min = Integer.MAX_VALUE;
    }

    public void push(int x) {
        dataStack.add(x);
        min = Math.min(min, x);
        minStack.add(min);
    }

    public void pop() {
        dataStack.pop();
        minStack.pop();
        min = minStack.isEmpty() ? Integer.MAX_VALUE : minStack.peek();
    }

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

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

对于实现最小值队列问题,可以先将队列使用栈来实现,然后就将问题转换为最小值栈,这个问题出现在 编程之美:3.7。

用栈实现括号匹配

20. Valid Parentheses (Easy)

"()[]{}"

Output : true
public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '{' || c == '[') {
            stack.push(c);
        } else {
            if (stack.isEmpty()) {
                return false;
            }
            char cStack = stack.pop();
            boolean b1 = c == ')' && cStack != '(';
            boolean b2 = c == ']' && cStack != '[';
            boolean b3 = c == '}' && cStack != '{';
            if (b1 || b2 || b3) {
                return false;
            }
        }
    }
    return stack.isEmpty();
}

数组中元素与下一个比它大的元素之间的距离

739. Daily Temperatures (Medium)

Input: [73, 74, 75, 71, 69, 72, 76, 73]
Output: [1, 1, 4, 2, 1, 1, 0, 0]

在遍历数组时用栈把数组中的数存起来,如果当前遍历的数比栈顶元素来的大,说明栈顶元素的下一个比它大的数就是当前元素。

public int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] dist = new int[n];
    Stack<Integer> indexs = new Stack<>();
    for (int curIndex = 0; curIndex < n; curIndex++) {
        while (!indexs.isEmpty() && temperatures[curIndex] > temperatures[indexs.peek()]) {
            int preIndex = indexs.pop();
            dist[preIndex] = curIndex - preIndex;
        }
        indexs.add(curIndex);
    }
    return dist;
}

循环数组中比当前元素大的下一个元素

503. Next Greater Element II (Medium)

Input: [1,2,1]
Output: [2,-1,2]
Explanation: The first 1's next greater number is 2;
The number 2 can't find next greater number;
The second 1's next greater number needs to search circularly, which is also 2.

与 739. Daily Temperatures (Medium) 不同的是,数组是循环数组,并且最后要求的不是距离而是下一个元素。

public int[] nextGreaterElements(int[] nums) {
    int n = nums.length;
    int[] next = new int[n];
    Arrays.fill(next, -1);
    Stack<Integer> pre = new Stack<>();
    for (int i = 0; i < n * 2; i++) {
        int num = nums[i % n];
        while (!pre.isEmpty() && nums[pre.peek()] < num) {
            next[pre.pop()] = num;
        }
        if (i < n){
            pre.push(i);
        }
    }
    return next;
}

热门文章

暂无图片
编程学习 ·

C语言 介绍

一.C的历史 编程语言的发展过程: 第1代语言 机器语言↓ 第2代语言 汇编语言↓ 第3代语言 高级语言——结构化:C,Fortran,Basic,Pascal↓分界线:1980s面向对象(OO):Algo,Simula67,Ada,SmallTalkC++,Java,C#结构化语言的缺陷: 操作和数据是分离的C语言的起源: 1969…
暂无图片
编程学习 ·

UDP通信关于recvfrom问题

server端bind自己的IP后和client端通信,再recvfrom后,打印源地址和目的地址一致,那个大神帮忙解释一下,附上两端的代码
暂无图片
编程学习 ·

Android 模拟器联网

先配置好adb环境变量,打开模拟器,cmd中输入adb shell 查看是否adb配置完成,exit退出adb模式,adb root将模拟器root,然后adb shell,可以直接setprop net.eth0.dns1 192.168.1.1 后面为自己ip地址
暂无图片
编程学习 ·

02 | 该如何选择消息队列?

1.应用场景见: https://blog.csdn.net/william_n/article/details/1040254082.学习/操作2.1 阅读文档02 | 该如何选择消息队列?李玥 2020-01-1400:0013:59讲述:李玥 大小:12.81M你好,我是李玥。这节课我们来聊一下几个比较常见的开源的消息队列中间件。如果你正在做消息队…
暂无图片
编程学习 ·

Spring-@Order注解

一、@Order 注解@Order的作用是定义Spring容器加载Bean的顺序 @Retention(RetentionPolicy.RUNTIME) @Target({ElementType.TYPE, ElementType.METHOD, ElementType.FIELD}) @Documented public @interface Order {/*** 默认最低优先级*/int value() default Ordered.LOWEST_PR…
暂无图片
编程学习 ·

Python入门的学习心得

由于我是自学Python,非科班出生,所以只能分享一些关于我的学习心得,如果有不对地方欢迎指正。不过非科班出生虽然是一个痛点,但是在工作上,我其实不输给我其他同事,这点我倒是很有自信,而且我也统一一句话“目前互联网上的免费编程课程,足够让你成为一个合格的码农”。…
暂无图片
编程学习 ·

jkd从1.8升级后报sun.misc相关错误

Idea解决找不到sun.misc.BASE64Encoder及sun.misc.BASE64Decoder找不到包 报错原因: JDK从1.8升级到9.0.1后sun.misc.BASE64Decoder和sun.misc.BASE64Encoder不可用 原因分析: ​ 参看官网,发现JDK中的lib\tools.jar和JRE中的lib\rt.jar已从Java SE 9中删除。这些JAR中可用的…
暂无图片
编程学习 ·

在海外如何寻找蓝海市场

2010年左右,我国跨境进口零售电商企业开始逐渐出现,到2015年电商数量实现了爆发式的增长。当然,随后就开始进入红海时代,网易考拉海购、天猫国际、京东全球购、唯品国际、小红书、洋码头占领了大部分市场。 国内红海,那就出海。 红海、蓝海概念的提出,让更多的创业者积极…
暂无图片
编程学习 ·

mmdetection训练出现:IndexError: list index out of range 错误

mmdetection训练出现:IndexError: list index out of range 错误文章目录:1 问题分析1.1 尝试解决错误:第一次1.2 尝试解决错误:第二次2 我的问题解决方式我的环境:Ubuntu18.04 TorchVision: 0.6.0 OpenCV: 4.2.0 MMCV: 0.5.5 MMDetection: 2.0.0+d9c8f14 MMDetection Com…
暂无图片
编程学习 ·

quartus ii 使用modelsim altera进行仿真

第一种:先随便写一个程序,有输入,有时钟,有输出再点击processing-->start-->start test bench template writer然后就会在modlsim的文件中生成一个.vt的文件 然后打开这个文件接下来就是再initial和always里面添加信号保存,再点击首先看仿真软件是不是modelsin-altera,再…
暂无图片
编程学习 ·

Tensorflow实现卷积神经网络

Tensorflow实现卷积神经网络Tensorflow实现卷积神经网络卷积层池化层归一化层实现简单的卷积神经网络 Tensorflow实现卷积神经网络 卷积层 卷积核,步福,填充,多通道卷积,激活函数,卷积函数。 主要函数使用: 1.conv2d函数 tf.nn.conv2d(input, filter, strides, padding, …
暂无图片
编程学习 ·

评估指标:精确率,召回率,F1_score,ROC,AUC

分类算法评估标准详解 分类准确度并不能够评估所有的场景,展示的结果也比较片面,这时候就需要其他的评估方法来进行测量评估。 所以接下来介绍一些其他的评估标准,将从以下5个方面来介绍: 混淆矩阵 精准率和召回率 F1 Score ROC曲线 AUC 一、混淆矩阵(Confusion Matrix) …
暂无图片
编程学习 ·

人工智能常用数据预处理

人工智能常用数据预处理一级目录正态化、标准化、归一化、正则化区别和作用 一级目录 1.读数据 2.合并训练和测试 2.填充空白数据 4.改变非数字为数字 5.去除无关数据 6.降为(合并相关数据) 7.正态化数据(碗圆) 正态化、标准化、归一化、正则化区别和作用 1.正态化归一化是…
暂无图片
编程学习 ·

前端性能优化

浏览器渲染机制 Html解析成DOM树,Css解析成CSS树,将DOM树与CSSDOM规则树合并在一起生成Render树,遍历渲染树开始布局,计算每个节点的位置大小信息,将渲染树每个节点绘制到屏幕阻塞渲染当浏览器遇到一个script标记时,DOM构建将暂停,直至脚本完成执行,然后继续构建DOM。每…
暂无图片
编程学习 ·

OA、ERP、BPM 各自的功能和特点是什么?怎么配合使用?

​OA是Office Automation的简称,译为办公自动化,常用于企业内部事务管理。OA具有的几个功能:信息存储、数据管理、数据共享。因此,它的使用场景常分布在日常办公中,比如:公文管理、沟通工具、文档管理、项目管理、任务管理、会议管理、通讯录、工作便签、问卷调查、常用工…
暂无图片
编程学习 ·

Object类的方法

Object 类是类层次结构的根,在 Java 语言中,所有的类从根本上而言都继承自这个类。而且,Object 类是 Java 语言中唯一没有父类的类,而其他所有的类,包括标准容器类,例如数组,都继承了 Object 类。方法名 返回类型 方法描述clone() Object 创建并返回此对象的一个副本equ…
暂无图片
编程学习 ·

操作系统——内核模块的键盘监控

操作系统——内核模块的键盘监控 实验环境: VMware + Ubuntu32位 实验步骤: 1.键盘码与ASII码的对应关系。 在Linux操作系统中,键盘的输入是以键盘码的形式存在的,所以我们必然需要将其转化为可读的字符(串)形式。于是我们构造数组:一些不常用的或是不方便表示的输入就使用…