LeetCode刷题之栈、队列
栈（Stack）
又名堆栈，它是一种重要的数据结构。从数据结构角度看，栈也是线性表，其特殊性在于栈的基本操作是线性表操作的子集，它是操作受限的线性表，因此，可称为限定性的数据结构。限定它仅在表尾进行插入或删除操作。表尾称为栈顶，相应地，表头称为栈底。栈的基本操作除了在栈顶进行插入和删除外，还有栈的初始化，判空以及取栈顶元素等。
队列（Queue）
是一种先进先出（FIFO，First-In-First-Out）的线性表。
在具体应用中通常用链表或者数组来实现。队列只允许在后端（称为 rear）进行插入操作，在前端（称为 front）进行删除操作。
队列的操作方式和堆栈类似，唯一的区别在于队列只允许新数据在后端进行添加。
Queue接口与List、Set同一级别，都是继承了Collection接口。LinkedList实现了Queue接 口。
队列常用的方法有：add、remove、element、offer、poll、peek、put、take，方法解释：
- add
增加一个元索 如果队列已满，则抛出一个IIIegaISlabEepeplian异常 - remove
移除并返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常 - element
返回队列头部的元素 如果队列为空，则抛出一NoSuchElementException异常 - offer 添加一个元素并返回true 如果队列已满，则返回false
- poll 移除并返问队列头部的元素 如果队列为空，则返回null
- peek 返回队列头部的元素 如果队列为空，则返回null
- put 添加一个元素 如果队列满，则阻塞
- take 移除并返回队列头部的元素
面试题 03.04. 化栈为队
实现一个MyQueue类，该类用两个栈来实现一个队列。
示例：
MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // 返回 1
queue.pop(); // 返回 1
queue.empty(); // 返回 false
题解：
/**
* 实现思路：
* 创建2个栈，栈1只负责入栈，栈2只负责出栈
* 存入几个元素到栈1后，如果此时栈2为空，则将栈1中的元素转移到栈2，从栈2出栈
* 如果此时栈2中不为空，则直接从栈2出栈
*/
class MyQueue {
Stack stack1; //stack1只负责入栈
Stack stack2; //stack2只负责出栈
/** Initialize your data structure here. */
public MyQueue() {
stack1 = new Stack<>();
stack2 = new Stack<>();
}
/** Push element x to the back of queue. */
public void push(int x) {
stack1.push(x);
}
/** Removes the element from in front of queue and returns that element. */
public int pop() {
if (!stack2.isEmpty()) {
return stack2.pop();
} else {
//将stack1中所有元素转移到stack2
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
return stack2.pop();
}
}
/** Get the front element. */
public int peek() {
if (!stack2.isEmpty()) {
return stack2.peek();
} else {
//将stack1中所有元素转移到stack2
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
return stack2.peek();
}
}
/** Returns whether the queue is empty. */
public boolean empty() {
if (stack1.isEmpty() && stack2.isEmpty()) {
return true;
} else {
return false;
}
}
}
1047. 删除字符串中的所有相邻重复项
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例：
输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。
题解：
/**
* 用栈的结构来维护没有重复项的字母序列:
* 循环从字符串中取出一个字符，与栈顶字符对比，如果不同，则放入栈；如果相同，则两个字符消掉，
* 即删除字符串中该字符，同时删除栈中该字符，最终栈中剩下来的字符数组为最终字符串
*
*/
class Solution {
public String removeDuplicates(String S) {
Stack stack = new Stack();
char[] chars = S.toCharArray();
for (char ch : chars) {
if (stack.isEmpty()) { //如果栈为空，则直接入栈
stack.push(ch);
} else { //如果栈不为空，则判断当前字符与栈顶字符是否相同，相同就从栈中弹出栈
if (ch != stack.peek()) {
stack.push(ch);
} else {
stack.pop();
}
}
}
StringBuilder stringBuilder = new StringBuilder();
for (Character ch : stack) {
stringBuilder.append(ch);
}
return stringBuilder.toString();
}
}
682. 棒球比赛
你现在是棒球比赛记录员。
给定一个字符串列表，每个字符串可以是以下四种类型之一：
1.整数（一轮的得分）：直接表示您在本轮中获得的积分数。
- "+"（一轮的得分）：表示本轮获得的得分是前两轮有效 回合得分的总和。
- "D"（一轮的得分）：表示本轮获得的得分是前一轮有效 回合得分的两倍。
- "C"（一个操作，这不是一个回合的分数）：表示您获得的最后一个有效 回合的分数是无效的，应该被移除。
每一轮的操作都是永久性的，可能会对前一轮和后一轮产生影响。
你需要返回你在所有回合中得分的总和。
示例 1:
输入: ["5","2","C","D","+"]
输出: 30
解释:
第1轮：你可以得到5分。总和是：5。
第2轮：你可以得到2分。总和是：7。
操作1：第2轮的数据无效。总和是：5。
第3轮：你可以得到10分（第2轮的数据已被删除）。总数是：15。
第4轮：你可以得到5 + 10 = 15分。总数是：30。
题解：
/**
* 思路：
* 用Stack来存储每一个轮的得分，最后累加得分。
* 根据每种字符规则，处理当前轮的得分
*/
class Solution {
public int calPoints(String[] ops) {
//stack为Integer类型，只存储每轮分数数值
Stack stack = new Stack();
for (String op : ops) {
if (op.equals("+")) {
int last = stack.pop(); //上一轮分数
int cur = stack.peek() + last; //当前轮分数
stack.push(last);
stack.push(cur);
} else if (op.equals("C")) {
//移除上一轮得分
stack.pop();
} else if (op.equals("D")) {
//当前分数为上一轮的2倍
int score = stack.peek()*2;
stack.push(score);
} else {
//当前为数字，直接加入
stack.push(Integer.valueOf(op));
}
}
int totalScore = 0;
for (Integer score : stack) {
totalScore += score;
}
return totalScore;
}
}
933. 最近的请求次数
写一个 RecentCounter 类来计算最近的请求。
它只有一个方法：ping(int t)，其中 t 代表以毫秒为单位的某个时间。
返回从 3000 毫秒前到现在的 ping 数。
任何处于 [t - 3000, t] 时间范围之内的 ping 都将会被计算在内，包括当前（指 t 时刻）的 ping。
保证每次对 ping 的调用都使用比之前更大的 t 值。
示例：
输入：inputs = ["RecentCounter","ping","ping","ping","ping"], inputs = [[],[1],[100],[3001],[3002]]
输出：[null,1,2,3,3]
题解：
class RecentCounter {
Queue queue;
public RecentCounter() {
queue = new LinkedList<>();
}
public int ping(int t) {
queue.add(t); //将当前时间入列
//遍历队列，判断当前元素是否是当前时间前3000的值，如果是，则从队列中移除
while (queue.peek() < t - 3000) {
queue.poll();
}
return queue.size();
}
}
剑指 Offer 59 - I. 滑动窗口的最大值
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
示例:
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
题解：
class Solution {
/**
* 思路：
* 从nums数组中取出前k个数，存入队列中
* 获取队列的最大值存储到集合中
* 然后队列移除头部，在尾部添加第k+1个数，获取队列中最大值存储到集合中
*
* @param nums
* @param k
* @return
*/
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums.length == 0) {
//如果数组为空，则返回空数组
return new int[0];
}
int[] result = new int[nums.length-k+1]; //总共需要输出的数组
Queue queue = new LinkedList<>();
//首次添加前k个数到队列中作为初始队列
for (int j=0;j maxNum) {
maxNum = num;
}
}
result[0] = maxNum;
for (int i=0;i max) {
max = num;
}
}
result[i+1] = max;
}
return result;
}
}
有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
题解：
class Solution {
public static boolean isValid(String s) {
//思路：1.在hashmap中存入左右括号对应分别作为键值对
//遍历字符，如果为左括号，就在栈中存入右括号，看后面的字符是否有该右括号来消掉
//3.用stack来存，先存就后取，后存就要先取
Stack stack = new Stack();
HashMap map = new HashMap();
map.put('(', ')');
map.put('[', ']');
map.put('{', '}');
for(Character ch : s.toCharArray()) {
if(map.containsKey(ch)) { //当前字符为左括号
stack.push(map.get(ch));
} else { //当前字符为右括号，那栈中最顶部必然要与之相同才行
if(stack.isEmpty() || stack.pop() != ch) {
return false;
}
}
}
//最后看stack还有没有没有正确关闭括号
return stack.isEmpty();
}
}
用队列实现栈
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
题解：
/**
* 用两个队列实现栈
* 这里需要实现一个队列元素的倒序，每次从queue2入列，从queue1中取出
*/
class MyStack {
Queue queue1;
Queue queue2;
/** Initialize your data structure here. */
public MyStack() {
queue1 = new LinkedList(); //入队列
queue2 = new LinkedList(); //出队列
}
/** Push element x onto stack. */
public void push(int x) {
queue2.offer(x);
while(!queue1.isEmpty()) { //将queue1中的元素移入queue2中，实现现有元素的倒序
queue2.offer(queue1.poll());
}
//交换数据，所以每次添加完数据都在queue1队列中
Queue temp = queue1;
queue1 = queue2;
queue2 = temp;
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
return queue1.poll();
}
/** Get the top element. */
public int top() {
return queue1.peek();
}
/** Returns whether the stack is empty. */
public boolean empty() {
return queue1.isEmpty();
}
}
用两个栈实现队列
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )
题解：
/**
* 实现思路：
* 创建2个栈，栈1只负责入栈，栈2只负责出栈
* 存入几个元素到栈1后，如果此时栈2为空，则将栈1中的元素转移到栈2，从栈2出栈
* 如果此时栈2中不为空，则直接从栈2出栈
*/
class CQueue {
Stack stack1; //stack1只负责入栈
Stack stack2; //stack2只负责出栈
public CQueue() {
stack1 = new Stack<>();
stack2 = new Stack<>();
}
/**
* 入列
* @param value
*/
public void appendTail(int value) {
stack1.push(value);
}
/**
* 出列并返回当前出列元素
* @return
*/
public int deleteHead() {
if (!stack2.isEmpty()) {
return stack2.pop();
} else {
//将stack1中所有元素转移到stack2
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
//若队列中没有元素，deleteHead 操作返回 -1
return stack2.isEmpty() ? -1 : stack2.pop();
}
}
}
最小栈
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。
题解：
/**
* 思路：用一个栈和一个最小栈来做，栈保存存入的数，最小栈的数目与存数栈一样，只是栈顶始终保存的是当前栈中最小的数
*/
class MinStack {
Stack stack;
Stack minStack;
public MinStack() {
stack = new Stack<>();
minStack = new Stack<>();
}
public void push(int val) {
stack.push(val);
if (minStack.isEmpty()) {
minStack.push(val);
} else {
minStack.push(Math.min(minStack.peek(), val));
}
}
public void pop() {
stack.pop();
minStack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}
去除重复字母
给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
题解：
class Solution {
/**
* 解题思路：
* 1.第一个条件：去重字母
* 2.第二个条件：保证字典序从小到大
* 3.第三个条件：保证字母存在至少一个
* @param s
* @return
*/
public String removeDuplicateLetters(String s) {
//第三个条件：保证字母存在至少一个
//做法：给每一种字母维护一个计数器，先遍历获取其数量，如果数量为1，则在第二个条件中不要弹出栈，否则可以弹出栈
int[] charCount = new int[256];
for (int i=0;i stk = new Stack<>();
boolean[] inStack = new boolean[256]; //用于存储这个字符是否已经记录过
// 第一个条件：去重字母
for(char c : s.toCharArray()) {
// 每遍历过一个字符，都将对应的计数减一
charCount[c]--;
if (inStack[c]) {
continue;
}
//第二个条件：保证字典序从小到大，在插入字母之前，判断与前一个字母的字典序，
// 如果比前一个小，则循环将字符弹出栈顶，清除在栈中的记录
while(!stk.empty() && stk.peek() > c) {
if (charCount[stk.peek()] == 0) {
break;
}
inStack[stk.pop()] = false;
}
stk.push(c);
inStack[c] = true;
}
StringBuilder sb = new StringBuilder();
while (!stk.empty()) {
sb.append(stk.pop());
}
return sb.reverse().toString();
}
}
剑指 Offer 59 - I. 滑动窗口的最大值
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
题解：
class Solution {
/**
* 思路：
* 从nums数组中取出前k个数，存入队列中
* 获取队列的最大值存储到集合中
* 然后队列移除头部，在尾部添加第k+1个数，获取队列中最大值存储到集合中
*
* @param nums
* @param k
* @return
*/
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums.length == 0) {
//如果数组为空，则返回空数组
return new int[0];
}
int[] result = new int[nums.length-k+1]; //总共需要输出的数组
Queue queue = new LinkedList<>();
//首次添加前k个数到队列中作为初始队列
for (int j=0;j maxNum) {
maxNum = num;
}
}
result[0] = maxNum;
for (int i=0;i max) {
max = num;
}
}
result[i+1] = max;
}
return result;
}
}
共有 0 条评论