【基础算法精讲-学习记录】二叉树5
视频学习记录 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# ...
【基础算法精讲-学习记录】二叉树4
视频学习记录 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:...
【基础算法精讲-学习记录】二叉树3
视频学习记录 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...
【基础算法精讲-学习记录】二叉树2
视频学习记录 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:...
【基础算法精讲-学习记录】二叉树1
视频学习记录 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...
申请海外保号神卡德国O2和德国沃达丰实践记录
时效性 需要提前声明，这种近乎于福利性质的 esim 申请非常看时效性，希望读者看到时还能用。 X 上的攻略贴从今年 2 月开始，然后突然说关门后，随后到 5 月又开门到现在（只开了一半），还是有点吃运气啊。 下面是部分参考资料，本文不会手把手讲述怎么申请到卡，而是给这些攻略中的一些步骤加点注释，让后来者方便点。 https://x.com/Hp2ai/status/2058578154025787604https://x.com/AI_Jasonyu/status/2017934338889834825https://x.com/AI_Jasonyu/status/2046746630859210806 注释沃达丰 vs O2 当前时间，两者由于 KYC（Know Your...
【基础算法精讲-学习记录】反转链表
视频学习记录 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....
【基础算法精讲-学习记录】二分查找2
视频学习记录 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...
【基础算法精讲-学习记录】二分查找1
视频学习记录 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): ...
【基础算法精讲-学习记录】相向双指针2
视频学习记录 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 =...
【基础算法精讲-学习记录】相向双指针1
视频例题学习记录 https://www.bilibili.com/video/BV1bP411c7oJ 视频讲了两道题，两数之和和三数之和，下意识想用的哈希表记录已遍历值从而让另一个值是否符合的判断只要O（1）的方法。但这个方法空间复杂度O（n），且很难向三数之和，四数之和推广。 灵神给出了相向双指针解法，也就是首尾各一个指针。首先是需要数组有序，默认非降序排列，然后判断当前两个之和与目标的关系，比目标大说明这两个值需要小点，就要大的那个前移。小了的话，就需要小值指针后移。注意这里不同情况都只对应一种指针移动。 那么对于三数之和呢？两个指针看起来不够用。确实，所以把多出来的那个放外面加一个循环处理，剩下两个还是相向双指针。 课后作业完成记录2824. 统计和小于目标的下标对数目 https://leetcode.cn/problems/count-pairs-whose-sum-is-less-than-target/ 123456789101112131415class Solution: def countPairs(self, nums:...
一起来学Python基础|LearnBasicPythonTogether
前言 发现 Python 写起来比 C++ 爽多了，以后写 Leetcode 和其他程序，只要对性能和应用场景没有特殊要求，就只用 Python 啦！（蛇堕力，悲） 总之，下面的内容是对学习了 《Python编程-从入门到实践》 基础部分的小结，不是那种事无巨细的笔记，而是学习中印象比较深刻的部分。（也就是对于本人比较新的部分） 原计划每章写一个博客来记录，发现大部分内容已经在 C++ 那边烂熟于心，只要补充 Python 特色的实现方式和小部分新特性就好。 由于下面内容可能涉及练习的剧透，所以想要尽可能地发挥这本书的学习效用的话，建议自行学习完成再看本文。 正文 首先，这是练习存放的对应仓库地址 如果仔细看的话，会发现练习不全，因为有些练习陆爻齐觉着与其它练习考察重复，或者他们是陆爻齐已经十分熟悉的内容。 字符串去除前后空格 很多时候，我们有去除字符串前面或者后面的空格的需求，这个时候就可以使用下面的例子中展现的 strip 系列函数。 1234name = "\tWang \n Xiao\tMing ...
【Leetcode Daily】LeetcodeDailySummary-滑动窗口小结
类别 该算法主要分为定长滑动窗口和不定长滑动窗口，前者由于窗口大小固定，往往是来求窗口内某种极值，极大、极小或者其它事物，后者则专注于求子数组/子字符串的数量。 不定长滑动窗口有的会尽可能追求窗口长度的极值，又会因为题目，细分几个种类，比如越长越满足、越短月满足，或者刚好满足的情况。 定长滑动窗口 基本的思路是，先是初始化一个定长的窗口，初始化到窗口长度减一，然后在循环过程中，先加入新元素，达到窗口满足大小的情况，然后自行检查窗口是否满足题目条件，并更新记录数值。随后退出最旧的元素。 示例题目与更为详细的思路讲解在博客 【Leetcode Daily】1456定长子串中元音的最大数目 不定长滑动窗口 与定长滑动窗口的不同之处在于，不需要开始先把窗口调整至某个状态，只需要不断地加入元素，检查条件，然后在不满足条件时，持续退出旧元素，直到再次满足条件。 至于几种分类，对于求满足条件窗口长度，只要每次循环持续更新记录数值的最大或最小就好，像是博客 【Leetcode...