力扣刷题笔记

# 单调队列

# 239

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        ans = []
        q = deque()
        for i, x in enumerate(nums):
            # 入队，其中 q 中元素为 nums 索引
            # 需要保证 q 中元素对应的 nums 值单调递减
            while q and nums[q[-1]] <= x:
                q.pop()   
            q.append(i) 
            # 出队，因为 q[0] 是目前滑动窗口中 nums 最大值的索引 
            # 所以如果当前滑动窗口超出最大值索引，就需要弹出当前最大值
            if i - q[0]>=k:
                q.popleft()
            # 记录答案
            if i >=k-1:
                ans.append(nums[q[0]])
        return ans

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        # 基本思路就是维护单调递增列表
        # 列表中元素为 nums 的值，列表元素个数永远为 k
        # 然后滑动窗口时，移除对应元素，添加对应元素
        from sortedcontainers import SortedList
        windows = SortedList(nums[0:k])
        n = len(nums)
        ans = [windows[-1]]
        # 计算范围，开始滑动
        for i in range(1,n-k+1):
            windows.remove(nums[i-1])
            windows.add(nums[i+k-1])
            ans.append(windows[-1])
        return ans

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 1438

class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        from sortedcontainers import SortedList 
        # 使用有序列表维护滑动窗口
        s = SortedList()
        n = len(nums)
        left = right = ret = 0
        
        while right < n :
            s.add(nums[right])

1
2
3
4
5
6
7
8
9
10

class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        # 基本思路就是维护两个单调队列
        # 分别存储滑动窗口的最大值和最小值
        n = len(nums)
        queMax, queMin = deque(), deque()
        left = right = ret = 0

        while right < n:
            while queMax and queMax[-1]<nums[right]:
…                queMax.remove(nums[left]) if nums[left] in queMax else ''
                queMin.remove(nums[left]) if nums[left] in queMin else ''
                left += 1
            ret = max(ret, right - left + 1)
            right += 1
        return ret

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 1499

# 2398

# 862

这道题整体思路是使用单调队列，但是需要使用前缀和的知识

下面开始的都是单调队列优化 DP 的案例

# 1425

# 375

# 1687

# 单调栈

# 739

# 42

接雨水这道题很经典了，可以使用单调栈的做法，也可以采用前后缀分解，相向双指针

这里面相向双指针的做法非常巧妙，一般人可能想象不到

对于雨水问题，还可以看 11 题，也是比较经典

# 树形 DP

543. 二叉树的直径 (opens new window)

直接递归，或是 dfs（保存全局变量）

124. 二叉树中的最大路径和 (opens new window)

2246. 相邻字符不同的最长路径 (opens new window)

# 区间 DP

# 状态机 DP

# 二叉搜索树

# 前缀和 + 哈希表

面试题 17.05. 字母与数字 (opens new window)

这道题和以往的前缀和题目不太相同，因为是判断子数组是否和为零，因此判断条件为 $[j, i]$ 其中的 $s[j]$ 是否等于 $s[i]$ （其中 s 为前缀和数组）

整体思路就是遍历前缀和数组，然后存入 hash，其中 key 为 $s[i]$ ，value 为 i，然后每次判断 $s[i]$ 是否出现过，如果出现过，那么判断 $j - i$ 是否比 $begin - end$ 大

# 模拟

# 2946

# 打表

2048. 下一个更大的数值平衡数 (opens new window)

# 二分查找

经典题目： 34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode） (opens new window)

使用左闭右闭的做法，详细看提交记录的备注

162. 寻找峰值 - 力扣（LeetCode） (opens new window)

153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode） (opens new window)

153 的解法很巧妙，因为我们在 162 中使用二分法，其作用就是找到数组中的某个峰值，但是无法确定是哪个峰，但是 153 中我们需要求得数组里面只有一个峰值，所以得到的答案必定为正确

值得注意的是这里二分比较的时候，比较的值为 nums[-1] 这个乍看不好想，自己画下图就明白了

33. 搜索旋转排序数组 - 力扣（LeetCode） (opens new window)

这道题简单做法可以先按照 153 求出最小值，然后，再分类下，再用最简单的红蓝染色法二分查找

进阶做法就是，只用一次二分，但是需要分类很多情况，需要自己动手画下（单独写一个函数判断是否为蓝色）

我第一次分类讨论少了两个等号，主要是仔细点就行

# 反转链表

206. 反转链表 - 力扣（LeetCode） (opens new window)

首先头节点是不会消失，所以不需要设置 dummy 节点（就算设置后面无法消除很麻烦），pre = None

92. 反转链表 II - 力扣（LeetCode） (opens new window)

