跟随carl代码随想录刷题
语言：python

---

20. 有效的括号

题目：给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
.
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
.
👉示例 1：
输入：s = “()”
输出：true
👉示例 2：
输入：s = “()[]{}”
输出：true
👉示例 3：
输入：s = “(]”
输出：false
👉示例 4：
输入：s = “([)]”
输出：false
👉示例 5：
输入：s = “{[]}”
输出：true

题目分析使用栈解决的经典问题

⭐️括号匹配是使用栈解决的经典问题

⭐️由于栈结构的特殊性，非常适合做对称匹配类的题目。

在写代码之前，要先想想有哪几种不匹配的情况。

1. 左括号多余
2. 括号没有多余，但是不匹配
3. 右括号多余

分为以下三种情况：

• 已经遍历完字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

用字典实现括号匹配

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

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)
1
2
3
4
5
6
7
8
9
10

如果不让用栈，那就用双指针

class Solution:
    def removeDuplicates(self, s: str) -> str:
        res = list(s)
        slow = fast = 0
        n = len(res)

        while fast<n:
            # 交换两个位置的元素
            res[slow] = res[fast]

            # 如果发现和前面一样，就回退一格
            if slow>0 and res[slow] == res[slow-1]:
                slow -= 1
            else:
                slow += 1
            fast += 1
        return ''.join(res[0:slow])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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中的最后一个数，以整数形式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

347. 中等前 K 个高频元素

题目：给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
👉示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
👉示例 2:
输入: nums = [1], k = 1
输出: [1]

题目分析优先级队列

1. 统计元素出现的频率map
2. 对频率进行排序优先级队列
3. 找到前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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31