双非本科准备秋招(12.2)—— 力扣栈与队列

2024-02-01 08:12

本文主要是介绍双非本科准备秋招(12.2)—— 力扣栈与队列,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

复习一下栈和队列的基础知识,刷几道题上上手。

1、102. 二叉树的层序遍历

广度优先遍历嘛,每次拓展一个新结点,就把新结点加入队列,这样遍历完队列中的元素,顺序就是层序遍历。

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {LinkedBlockingQueue<TreeNode> q = new LinkedBlockingQueue<>();List<List<Integer>> list = new ArrayList<>();if(root == null) return list;q.offer(root);int cnt = 1;while(!q.isEmpty()){List<Integer> L = new ArrayList<>();int temp = 0;for(int i = 0; i < cnt; i++){TreeNode t = q.poll();L.add(t.val);if(t.left != null){q.offer(t.left);temp++;}if(t.right != null){q.offer(t.right);temp++;}}cnt = temp;list.add(L);}return list;}
}

2 、20. 有效的括号

有几种典型的适合用栈解决的问题,括号匹配就是。

class Solution {public boolean isValid(String s) {Stack<Character> stack = new Stack<>();for(int i = 0; i < s.length(); i++){char c = s.charAt(i);if(stack.isEmpty()){stack.push(c);continue;}if(stack.peek() == '(' && c == ')'){stack.pop();}else if(stack.peek() == '[' && c == ']'){stack.pop();}else if(stack.peek() == '{' && c == '}'){stack.pop();}else{stack.push(c);}}return stack.isEmpty();}
}

3、150. 逆波兰表达式求值

原来后缀表达式就叫逆波兰表达式啊,跟上个题也差不多,是数字就压栈,是操作符就取出来两个操作一下,然后把结果入栈,最后栈内肯定只有一个元素,这个元素就是答案。

学完了JVM之后,发现其实栈帧中的操作数栈就是使用的后缀表达式。

class Solution {public int evalRPN(String[] tokens) {Stack<Integer> s = new Stack<>();for(int i = 0; i < tokens.length; i++){if(tokens[i].equals("+")){int v1 = s.pop();int v2 = s.pop();s.push(v1 + v2);}else if(tokens[i].equals("-")){int v1 = s.pop();int v2 = s.pop();s.push(v2-v1);}else if(tokens[i].equals("*")){int v1 = s.pop();int v2 = s.pop();s.push(v1*v2);}else if(tokens[i].equals("/")){int v1 = s.pop();int v2 = s.pop();s.push(v2/v1);}else{s.push(Integer.valueOf(tokens[i]));}}return Integer.valueOf(s.pop());}
}

4、232. 用栈实现队列

队列是先进先出,栈是先进后出,那么来回倒腾这个栈就行了,画个图解释一下。

push操作都一样,pop的时候,把栈的元素移动到另一个栈内,这时候就是反转过的了,直接pop就行。

class MyQueue {Stack<Integer> s1 = null;Stack<Integer> s2 = null;public MyQueue() {s1 = new Stack<>();s2 = new Stack<>();}public void push(int x) {s2.push(x);}public int pop() {if(s1.isEmpty()){while(!s2.isEmpty()){s1.push(s2.pop());}}return s1.pop();}public int peek() {if(s1.isEmpty()){while(!s2.isEmpty()){s1.push(s2.pop());}}return s1.peek();}public boolean empty() {return s1.isEmpty()&&s2.isEmpty();}
}

5、225. 用队列实现栈

主要是push不同,每次push都把队列中的元素移动到另一个队列中,然后加入元素,然后再把另一个队列中的元素拿回来,这样这个队列就和栈一样了。

class MyStack {LinkedBlockingQueue<Integer> q1 = new LinkedBlockingQueue<>();LinkedBlockingQueue<Integer> q2 = new LinkedBlockingQueue<>();public MyStack() {}public void push(int x) {while(!q1.isEmpty()){q2.offer(q1.poll());}q1.offer(x);while(!q2.isEmpty()){q1.offer(q2.poll());}}public int pop() {return q1.poll();}public int top() {return q1.peek();}public boolean empty() {return q1.isEmpty();}
}

这篇关于双非本科准备秋招(12.2)—— 力扣栈与队列的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/666635

相关文章

C++ RabbitMq消息队列组件详解

《C++RabbitMq消息队列组件详解》:本文主要介绍C++RabbitMq消息队列组件的相关知识,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1. RabbitMq介绍2. 安装RabbitMQ3. 安装 RabbitMQ 的 C++客户端库4. A

golang实现延迟队列(delay queue)的两种实现

《golang实现延迟队列(delayqueue)的两种实现》本文主要介绍了golang实现延迟队列(delayqueue)的两种实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的... 目录1 延迟队列:邮件提醒、订单自动取消2 实现2.1 simplChina编程e简单版:go自带的time

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

Redis消息队列实现异步秒杀功能

《Redis消息队列实现异步秒杀功能》在高并发场景下,为了提高秒杀业务的性能,可将部分工作交给Redis处理,并通过异步方式执行,Redis提供了多种数据结构来实现消息队列,总结三种,本文详细介绍Re... 目录1 Redis消息队列1.1 List 结构1.2 Pub/Sub 模式1.3 Stream 结

SpringKafka错误处理(重试机制与死信队列)

《SpringKafka错误处理(重试机制与死信队列)》SpringKafka提供了全面的错误处理机制,通过灵活的重试策略和死信队列处理,下面就来介绍一下,具有一定的参考价值,感兴趣的可以了解一下... 目录引言一、Spring Kafka错误处理基础二、配置重试机制三、死信队列实现四、特定异常的处理策略五

Spring Boot整合消息队列RabbitMQ的实现示例

《SpringBoot整合消息队列RabbitMQ的实现示例》本文主要介绍了SpringBoot整合消息队列RabbitMQ的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的... 目录RabbitMQ 简介与安装1. RabbitMQ 简介2. RabbitMQ 安装Spring

如何通过Python实现一个消息队列

《如何通过Python实现一个消息队列》这篇文章主要为大家详细介绍了如何通过Python实现一个简单的消息队列,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录如何通过 python 实现消息队列如何把 http 请求放在队列中执行1. 使用 queue.Queue 和 reque

解读Redis秒杀优化方案(阻塞队列+基于Stream流的消息队列)

《解读Redis秒杀优化方案(阻塞队列+基于Stream流的消息队列)》该文章介绍了使用Redis的阻塞队列和Stream流的消息队列来优化秒杀系统的方案,通过将秒杀流程拆分为两条流水线,使用Redi... 目录Redis秒杀优化方案(阻塞队列+Stream流的消息队列)什么是消息队列?消费者组的工作方式每

Redis延迟队列的实现示例

《Redis延迟队列的实现示例》Redis延迟队列是一种使用Redis实现的消息队列,本文主要介绍了Redis延迟队列的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习... 目录一、什么是 Redis 延迟队列二、实现原理三、Java 代码示例四、注意事项五、使用 Redi

hdu1180(广搜+优先队列)

此题要求最少到达目标点T的最短时间,所以我选择了广度优先搜索,并且要用到优先队列。 另外此题注意点较多,比如说可以在某个点停留,我wa了好多两次,就是因为忽略了这一点,然后参考了大神的思想,然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<