LuYaoQi's Blogs

视频学习记录 https://www.bilibili.com/video/BV1mY411D7f6? 以模拟某种情况下的全排列为基础的排列型回溯，核心是通过bool列表或者集合记录已走的路径。 例题和课后作业代码记录46. 全排列 https://leetcode.cn/problems/permutations/description/ 1234567891011121314151617class Solution: def permute(self, nums: List[int]) -> List[List[int]]: ans = [] path = [] not_on_path = {} n = len(nums) def dfs(index:int, not_on_path:set): if index == n: nonlocal ans, path ...

视频学习记录 https://www.bilibili.com/video/BV1xG4y1F7nC 组合型的回溯，就是在子集型回溯的基础上增加了一些限制，可以通过剪枝进一步减少搜索范围。 之前的子集可能是找一串字符串的各种子集，组合则是限制了最终的子集长度，内容等。 例题和课后作业代码记录77. 组合 https://leetcode.cn/problems/combinations/description/ 123456789101112131415161718class Solution: def combine(self, n: int, k: int) -> List[List[int]]: ans = [] path = [] def dfs(i:int, select_num:int): nonlocal ans, path # print(ans, path) if select_num == k: ...

视频学习记录 https://www.bilibili.com/video/BV1mG4y1A7Gu/? 回溯，主要是问自己三个问题：当前操作是什么，子问题是什么，下一个子问题是什么 本次主要学的是子集型回溯，特点是每个元素都可以选或不选，由此就有两个解答思路： 从输入（元素）角度：每个递归都是判断一个元素选或不选； 从答案角度：每个递归是在比上回更小的子问题上遍历元素，间接排除了不同递归层次重复选择子问题的情况； 例题和课后作业代码记录17. 电话号码的字母组合 https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/ 123456789101112131415161718192021222324252627MAPPING = { "2": "abc", "3": "def", "4": "ghi", ...

视频学习记录 https://www.bilibili.com/video/BV1hG4y1277i? 层序遍历，在二叉树中也能叫BFS，与DFS相比，核心就是从上往下一层层地遍历二叉树。 一种实现方式是准备两个数组，cur和nxt分别存放当前要遍历的节点和下一层的节点，一轮轮遍历。 另一种不用nxt数组，下一层的节点直接放在cur后面（cur当队列用），遍历每一层节点时注意当前层的节点数目来遍历。 例题和课后作业代码记录102. 二叉树的层序遍历 https://leetcode.cn/problems/binary-tree-level-order-traversal/description/ 1234567891011121314151617181920212223242526# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# ...

视频学习记录 https://www.bilibili.com/video/BV1W44y1Z7AR 本次专注于“最近公共祖先”，核心就是聚焦一个节点分类讨论，当要找的节点在其左右，或者自己就是要怎么处理，其他详细内容在代码注释中。 例题和课后作业代码记录236. 二叉树的最近公共祖先 https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/ 1234567891011121314151617181920212223# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution: def lowestCommonAncestor(self, root:...

视频学习记录 https://www.bilibili.com/video/BV14G411P7C1/ 这一节的重点在于理解遍历二叉搜索树的三种方式，前序中序和后序，具体都在下面第一个代码记录中。 例题和课后作业代码记录98. 验证二叉搜索树 https://leetcode.cn/problems/validate-binary-search-tree/description/ 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution: def...

视频学习记录 https://www.bilibili.com/video/BV18M411z7bb 承接上篇 【基础算法精讲-学习记录】二叉树1，本期是对于二叉树中递归的灵活运用，只要简单调整，之前的 dfs 遍历也能用于判断两个二叉树是否相同，或者一个二叉树是否对称这种。 总之就是别被全局的复杂吓住，梳理好单个节点上下关系就能写出递归。 例题和课后作业代码记录100. 相同的树 https://leetcode.cn/problems/same-tree/description/ 12345678910111213# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution: def isSameTree(self, p:...

视频学习记录 https://www.bilibili.com/video/BV1UD4y1Y769/ 二叉树往往用递归的方法比较好解决，而思考如何递归的秘诀在于：从顶层视角看，对于一个节点，上面递什么，下面归什么，边界条件是什么。 换句话就是，不要被整体迷住，专注于其中的一个节点和其左右子树的关系（有时还有父节点传的东西）就行 例题和课后作业代码记录104. 二叉树的最大深度 https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/ 12345678910111213# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution: def...

视频学习记录 https://www.bilibili.com/video/BV1VP4y1Q71e 前后指针，标题看着和【基础算法精讲-学习记录】快慢指针差不多，都是一前一后两个指针，但是要解决的重点不同。 快慢指针强调的是两个指针行动的速度不同，这样才方便找到中间节点；这次的前后指针则是强调偏快的指针是作为侦查兵去检查重复值等，这样才方便链表去重。 例题和课后作业代码记录237. 删除链表中的节点 https://leetcode.cn/problems/delete-node-in-a-linked-list/description/ 1234567891011121314151617181920# Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val = x# self.next = Noneclass Solution: def deleteNode(self, node): ...