因为头节点可能变化（因为 left 可能等于 0），所以需要设置 dummy 节点，只是反转节点很简单，但是主要是如何反转之后进行连接

按照示例 1 里的数据

循环过后
p0 = 1 p0.next = 2
同时
pre = 4 cur = 5 
需要连接的四个节点都具备了，非常巧妙，直接连接即可
所以 p0 是区别于 cur 和 pre 的关键节点

还有就是 pre 最开始循环的时候，我们是不能破坏 p0.next = 2 的，所以 pre 不能为 p0，应该为 None

1
2
3
4
5
6
7
8

25. K 个一组翻转链表 - 力扣（LeetCode） (opens new window)

没什么特别，主要是先循环一边计算长度 n，主要注意的就是每 k 个循环，然后每次 p0 节点都是由上次循环的 p0.next，只不过需要单独存储下，因为该值后面会被覆盖

# 快慢指针

876. 链表的中间结点 - 力扣（LeetCode） (opens new window)

141. 环形链表 - 力扣（LeetCode） (opens new window)

142. 环形链表 II - 力扣（LeetCode） (opens new window)

142 这道题需要非常复杂的推导，很难说清，还是推荐看下灵神的视频： https://www.bilibili.com/video/BV1KG4y1G7cu/?p=7&spm_id_from=pageDriver

143. 重排链表 - 力扣（LeetCode） (opens new window)

143 本身并不是很难，但是它很好的给前面前面几道题结合了起来

# 删除节点

237. 删除链表中的节点 - 力扣（LeetCode） (opens new window)

19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode） (opens new window)

19 题因为可能倒数最后一个节点，也就是头节点可能变动，所以需要设置 dummy

83. 删除排序链表中的重复元素 - 力扣（LeetCode） (opens new window)

83 可以保留头节点

82. 删除排序链表中的重复元素 II - 力扣（LeetCode） (opens new window)

很明显这道题头节点可能消失，需要设置 dummy

# 二叉树与递归

100. 相同的树 - 力扣（LeetCode） (opens new window)

101. 对称二叉树 - 力扣（LeetCode） (opens new window)

101 这道题可以直接使用 100 的函数，但是需要小改动下，对调下里面的 left 和 right，就是轴对称了

110. 平衡二叉树 - 力扣（LeetCode） (opens new window)

110 这道题不平衡的判断很简单，就是两个子树高度差大于 1 即可，主要是递归的时候如何返回

首先按照正常得到高度的函数，依次递归，但是在递归过程中需要加入为 -1 的情况，也就是不平衡，一旦出现 -1 （不管是左子树还是右子树），之后网上 return 返回的也必须是 -1，最后判断返回的值是否为 -1 即可

199. 二叉树的右视图 - 力扣（LeetCode） (opens new window)

从右视图观察，我们在遍历的过程中需要有两个值，一个是当前递归深度，一次是目前答案列表的长度，利用这两个值判断当前节点是否应该被加入答案列表中，递归深度每次递归时使用 depth 标记即可，答案长度就是 len(ans)，同时注意因为是右视图，深度优先搜索 dfs 优先从右子树遍历

# 验证二叉搜索树

98. 验证二叉搜索树 - 力扣（LeetCode） (opens new window)

分为三种方法，分别为前序中序后序

先序遍历（先根遍历）：先访问根节点，然后访问左子树，最后访问右子树。

中序遍历（中根遍历）：先访问左子树，然后访问根节点，最后访问右子树。

后序遍历（后根遍历）：先访问左子树，然后访问右子树，最后访问根节点。

# 数学

2947. 统计美丽子字符串 I (opens new window)

这里是用到前缀和和哈希表的知识，这些都比较简单，但是关于数学的部分太难了

这里有灵神的关于数学位运算的教程，可以先学习：分享｜从集合论到位运算，常见位运算技巧分类总结！ - 力扣（LeetCode） (opens new window)

# 补充

# LaTex

参考资料：

# 编辑器

力扣编辑器里面的剪切 ctrl + x 无效

解决方案：需要选中代码之后，先复制，然后删除，然后粘贴（同时注意不能先使用 ctrl + x 剪切，否则会失效）

使用 leetcode 编辑光标选中一段代码之后，可以直接点击 $($ 即可为代码两端加上括号（也不限于其他字符）

# 其他注意

`!=` 和 is not 含义是不同的
`==` 用于比较两个对象的值是否相等，而 is 检查两个变量是否指向内存中的同一个对象。在大多数情况下，这意味着你应该使用 `==` 和 `!=`，除非与 None 进行比较。

1
2

编辑

上次更新: 2024/03/24, 08:31:38

← Python 刷题指南周赛汇总→