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;
}

热门文章

暂无图片
编程学习 ·

Linux centos7 乱码设置中文字符集

1.locale 查看现在使用的字符集locale -a 查看有哪些字符集utf8的就可以显示中文yum -y install kde-l10n-Chinese 安装后选个uft8的 ,设置一下全局变量vi /etc/profileexport LANG=en_CA.utf8=号后面是字符集,这个大家随意最后让这个配置文件生效就可以了. /etc/profile 可能…
暂无图片
编程学习 ·

oracle创建索引语句

oracle : 单索引 create index 索引名称 on table(column)删除索引 drop index 索引名称复合索引 create index WBSINDEX ON project_info(wbs,is_delete)查询某张表中所有索引 select * from ALL_INDEXS where table_name = project_info查询某张表加了索引的列 select * from…
暂无图片
编程学习 ·

ubuntu:beyond compare 4 This license key has been revoked 解决办法

错误如图所示:解决办法:(1)先用find命令找到bcompare所在位置:sudo find /home/ -name *bcompare(2)进入 /home/whf/.config,删除/bcomapre文件夹注意一般.config为隐藏文件,通过 ctrl+h 可以显示:(3)cd /usr/lib/beyondcompare/ (4)sudo sed -i "s/keexjEP3…
暂无图片
编程学习 ·

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

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

c++ string操作

c++ string操作 #include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std;void test01() {///*string& operator=(const char* s)* string& operator=(const string &s)* string& operato…
暂无图片
编程学习 ·

自动驾驶论文解析(7)

本文解析论文: A Practical Trajectory Planning Framework for Autonomous Ground Vehicles Driving in Urban Environments 来自国防科大团队 文章依旧沿用了经典的横向的空间规划,和纵向的速度规划。在横向上,横向位置是关于纵向距离S的三阶多项式。纵向上速度是关于时间…
暂无图片
编程学习 ·

医疗知识图谱笔记(二)

1.re库import re # 从字符串中匹配是否有该模板 print(re.search(pattern = w{2}, string = www.runoob.com)) # 从字符串中替换掉该模板 print(re.sub(pattern = #.*$, repl = "", string = "2004-959-559 # 这是一个国外电话号码")) # 从字符串中找到所…
暂无图片
编程学习 ·

Explicit Model Predictive Control of a Magnetic Flexible Endoscope

对胶囊的动力学进行建模,能更好的对胶囊进行控制,在已知胶囊预定义轨迹的情况下,对胶囊进行预测控制和定位。 一个磁灵活内窥镜的显式模型预测控制 Explicit Model Predictive Control of a Magnetic Flexible Endoscope [1] Paper Link Authors: Scaglioni, Bruno, et al. …
暂无图片
编程学习 ·

力扣-算法练习(Python)

9.回文数判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。示例1: 输入: 121 输出: true 示例2: 输入: -121 输出: false 解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。 示例3: 输入: 10 输出: fal…
暂无图片
编程学习 ·

elementUI From表单踩坑之watch 变量监控

-当修改input框内的值(form.name)的时候,watch 监控from失败,watch中的from不相应,打印无效;<el-form ref="form" :model="form" label-width="80px"><el-form-item label="活动名称"><el-input v-model="f…
暂无图片
编程学习 ·

String类

String类的subString方法从指定位置截取到字符串结尾 substring (int beginIndex) :返回一个子字符串,从beginIndex开始截取字符串到字符串结尾。 eg:str1.subString(5)//从第6个位置开始截取截取指定范围的内容 substring (int beginIndex, int endIndex) :返回一个子字符…
暂无图片
编程学习 ·

Go 结构体使用注意事项和细节

结构体使用注意事项和细节结构体的所有字段在内存中是连续的//结构体 type Point struct {x inty int }//结构体 type Rect struct {leftUp, rightDown Point }func main() {r1 := Rect{Point{1,2}, Point{3,4}}//r1有四个int, 在内存中是连续分布//打印地址fmt.Printf("…
暂无图片
编程学习 ·

剑指Offer(4)--重建二叉树

文章目录题目思路代码 题目 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。 思路首先我们看上面的图片,首…
暂无图片
编程学习 ·

Ubuntu系统分区(待补充)

Ubuntu系统下一个分区工具是gparted。假设一共有60G空间,建议按照以下方式来分区: 分区之前,建议备份一下现有数据防止丢失: sudo su cd / tar -cvpzf /media/sda7/backup.tgz —exclude=/lost+found —exclude=/sys —exclude=/media /
暂无图片
编程学习 ·

Git 提示fatal: remote origin already exists 错误解决办法

今天使用git 添加远程github仓库的时候提示错误:fatal: remote origin already exists. 意思是origin已经存在,确实,之前我失败一次就放弃了。最后找到解决办法如下: 1、先删除远程 Git 仓库 $ git remote rm origin 2、再添加远程 Git 仓库 $ git remote add origin https…
暂无图片
编程学习 ·

微信测试公众号 接口配置信息

1:首先要先注册一个测试的公众号 1:这样就可以得到自己的appid 和 appsecret 2:接口配置信息 可以看到参数 (测试公众号只有url 和 token) 1:url 是开发者用来接收微信消息和事件 的接口URL。(必须以http://开头,目前支持80端口) 2: Token:可由开发者可以任意填写,用作…
暂无图片
编程学习 ·

从word中复制内容包含图片到百度ueditor编辑器中

1.4.2之后官方并没有做功能的改动,1.4.2在word复制这块没有bug,其他版本会出现手动无法转存的情况本文使用的后台是Java。前端为Jsp(前端都一样,后台如果语言不通得自己做 Base64编码解码)因为公司业务需要支持IE8 ,网上其实有很多富文本框,效果都很好。例如www.wangEdi…