视频学习记录 https://www.bilibili.com/video/BV1KG4y1G7cu 快慢指针遍历链表作为代码只有下面几行： 123456def getMid(head): slow, fast = head, head while fast and fast.next: fast = fast.next.next slow = slow.next return slow 其中最核心的在于，循环条件中，fast是链表长度为偶数停，fast.next则是在链表长度偶数停，不用死记硬背的。用长度为2和3的链表自己就能推出来。 对于一些诡异的环形链表II这种题目，放宽心，这是面试记的，自己要能推出来，当初高考数学就不是这个分了。 例题和课后作业代码记录876. 链表的中间结点 https://leetcode.cn/problems/middle-of-the-linked-list/description/ 123456789101112131415# Definition for...

视频学习记录 https://www.bilibili.com/video/BV1sd4y1x7KN 链表反转小结下来就三点，首先理解下面这个 pre 和 cur 是怎么让一个链表反转过来的。 12345678def reverseList(l): pre, cur = None, l while cur: nxt = cur.next cur.next = pre pre = cur cur = nxt return pre 然后，了解到这样反转后，pre 指的是反转后链表的第一个节点，同时也是原来位置上那一段的最后一个，而 cur 在下一段的第一个（如果没有下一段就是空嘛） 最后，如果需要在一个链表上实现分段多次反转，每一小段的反转前的那个节点可以命名为 p0，负责将上一段的最后与下一段刚反转的头衔接。p0 下一个就是 pre，为了避免只反转 1 个元素链表特殊情况让 p0 和 pre 一个位置，可以引入哨兵节点。 例题和课后作业代码记录206....

视频学习记录 https://www.bilibili.com/video/BV1QK411d76w 这节课讲得是二分查找的灵活运用，比如找数组中的小峰值和那种旋转排序数组的最小值都可以用。核心是通过二分判断一半的数据性质。 例题和课后作业代码记录162. 寻找峰值 https://leetcode.cn/problems/find-peak-element/description/ 12345678910111213141516class Solution: def findPeakElement(self, nums: List[int]) -> int: # 由于相邻元素值不同，可以通过二分查找，直接切入到某个峰值的左右侧然后迅速逼近 # 在这里定，红色就是指针往左，蓝色是峰值以及峰值往右，由于最右边的值必定蓝色，所以不在二分区间 # 时间 Ologn，空间 O1 n = len(nums) left = 0 right = n - 2 while...

视频学习记录 https://www.bilibili.com/video/BV1AP41137w7 二分查找遵循两个不变量原则，分别是左指针以左不符合和右指针以右符合（具体是否包括左右指针自身根据取的闭区间或者开区间决定） 判断左右指针更新后是否为mid或者加减一，也是看区间，如果是闭区间，那么左右指针一开始就是可能的边界值，那么最后一个值时，两个指针是同一个位置，自然需要加减一，否则死循环。 熟悉后，对于问题的二分可以倒着推导。比如题目要求找到一个数值h，这个h需要在满足某些条件下尽量大或者尽量小，那么就假设找到题目说的h，看看h的左右两侧是不是符合某些性质，比如左边都不符合条件，右侧都符合这种。然后根据这些信息就可以确定左右指针怎么更新等二分细节。 例题和课后作业代码记录34....

视频学习记录 https://www.bilibili.com/video/BV1hd4y1r7Gq 滑动窗口是基于双指针的技巧，本质就是在维护左指针和右指针之间这个序列满足或不满足某种条件，一旦达到需要窗口需要变化的情况，就让左指针右移来缩小窗口。 例题和课后作业代码记录209. 长度最小的子数组 https://leetcode.cn/problems/minimum-size-subarray-sum/description/ 123456789101112131415161718192021222324252627282930313233class Solution: def minSubArrayLen(self, target: int, nums: List[int]) -> int: # 另一种写法 n = len(nums) ans = n + 1 left = 0 cur_sum = 0 for right in range(n): ...

视频学习记录 https://www.bilibili.com/video/BV1Qg411q7ia 最重要的一点，在于给出了双指针在过程中，左右分别什么时候才动。就拿“11. 盛最多水的容器”来说，如果取其中较高的那个指针向中间移动，宽度肯定减少，而高度就算下个值比现在大也不会增加，因为另一边更小。所以要动矮的那个，万一取到高得多大值就可以弥补宽度大缩小。 至于接雨水，核心在于把计算接住的雨水转换成一列列上水的累计。这样就能通过前后缀分解计算一列列的水。 例题和课后作业代码记录11. 盛最多水的容器 https://leetcode.cn/problems/container-with-most-water/description/ 123456789101112131415161718class Solution: def maxArea(self, height: List[int]) -> int: # 时间复杂度 n，相向遍历一次，空间复杂度 1，额外空间与变量大小无关 l = 0 r =...