力扣刷题记录（五）栈与队列

ゝ一纸荒年。 2022-10-05 13:51 196阅读 0赞

1.工作上一定没人这么搞，但是考察对栈、队列理解程度的好题  
① 题号232.用栈实现队列  
使用栈实现队列的下列操作：  
push(x) – 将一个元素放入队列的尾部。 pop() – 从队列首部移除元素。 peek() – 返回队列首部的元素。 empty() – 返回队列是否为空。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70]  
解析：  
这是一道模拟题，不涉及到具体算法，考察的就是对栈和队列的掌握程度。  
使用栈来模式队列的行为，如果仅仅用一个栈，是一定不行的，所以需要两个栈一个输入栈，一个输出栈，这里要注意输入栈和输出栈的关系。  
在push数据的时候，只要数据放进输入栈就好，但在pop的时候，操作就复杂一些，输出栈如果为空，就把进栈数据全部导入进来（注意是全部导入），再从出栈弹出数据，如果输出栈不为空，则直接从出栈弹出数据就可以了。  
最后如何判断队列为空呢？如果进栈和出栈都为空的话，说明模拟的队列为空了。  
在代码实现的时候，会发现pop() 和 peek()两个函数功能类似，代码实现上也是类似的，可以思考一下如何把代码抽象一下。

答：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][20210609151219514.png]  
2. 用队列实现栈还是有点别扭。  
① 题号225. 用队列实现栈  
使用队列实现栈的下列操作：  
push(x) – 元素 x 入栈  
pop() – 移除栈顶元素  
top() – 获取栈顶元素  
empty() – 返回栈是否为空

注意:  
你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。  
你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。  
你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。

解析：  
其实这道题目就是用一个队里就够了。  
一个队列在模拟栈弹出元素的时候只要将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部，此时在去弹出元素就是栈的顺序了。

答：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 4]  
![在这里插入图片描述][20210609164712872.png]  
3. 数据结构与算法应用往往隐藏在我们看不到的地方  
① 题号20. 有效的括号  
给定一个只包括 ‘(’，’)’，’\{’，’\}’，’\[’，’\]’ 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。  
左括号必须以正确的顺序闭合。  
注意空字符串可被认为是有效字符串。  
示例 1: 输入: “()” 输出: true

示例 2: 输入: “()\[\]\{\}” 输出: true

示例 3: 输入: “(\]” 输出: false

示例 4: 输入: “(\[)\]” 输出: false

示例 5: 输入: “\{\[\]\}” 输出: true

解析：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 5]  
第一种情况：已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false

第二种情况：遍历字符串匹配的过程中，发现栈里没有要匹配的字符。所以return false

第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号return false

那么什么时候说明左括号和右括号全都匹配了呢，就是字符串遍历完之后，栈是空的，就说明全都匹配了。

分析完之后，代码其实就比较好写了，

但还有一些技巧，在匹配左括号的时候，右括号先入栈，就只需要比较当前元素和栈顶相不相等就可以了，比左括号先入栈代码实现要简单的多了！

答：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 6]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 7]  
![在这里插入图片描述][20210609192353144.png]  
4. 匹配问题都是栈的强项  
① 题号1047. 删除字符串中的所有相邻重复项  
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。  
在 S 上反复执行重复项删除操作，直到无法继续删除。  
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。  
示例： 输入：“abbaca” 输出：“ca” 解释： 例如，在 “abbaca” 中，我们可以删除 “bb” 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 “aaca”，其中又只有 “aa” 可以执行重复项删除操作，所以最后的字符串为 “ca”。  
提示： 1 <= S.length <= 20000 S 仅由小写英文字母组成。

解析：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 8]

答：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 9]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 10]  
![在这里插入图片描述][20210609194030965.png]  
5. 这不仅仅是一道好题，也展现出计算机的思考方式  
① 题号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 + \* 也可以依据次序计算出正确结果。

适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。

解析：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 11]  
答:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 12]  
![在这里插入图片描述][20210609201610989.png]  
![在这里插入图片描述][20210609201624709.png]

注：  
我们习惯看到的表达式都是中缀表达式，因为符合我们的习惯，但是中缀表达式对于计算机来说就不是很友好了。  
例如：4 + 13 / 5，这就是中缀表达式，计算机从左到右去扫描的话，扫到13，还要判断13后面是什么运算法，还要比较一下优先级，然后13还和后面的5做运算，做完运算之后，还要向前回退到 4 的位置，继续做加法，你说麻不麻烦！  
那么将中缀表达式，转化为后缀表达式之后：\[“4”, “13”, “5”, “/”, “+”\] ，就不一样了，计算机可以利用栈里顺序处理，不需要考虑优先级了。也不用回退了， 所以后缀表达式对计算机来说是非常友好的。  
可以说本题不仅仅是一道好题，也展现出计算机的思考方式。  
在1970年代和1980年代，惠普在其所有台式和手持式计算器中都使用了RPN（后缀表达式），直到2020年代仍在某些模型中使用了RPN。

6.要用啥数据结构呢？  
① 题号239. 滑动窗口最大值  
给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。  
返回滑动窗口中的最大值。  
例:

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 13]  
答：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 14]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 15]  
![在这里插入图片描述][20210609230529827.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70]: /images/20221005/48f319be181848ec8760a9f6f5e21f92.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 1]: /images/20221005/3d5bbbd546484e7c90fbaeedfb21f78c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 2]: /images/20221005/0ef0439410e14535a8952dcbd95f5ec5.png
[20210609151219514.png]: /images/20221005/2daf8d42f6fa4eda925ee79f6a489c87.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 3]: /images/20221005/f1e086b6eecd4a4688fa3e6ece6dfa82.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 4]: /images/20221005/055417d55621462188924b420441c724.png
[20210609164712872.png]: /images/20221005/1b903e0666f9490eb540a90fc6413610.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 5]: /images/20221005/f72c2b4f34db4e59aedc82c80bad5459.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 6]: /images/20221005/ab1e6a391d05447d807856a713b4b4aa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 7]: /images/20221005/a835f6c85ff14b5db0d8d5ff43b85280.png
[20210609192353144.png]: /images/20221005/8333dafa77f743f6a903e0e403e3e094.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 8]: /images/20221005/cc43cdfe9bc04777847fefd28387e1bd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 9]: /images/20221005/43631c5950e64b84a7ab8f7b0124f14d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 10]: /images/20221005/a4de2592a977438b9d8bc00c54a996e8.png
[20210609194030965.png]: /images/20221005/3868d28caa9a47ca922dc81f8e8af9ff.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 11]: /images/20221005/dd4c6460911f41a388a8826e444d89e4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 12]: /images/20221005/9c00418b0ee545ef8294c0429abdb887.png
[20210609201610989.png]: /images/20221005/e7f519274b0348a4b16abec62d77cc63.png
[20210609201624709.png]: /images/20221005/d1e39793db094fabb2a426e3c03012d1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 13]: /images/20221005/3c48b7a5c71844d1b08426adb6ddec3a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 14]: /images/20221005/98480430a2904957b8f77ba8a1f7acaf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 15]: /images/20221005/63de740c9de641fe84e4832481412c43.png
[20210609230529827.png]: /images/20221005/99000a1ce29840ce9e0bb4fec6aba661.png