- 20. 有效的括号
- 题目分析`使用栈解决的经典问题`
- 完整代码如下
- 用if判断实现括号匹配
- 用字典实现括号匹配
- 1047. `简单`删除字符串中的所有相邻重复项
- 题目分析`匹配问题都是栈的强项`
- 完整代码如下
- 使用`栈`
- 如果不让用`栈`，那就用`双指针`
- 150. `中等`逆波兰表达式求值
- 题目分析
- 完整代码如下
- 239. `困难`滑动窗口最大值
- 题目分析`单调队列的经典题目`
- 完整代码如下
- 347. `中等`前 K 个高频元素
- 题目分析`优先级队列`
- 完整代码如下
跟随carl代码随想录刷题
语言：python
20. 有效的括号
题目分析使用栈解决的经典问题题目：给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
.
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
.
示例 1：
输入：s = “()”
输出：true
示例 2：
输入：s = “()[]{}”
输出：true
示例 3：
输入：s = “(]”
输出：false
示例 4：
输入：s = “([)]”
输出：false
示例 5：
输入：s = “{[]}”
输出：true
⭐️括号匹配是使用栈解决的经典问题
⭐️由于栈结构的特殊性，非常适合做对称匹配类的题目。
在写代码之前，要先想想有哪几种不匹配的情况。
- 左括号多余
- 括号没有多余，但是不匹配
- 右括号多余
分为以下三种情况：
- 已经遍历完字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，return false
- 遍历字符串的过程中，发现栈里没有要匹配的字符，return false
- 遍历字符串的过程中，栈已经空了，没有匹配的字符了，说明右括号没有找到对应的左括号来匹配，return false
当字符串遍历完，且栈为空时，说明全部都匹配，return True
完整代码如下 用if判断实现括号匹配class Solution:
def isValid(self, s: str) -> bool:
stack = []
for i in s:
if i == '(':
stack.append(')')
elif i == '[':
stack.append(']')
elif i == '{':
stack.append('}')
elif not stack or i != stack[-1]: # 如果栈为空，说明右括号多余；如果不等于栈最后一个元素，说明左右括号不匹配
return False
else:
stack.pop() # 如果输入是`右括号`，且栈内有相应的匹配项，则pop
# 如果栈为空，返回True，否则返回False
return True if not stack else False
用字典实现括号匹配
class Solution:
def isValid(self, s: str) -> bool:
stack = []
mapping = {
'(': ')',
'[': ']',
'{': '}'
}
for i in s:
if i in mapping:
stack.append(mapping[i])
elif not stack or i != stack[-1]: # 如果栈为空，说明右括号多余；如果不等于栈最后一个元素，说明左右括号不匹配
return False
else:
stack.pop() # 如果输入是`右括号`，且栈内有相应的匹配项，则pop
# 如果栈为空，返回True，否则返回False
return True if not stack else False
1047. 简单删除字符串中的所有相邻重复项
题目分析匹配问题都是栈的强项题目：给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
如果栈不为空，且输入元素与栈顶元素相同，则将栈顶元素弹出
否则就将输入元素压入栈内
输出栈
class Solution:
def removeDuplicates(self, s: str) -> str:
stack = []
for i in s:
if stack and i == stack[-1]:
stack.pop()
else:
stack.append(i)
return ''.join(stack)
如果不让用栈，那就用双指针
class Solution:
def removeDuplicates(self, s: str) -> str:
res = list(s)
slow = fast = 0
n = len(res)
while fast0 and res[slow] == res[slow-1]:
slow -= 1
else:
slow += 1
fast += 1
return ''.join(res[0:slow])
150. 中等逆波兰表达式求值
题目分析题目：根据 逆波兰表示法，求表达式的值。
.
有效的算符包括 +、-、、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
.
注意 两个整数之间的除法只保留整数部分。
可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1：
输入：tokens = [“2”,“1”,“+”,“3”,"“]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
示例 2：
输入：tokens = [“4”,“13”,“5”,”/“,”+“]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
示例 3：
输入：tokens = [“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
与消消乐很像，相邻元素做运算
中缀表达式：4 + 13 / 5，对计算机不友好
后缀表达式：["4", "13", "5", "/", "+"] ，对计算机友好
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
"""
1. 保存两个栈顶元素：`first_num, second_num = stack.pop(), stack.pop()`
2. eval()可以将字符串当成有效的表达式来求值，并返回计算结果。
3. stack.append()中不要写反！是用{second_num}{i}{first_num}
"""
stack = []
for i in tokens:
if i not in ["+", "-", "*", "/"]:
stack.append(i)
else:
first_num, second_num = stack.pop(), stack.pop() # 这一步很妙！保存栈顶的两个元素
stack.append(
int(eval(f'{second_num}{i}{first_num}'))
) # 这一步两个数字的顺序不要写反
return int(stack.pop()) # 返回stack中的最后一个数，以整数形式
239. 困难滑动窗口最大值
题目：给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
题目分析单调队列的经典题目示例 1：
示例 2：
输入：nums = [1], k = 1
输出：[1]
随着窗口的移动，队列也一进一出，每次移动之后，队列告诉我们里面的最大值是什么。
队列里的元素要有序存储，最大值放在出队口，
单调队列：
- 需要自己构造。
- 本题中，单调队列的接口为pop、push
- 单调队列不是一成不变的，而是不同场景不同写法。要保证队列里单调递增或单调递减的原则
class MyQueue:
"""
构造单调队列
"""
def __init__(self):
self.queue = []
def pop(self, value):
"""
接到移除元素的请求后，要进行判断，如果符合移除条件，则进行移除。判断条件为：
当作为队首的元素没有大过新元素时，则移除（pop）它
"""
if self.queue and value == self.queue[0]:
self.queue.pop(0)
def push(self, value):
"""
接收到新元素的压入请求后，在压入之前要先判断队列里是否有需要移除的元素：
1. 如果后面压入的数字比前一个大，那么就要把前面的那个小数字弹出（pop）。
此时，原先作为队首的数字被弹出，因为它没有新元素大，而新元素晋升为队首
2. 如果后面压入的数字没有前一个大，那就把它放在队列中。
不管是以上哪种情况，最终，队列中的第一个元素始终是队列中的最大值
"""
while self.queue and value > self.queue[-1]:
self.queue.pop()
self.queue.append(value)
def front(self):
"""
返回队列中的第一个元素，即，返回队列中的最大值
"""
return self.queue[0]
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
que = MyQueue()
result = []
for i in range(k): # 将窗口内的数值压入队列
que.push(nums[i])
result.append(que.front())
for i in range(k, len(nums)):
que.pop(nums[i-k]) # 因为窗口滑动，所以左边移除一个元素
que.push(nums[i]) # 因为窗口滑动，所以右侧推入新元素
result.append(que.front())
return result
347. 中等前 K 个高频元素
题目分析优先级队列题目：给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
- 统计元素出现的频率map
- 对频率进行排序优先级队列
- 找到前k个高频的元素
优先级队列：披着队列外衣的堆。
- 只从队头取元素，从队尾添加元素。
- 优先级队列内部元素是自动依照元素的权值排列。
- 利用大顶堆（max-heap）完成对元素的排序
堆：
- 完全二叉树
- 大顶堆：树的节点值都不小于其左右孩子的值。
- 小顶堆：树的节点值都不大于其左右孩子的值。
- 可直接用优先级队列priority_queue实现大顶堆、小顶堆
- 大顶堆：从大到小排
- 小顶堆：从小到大排
本题中对元素进行排序应该使用小顶堆
- 因为：如果选择大顶堆，那么每次移动更新大顶堆的时候，都把最大的元素弹出去了，那如何保留前k个高频元素呢？
- 小顶堆每次都将最小的元素弹出，最后小顶堆里积累的才是前k个最大的元素
python中heapq堆的讲解
python字典中get()函数的用法总结
import heapq
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
"""
1. 统计元素出现的频率，建议记住，很通用
"""
map_ = {}
for i in range(len(nums)):
map_[nums[i]] = map_.get(nums[i], 0) + 1 # 0表示count初始值为0，count += 1
"""
2. 对频率进行排序
"""
pri_que = [] # 小顶堆
for key, freq in map_.items():
heapq.heappush(pri_que, (freq, key))
if len(pri_que) > k:
heapq.heappop(pri_que) # 删除最小值（即第一个元素）
"""
3. 找出前k个高频元素。因为小顶堆先弹出的是最小的，所以倒序来输出到数组
"""
result = [0] * k
for i in range(k-1, -1, -1):
result[i] = heapq.heappop(pri_que)[1]
# `[1]`的作用：只输出[[3,1],[2,2]]索引为1的部分，
# 即，只输出频率，不输出元素值
return result
