河南省旅游网站建设,杭州低价做网站,樟木头镇做网站,网站没制作好可以备案吗数据结构——栈与队列相关题目232. 用栈实现队列思路225. 用队列实现栈1.两个队列实现栈2.一个队列实现栈20. 有效的括号思路1047. 删除字符串中的所有相邻重复项思路155. 最小栈150. 逆波兰表达式求值思路239. 滑动窗口最大值单调队列347. 前 K 个高频元素思路232. 用栈实现队…
数据结构——栈与队列相关题目232. 用栈实现队列思路225. 用队列实现栈1.两个队列实现栈2.一个队列实现栈20. 有效的括号思路1047. 删除字符串中的所有相邻重复项思路155. 最小栈150. 逆波兰表达式求值思路239. 滑动窗口最大值单调队列347. 前 K 个高频元素思路232. 用栈实现队列
232. 用栈实现队列
使用栈实现队列的下列操作
push(x) – 将一个元素放入队列的尾部。pop() – 从队列首部移除元素。peek() – 返回队列首部的元素。empty() – 返回队列是否为空。
说明: 你只能使用标准的栈操作 – 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。 你所使用的语言也许不支持栈。你可以使用 list 或者 deque双端队列来模拟一个栈只要是标准的栈操作即可。 假设所有操作都是有效的 例如一个空的队列不会调用 pop 或者 peek 操作。
思路
需要两个栈一个输入栈一个输出栈这里要注意输入栈和输出栈的关系。
在push数据的时候只要数据放进输入栈就好但在pop的时候操作就复杂一些输出栈如果为空就把进栈数据全部导入进来注意是全部导入再从出栈弹出数据如果输出栈不为空则直接从出栈弹出数据就可以了。
最后如何判断队列为空呢如果进栈和出栈都为空的话说明模拟的队列为空了。
class MyQueue {StackInteger stackIn;StackInteger stackOut;public MyQueue() {stackIn new Stack();stackOut new Stack();}public void push(int x) {stackIn.push(x);}public int pop() {dumpstackIn();return stackOut.pop();}public int peek() {dumpstackIn();return stackOut.peek();}public boolean empty() {return stackIn.isEmpty() stackOut.isEmpty();}// 如果stackOut为空那么将stackIn中的元素全部放到stackOut中private void dumpstackIn(){if (!stackOut.isEmpty()) return; while (!stackIn.isEmpty()){stackOut.push(stackIn.pop());}}
}225. 用队列实现栈
225. 用队列实现栈
使用队列实现栈的下列操作
push(x) – 元素 x 入栈pop() – 移除栈顶元素top() – 获取栈顶元素empty() – 返回栈是否为空
注意:
你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。 你所使用的语言也许不支持队列。 你可以使用 list 或者 deque双端队列来模拟一个队列 , 只要是标准的队列操作即可。 你可以假设所有操作都是有效的例如, 对一个空的栈不会调用 pop 或者 top 操作。
1.两个队列实现栈
队列是先进先出的规则把一个队列中的数据导入另一个队列中数据的顺序并没有变并没有变成先进后出的顺序。
用两个队列que1和que2实现队列的功能que2其实完全就是一个备份的作用把que1最后面的元素以外的元素都备份到que2然后弹出最后面的元素再把其他元素从que2导回que1。 使用两个 Queue 实现
class MyStack {QueueInteger queue1; // 和栈中保持一样元素的队列QueueInteger queue2; // 辅助队列public MyStack() {queue1 new LinkedList();queue2 new LinkedList();}public void push(int x) {queue2.offer(x); // 先放在辅助队列中while (!queue1.isEmpty()){queue2.offer(queue1.poll());}QueueInteger queueTemp;queueTemp queue1;queue1 queue2;queue2 queueTemp; // 最后交换queue1和queue2将元素都放到queue1中}public int pop() {// 因为queue1中的元素和栈中的保持一致所以这个和下面两个的操作只看queue1return queue1.poll(); }public int top() {return queue1.peek();}public boolean empty() {return queue1.isEmpty();}
}使用两个 Deque 实现
class MyStack {// Deque 接口继承了 Queue 接口// 所以 Queue 中的 add、poll、peek等效于 Deque 中的 addLast、pollFirst、peekFirstDequeInteger que1;DequeInteger que2;public MyStack() {que1 new ArrayDeque();//双端队列que2 new ArrayDeque();}public void push(int x) {que1.addLast(x);}public int pop() {int size que1.size();size--;// 将que1导入que2 留下最后一个值while (size-- 0) {que2.addLast(que1.peekFirst());que1.pollFirst();}//删除que1中最后的元素并作为返回结果int res que1.pollFirst();// 将que2对象的引用赋给que1,此时que1que2指向同一个队列que1 que2;// 如果直接操作que2que1也会受到影响所以为que2分配一个新的空间que2 new ArrayDeque();return res; }public int top() {return que1.peekLast();}public boolean empty() {return que1.isEmpty();}
}2.一个队列实现栈
队列模拟栈其实一个队列就够了
一个队列在模拟栈弹出元素的时候只要将队列头部的元素除了最后一个元素外 重新添加到队列尾部此时在去弹出元素就是栈的顺序了。
class MyStack {// Deque 接口继承了 Queue 接口DequeInteger que1;public MyStack() {que1 new ArrayDeque();//双端队列}public void push(int x) {que1.addLast(x);}public int pop() {int size que1.size();size--;while (size-- 0) {//队列头部的元素除了最后一个元素外 重新添加到队列尾部que1.addLast(que1.peekFirst());que1.pollFirst();}int res que1.pollFirst();return res;}public int top() {return que1.peekLast();}public boolean empty() {return que1.isEmpty();}
}ArrayDeque双端队列可直接使用提供的API实现(没啥意义了)
class MyStack {// Deque 提供了实现堆栈的push,pop,peekDequeInteger que1;public MyStack() {que1 new ArrayDeque();//双端队列}public void push(int x) {que1.push(x);}public int pop() {return que1.pop(); }public int top() {return que1.peek();}public boolean empty() {return que1.isEmpty();}
}20. 有效的括号
20. 有效的括号
给定一个只包括 ‘(’‘)’‘{’‘}’‘[’‘]’ 的字符串判断字符串是否有效。 有效字符串需满足
左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。
示例 1:
输入: “()” 输出: true 示例 2:
输入: “()[]{}” 输出: true 示例 3:
输入: “(]” 输出: false
思路
括号匹配是使用栈解决的经典问题。 编译原理中编译器在词法分析的过程中处理括号、花括号等这个符号的逻辑也是使用了栈这种数据结构。
由于栈结构的特殊性非常适合做对称匹配类的题目。 首先要弄清楚字符串里的括号不匹配有几种情况。 第一种情况字符串里左方向的括号多余了 所以不匹配。 第二种情况括号没有多余但是 括号的类型没有匹配上。 第三种情况字符串里右方向的括号多余了所以不匹配。 代码随想录动画
字符串遍历完之后栈是空的就说明全都匹配了。
第一种情况已经遍历完了字符串但是栈不为空说明有相应的左括号没有右括号来匹配所以return false
第二种情况遍历字符串匹配的过程中发现栈里没有要匹配的字符。所以return false
第三种情况遍历字符串匹配的过程中栈已经为空了没有匹配的字符了说明右括号没有找到对应的左括号return false
技巧在匹配左括号的时候右括号先入栈就只需要比较当前元素和栈顶相不相等就可以了比左括号先入栈代码实现要简单的多了
时间复杂度O(n)O(n)O(n)其中 nn 是字符串 ss 的长度。 空间复杂度O(n∣Σ∣)O(n∣Σ∣)O(n∣Σ∣)其中Σ 表示字符集本题中字符串只包含 6 种括号∣Σ∣6。
class Solution {public boolean isValid(String s) {DequeCharacter deque new LinkedList();char ch;for (int i0;is.length();i) {ch s.charAt(i);//碰到左括号就把相应的右括号入栈if (ch() {deque.push());} else if (ch{) {deque.push(}); } else if (ch[) {deque.push(]);} else if (deque.isEmpty()||deque.peek()!ch) {//栈已经为空或匹配不对return false;} else {//如果是右括号判断是否和栈顶元素匹配//匹配则从栈中删除deque.pop();}}//最后判断栈中是否还有元素return deque.isEmpty();}
}1047. 删除字符串中的所有相邻重复项
1047. 删除字符串中的所有相邻重复项
给出由小写字母组成的字符串 S重复项删除操作会选择两个相邻且相同的字母并删除它们。
在 S 上反复执行重复项删除操作直到无法继续删除。 在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例
输入“abbaca” 输出“ca” 解释例如在 “abbaca” 中我们可以删除 “bb” 由于两字母相邻且相同这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 “aaca”其中又只有 “aa” 可以执行重复项删除操作所以最后的字符串为 “ca”。 提示
1 S.length 20000 S 仅由小写英文字母组成。
思路
本题要删除相邻相同元素其实也是匹配问题相同左元素相当于左括号相同右元素就是相当于右括号匹配上了就删除。 可以把字符串顺序放到一个栈中然后如果相同的话 栈就弹出这样最后栈里剩下的元素都是相邻不相同的元素了。
从栈中弹出剩余元素因为从栈里弹出的元素是倒序的所以在对字符串进行反转一下就得到了最终的结果。
用Deque作为堆栈
class Solution {public String removeDuplicates(String s) {//ArrayDeque会比LinkedList在除了删除元素这一点外会快一点//参考https://stackoverflow.com/questions/6163166/why-is-arraydeque-better-than-linkedlistArrayDequeCharacter deque new ArrayDeque();char ch;for (int i0;is.length();i) {ch s.charAt(i);if (deque.isEmpty()||deque.peek()!ch) {deque.push(ch);} else {deque.pop();}}String str ;while (!deque.isEmpty()) {//直接把删除的元素放在前面拼接//否则还需要反转字符串str deque.pop() str;}return str;}
}拿字符串直接作为栈省去了栈还要转为字符串的操作
class Solution {public String removeDuplicates(String s) {// 将 res 当做栈StringBuffer res new StringBuffer();// top为 res 的长度int top -1;for (int i 0; i s.length(); i) {char c s.charAt(i);// 当 top 0,即栈中有字符时当前字符如果和栈中字符相等弹出栈顶字符同时 top--if (top 0 res.charAt(top) c) {res.deleteCharAt(top);top--;// 否则将该字符入栈同时top} else {res.append(c);top;}}return res.toString();}
}拓展双指针
class Solution {public String removeDuplicates(String s) {char[] ch s.toCharArray();int fast 0;int slow 0;while (fast s.length()) {// 直接用fast指针覆盖slow指针的值ch[slow] ch[fast];// 遇到前后相同值的就跳过即slow指针后退一步下次循环就可以直接被覆盖掉了if(slow 0 ch[slow] ch[slow - 1]){slow--;}else{slow;}fast;}return new String(ch,0,slow);}
}155. 最小栈
155. 最小栈
150. 逆波兰表达式求值
150. 逆波兰表达式求值
根据 逆波兰表示法求表达式的值。
有效的运算符包括 , - , * , / 。每个运算对象可以是整数也可以是另一个逆波兰表达式。
说明
整数除法只保留整数部分。 给定逆波兰表达式总是有效的。换句话说表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1
输入: [“2”, “1”, “”, “3”, * ] 输出: 9 解释: 该算式转化为常见的中缀算术表达式为((2 1) * 3) 9 示例 2
输入: [“4”, “13”, “5”, “/”, “”] 输出: 6 解释: 该算式转化为常见的中缀算术表达式为(4 (13 / 5)) 6 示例 3
输入: [“10”, “6”, “9”, “3”, “”, “-11”, * , “/”, * , “17”, “”, “5”, “”]
输出: 22
解释:该算式转化为常见的中缀算术表达式为
((10 * (6 / ((9 3) * -11))) 17) 5 ((10 * (6 / (12 * -11))) 17) 5 ((10 * (6 / -132)) 17) 5 ((10 * 0) 17) 5 (0 17) 5 17 5 22 逆波兰表达式是一种后缀表达式所谓后缀就是指算符写在后面。
平常使用的算式则是一种中缀表达式如 ( 1 2 ) * ( 3 4 ) 。
该算式的逆波兰表达式写法为 ( ( 1 2 ) ( 3 4 ) * ) 。
逆波兰表达式主要有以下两个优点 去掉括号后表达式无歧义上式即便写成 1 2 3 4 * 也可以依据次序计算出正确结果。 适合用栈操作运算遇到数字则入栈遇到算符则取出栈顶两个数字进行计算并将结果压入栈中。
思路
本题中每一个子表达式要得出一个结果然后拿这个结果再进行运算那么这就是一个相邻元素做运算的过程出现运算符就要对之前的元素计算 class Solution {public int evalRPN(String[] tokens) {DequeInteger stack new LinkedList();for (int i0;itokens.length;i) {if (.equals(tokens[i])) {stack.push(stack.pop()stack.pop());} else if (-.equals(tokens[i])) {stack.push(-stack.pop()stack.pop());} else if (*.equals(tokens[i])) {stack.push(stack.pop()*stack.pop());} else if (/.equals(tokens[i])) {int temp1 stack.pop();int temp2 stack.pop();stack.push(temp2/temp1);} else {stack.push(Integer.valueOf(tokens[i]));}}return stack.pop();}
}239. 滑动窗口最大值
239. 滑动窗口最大值
给定一个数组 nums有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回滑动窗口中的最大值。
进阶 你能在线性时间复杂度内解决此题吗 提示
1 nums.length 10^5 -10^4 nums[i] 10^4 1 k nums.length
单调队列
我们需要一个队列这个队列呢放进去窗口里的元素然后随着窗口的移动队列也一进一出每次移动之后队列告诉我们里面的最大值是什么。队列里的元素一定是要排序的而且要最大值放在出队口。
但如果把窗口里的元素都放进队列里窗口移动的时候队列需要弹出元素。 实际上没有必要维护窗口里的所有元素只需要维护有可能成为窗口里最大值的元素就可以了同时保证队里里的元素数值是由大到小的。那么这个维护元素单调递减的队列就叫做单调队列即单调递减或单调递增的队列。
不要以为实现的单调队列就是 对窗口里面的数进行排序如果排序的话那和优先级队列又有什么区别了呢。
代码随想录动画 对于窗口里的元素{2, 3, 5, 1 ,4}单调队列里只维护{5, 4} 就够了保持单调队列里单调递减此时队列出口元素就是窗口里最大元素。
设计单调队列的时候pop和push操作要保持如下规则
pop(value)如果窗口移除的元素value等于单调队列的出口元素那么队列弹出元素否则不用任何操作push(value)如果push的元素value大于入口元素的数值那么就将队列入口的元素弹出直到push元素的数值小于等于队列入口元素的数值为止
保持如上规则每次窗口移动的时候只要问que.front()就可以返回当前窗口的最大值。 时间复杂度 O(n)O(n)O(n) 空间复杂度 O(k)O(k)O(k)
自定义单调队列
class Solution {public int[] maxSlidingWindow(int[] nums, int k) {if (nums.length 1) {return nums;}//结果数组的长度int len nums.length - k 1;int[] res new int[len];int num 0;MyQueue myQueue new MyQueue();for (int i0;ik;i) {myQueue.add(nums[i]);}res[num] myQueue.peek();for (int i k; i nums.length; i) {//滑动窗口移除最前面的元素移除时判断该元素是否放入队列myQueue.poll(nums[i - k]);//滑动窗口加入最后面的元素myQueue.add(nums[i]);//记录对应的最大值res[num] myQueue.peek();}return res;}
}
class MyQueue {DequeInteger deque new LinkedList();//弹出元素时比较当前要弹出的数值是否等于队列出口的数值如果相等则弹出//同时判断队列当前是否为空void poll(int val) {if (!deque.isEmpty() val deque.peek()) {deque.poll();}}//添加元素时如果要添加的元素大于入口处的元素就将入口元素弹出//保证队列元素单调递减//比如此时队列元素3,12将要入队比1大所以1弹出此时队列3,2void add(int val) {while (!deque.isEmpty() val deque.getLast()) {deque.removeLast();}deque.add(val);}//队列队顶元素始终为最大值int peek() {return deque.peek();}
}利用双端队列手动实现单调队列
/*** 用一个单调队列来存储对应的下标每当窗口滑动的时候直接取队列的头部指针对应的值放入结果集即可* 单调队列类似 tail -- 3 -- 2 -- 1 -- 0 (-- head) (右边为头结点元素存的是下标)*/
class Solution {public int[] maxSlidingWindow(int[] nums, int k) {ArrayDequeInteger deque new ArrayDeque();int res[] new int[nums.length-k1];int idx 0;for (int i0;inums.length;i) {// 根据题意i为nums下标是要在[i - k 1, i] 中选到最大值只需要保证两点// 1.队列头结点需要在[i - k 1, i]范围内不符合则要弹出while(!deque.isEmpty() deque.peek() i - k 1){deque.poll();}// 2.单调就要保证每次放进去的数字要比末尾的都大否则也弹出while(!deque.isEmpty() nums[deque.peekLast()] nums[i]) {deque.pollLast();}deque.offer(i);// 因为单调当i增长到符合第一个k范围的时候每滑动一步都将队列头节点放入结果就行了if(i k - 1){res[idx] nums[deque.peek()];}}return res;}
}PS题解中单调队列里的pop和push接口仅适用于本题。单调队列不是一成不变的而是不同场景不同写法总之要保证队列里单调递减或递增的原则所以叫做单调队列。
347. 前 K 个高频元素
347. 前 K 个高频元素
给定一个非空的整数数组返回其中出现频率前 k 高的元素。
示例 1:
输入: nums [1,1,1,2,2,3], k 2 输出: [1,2] 示例 2:
输入: nums [1], k 1 输出: [1] 提示
你可以假设给定的 k 总是合理的且 1 ≤ k ≤ 数组中不相同的元素的个数。你的算法的时间复杂度必须优于 O(nlogn)O(n \log n)O(nlogn) , n 是数组的大小。题目数据保证答案唯一换句话说数组中前 k 个高频元素的集合是唯一的。你可以按任意顺序返回答案。
思路
这道题目主要涉及到如下三块内容
要统计元素出现频率对频率排序找出前K个高频元素
首先统计元素出现的频率这一类的问题可以使用map来进行统计。
然后是对频率进行排序这里我们可以使用一种容器适配器就是优先级队列。 为什么不用快排呢 使用快排要将map转换为数组的结构然后对整个数组进行排序效率较低。而这种场景下我们其实只需要维护k个有序的序列就可以了所以使用优先级队列是最优的。
如果定义一个大小为k的大顶堆在每次移动更新大顶堆的时候每次弹出都把最大的元素弹出去了那么怎么保留下来前K个高频元素呢。而且使用大顶堆就要把所有元素都进行排序那能不能只排序k个元素呢
所以我们要用小顶堆因为要统计最大前k个元素只有小顶堆每次将最小的元素弹出最后小顶堆里积累的才是前k个最大元素。
寻找前k个最大元素流程如代码随想录图所示图中的频率只有三个所以正好构成一个大小为3的小顶堆如果频率更多一些则用这个小顶堆进行扫描
class Solution {public int[] topKFrequent(int[] nums, int k) {int[] result new int[k];HashMapInteger, Integer map new HashMap();for (int num : nums) {map.put(num, map.getOrDefault(num, 0) 1);}SetMap.EntryInteger, Integer entries map.entrySet();// 根据map的value值正序排相当于一个小顶堆// 使用lambda表达式PriorityQueueMap.EntryInteger, Integer queue new PriorityQueue((o1, o2) - o1.getValue() - o2.getValue()); for (Map.EntryInteger, Integer entry : entries) {queue.offer(entry);if (queue.size() k) {queue.poll();}}for (int i k - 1; i 0; i--) {result[i] queue.poll().getKey();}return result;}
}
