力扣刷题笔记
# 单调队列
# 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
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
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])
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
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)
这道题和以往的前缀和题目不太相同,因为是判断子数组是否和为零,因此判断条件为 其中的是否等于(其中 s 为前缀和数组)
整体思路就是遍历前缀和数组,然后存入 hash,其中 key 为 ,value 为 i,然后每次判断 是否出现过,如果出现过,那么判断 是否比 大
# 模拟
# 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
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
参考资料:
- mohu.org/info/lshort-cn.pdf (opens new window)
- mohu.org/info/symbols/symbols.htm (opens new window)
- Latex常见用法汇总-腾讯云开发者社区-腾讯云 (tencent.com) (opens new window)
- LaTeX数学符号大全_latex 数学符号-CSDN博客 (opens new window)
# 编辑器
力扣编辑器里面的剪切 ctrl + x 无效
解决方案:需要选中代码之后,先复制,然后删除,然后粘贴(同时注意不能先使用 ctrl + x 剪切,否则会失效)
使用 leetcode 编辑光标选中一段代码之后,可以直接点击 即可为代码两端加上括号(也不限于其他字符)
# 其他注意
`!=` 和 is not 含义是不同的
`==` 用于比较两个对象的值是否相等,而 is 检查两个变量是否指向内存中的同一个对象。在大多数情况下,这意味着你应该使用 `==` 和 `!=`,除非与 None 进行比较。
2