笺札

300. 最长递增子序列-LeetCode 🎯 问题描述（来源于LeetCode） 描述：给你一个整数数组 nums，找到其中最长严格递增子序列的长度。 说明： 子序列是由数组元素删除（或不删除）任意数量的元素后，不改变其余元素顺序得到的序列。 示例： 示例 1： 123输入：nums = [10,9,2,5,3,7,101,18]输出：4解释：最长递增子序列是 [2,3,7,18]，长度为 4。 示例 2： 12输入：nums = [0,1,0,3,2,3]输出：4 💻 解题思路 思路1：动态规划 (自底向上) 核心思想： 这是一个标准的线性 DP 问题。 状态定义：dp[i] 表示以 nums[i] 为结尾的最长递增子序列的长度。 注意：必须定义为“以 i 结尾”，而不是“前 i 个元素中的最大长度”，这样才能推导状态转移。 状态转移：对于每个元素 i，我们去看它前面所有的元素 j。 如果 nums[j] < nums[i]，说明 i 可以接在 j 后面。 此时 dp[i] = max(dp[i], dp[j] + 1)...

3090. 每个字符最多出现两次的最长子字符串 🎯 问题描述（来源于LeetCode） 描述： 给你一个字符串 s，请找出满足每个字符最多出现两次的最长子字符串，并返回该子字符串的最大长度。 说明： 子字符串：字符串中一段连续非空的字符序列。 核心逻辑：使用滑动窗口维护一个“每个字符出现次数不超过 2 次”的区间。当某个字符出现次数达到 3 次时，收缩左边界，直到该字符次数恢复为 2 次。 示例： 示例 1： 1234输入： s = "bcbbbcba"输出： 4解释：以下子字符串长度为 4，并且每个字符最多出现两次：`"bcbbbcba"`。 示例 2： 12345输入：s = "aaaa"输出：2解释：子字符串 "aa" 满足条件（'a' 出现 2 次）。子字符串 "aaa" 不满足条件（'a' 出现 3 次）。 💻 解题思路 思路1：不定长滑动窗口 思路1：代码实现 1234567891011121...

2461.长度为k子数组中的最大和 🎯 问题描述（来源于LeetCode） 描述： 给你一个整数数组 nums 和一个整数 k。请你从 nums 中找出满足下述条件的最大子数组和： 子数组的长度是 k。 子数组中的所有元素各不相同（互不相同）。 如果不存在满足这些条件的子数组，返回 0。 说明： 子数组：数组中一段连续非空的元素序列。 核心逻辑：长度为 k 的子数组中所有元素各不相同，等价于该子数组中不同元素的个数等于 k。 示例： 示例 1： 123输入：nums = [1,2,3,4,5], k = 3输出：12解释：子数组 [3,4,5] 的和为 12，长度为 3，且所有元素互不相同。 示例 2： 123输入：nums = [1,2,2,1], k = 3输出：0解释：长度为 3 的子数组有 [1,2,2] 和 [2,2,1]，它们都包含重复元素 2，因此不存在满足条件的子数组。 💻 解题思路 思路1：定长滑动窗口 + 哈希表计数 思路1：代码实现 123456789101112131415161718192021222324252...

133. 克隆图 (Clone Graph) 🎯 问题描述（来源于LeetCode） 描述：给你无向连通图中一个节点的引用，请你返回该图的深拷贝（克隆）。图中的每个节点都包含它的值 val（int）和其邻居的列表（list[Node]）。 1234class Node { public int val; public List neighbors;} 测试用例格式： 简单起见，每个节点的值都和它的索引相同。例如，第一个节点值为 1（val = 1），第二个节点值为 2（val = 2），以此类推。该图在测试用例中使用邻接列表表示。 示例 1：12345678输入: adjList = [[2,4],[1,3],[2,4],[1,3]]输出: [[2,4],[1,3],[2,4],[1,3]]解释:图中有 4 个节点。节点 1 的值是 1，它有两个邻居：节点 2 和 4。节点 2 的值是 2，它有两个邻居：节点 1 和 3。节点 3 的值是 3，它有两个邻居：节点 2 和 4。节点 4 的值是 4，它有两个邻居：节点 1 和 3。 (注：这是...

200. 岛屿数量 (Number of Islands) 🎯 问题描述（来源于LeetCode） 描述：给你一个 m x n 的二维二进制网格 grid，其中 1 代表陆地，0 代表水域。岛屿总是被水域包围，并且通过水平方向或垂直方向上相邻的陆地连接而成。你可以假设网格的四条边均被水域包围。 说明：请你计算网格中岛屿的数量。 示例： 示例 1：12345678输入: grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"]]输出:...

695. 岛屿的最大面积 🎯 问题描述 给定一个包含 0 和 1 的二维网格 grid，其中 1 代表陆地，0 代表水域。岛屿是由水平方向或垂直方向上相邻的陆地连接而成的。请计算并返回最大的岛屿面积。如果不存在岛屿，则返回面积 0。 测试用例格式： 输入：二维列表 grid，每个元素为 0 或 1 输出：整数，表示最大岛屿面积 💻 解题思路 核心算法：深度优先搜索（DFS） 算法原理 遍历网格：使用双重循环遍历网格中的每个格子 发现陆地：当遇到值为 1 的格子时，启动 DFS 计算该岛屿的面积 淹没岛屿：在 DFS 过程中将访问过的陆地标记为 0，防止重复计算 面积累加：通过递归返回值累加每个连通陆地的面积 关键技术点 递归返回值：利用返回值传递子问题的解，避免传值问题 边界处理：在递归开始时检查边界条件 状态标记：直接修改原数组标记已访问位置，节省空间 💻 解题思路 思路1： DFS 思路1：代码实现 12345678910111213141516171819202122232425262728class Solution: def m...

494. 目标和 🎯 问题描述 描述：给定一个非负整数数组 nums 和一个目标整数 target，对于数组中的每个数字，可以选择给它添加 ‘+’ 或 ‘-’ 符号。返回可以使最终数组和等于目标值 target 的表达式数目。 说明： 给定数组非空，且包含非负整数 数组长度 n ≤ 20 数组中数字总和 ≤ 1000 目标值 -1000 ≤ target ≤ 1000 示例： 示例 1： 12345678输入：nums = [1,1,1,1,1], target = 3输出：5解释：有 5 种方法让最终和为 3：-1+1+1+1+1 = 3+1-1+1+1+1 = 3+1+1-1+1+1 = 3+1+1+1-1+1 = 3+1+1+1+1-1 = 3 示例 2： 12输入：nums = [1], target = 1输出：1 💻 解题思路 思路1：记忆化搜索（递归DP） 核心思想：这是一个典型的子集划分问题，可以通过递归枚举所有可能的符号组合来解决。 问题转化： 设所有添加 ‘+’ 的数字之和为 P，所有添加 ‘-’ 的数字之和为 N 我们需要 P - ...

1137. 第 N 个泰波那契数-LeetCode 🎯 问题描述（来源于LeetCode） 描述：泰波那契序列 Tn 定义如下： 说明： 答案保证在 32 位有符号整数范围内（即 [−231,231−1][-2^{31}, 2^{31} - 1][−231,231−1]）。 示例： 示例 1： 12345输入：n = 4输出：4解释：T_3 = 0 + 1 + 1 = 2T_4 = 1 + 1 + 2 = 4 示例 2： 12输入：n = 25输出：1389537 💻 解题思路 思路1：记忆化搜索 (Memoization Search) 核心思想： 泰波那契数列是斐波那契数列的变种，同样具有明显的重叠子问题性质。如果使用朴素递归（直接函数调用自己），时间复杂度将是指数级的，导致超时。 为了解决这个问题，我们采用记忆化搜索（动态规划的自顶向下实现）： 查表：在计算前，先检查该状态是否已经计算过。 计算：如果未计算过，递归计算其依赖的前三个状态之和。 存表：计算出结果后，立即将其存入哈希表（字典）中，供后续调用复用。 算法步骤： 初始化一个字典...

226. 翻转二叉树 🎯 问题描述（来源于LeetCode） 描述：给定一个二叉树的根节点 root，请翻转这棵树，即交换每个节点的左子树和右子树，并返回翻转后的根节点。 说明： 这是一个经典的树形操作问题，核心在于理解“镜像”概念。 示例： 示例 1：123输入：root = [4,2,7,1,3,6,9]输出：[4,7,2,9,6,3,1]解释：根节点4的左右孩子2和7互换，随后2的左右孩子1和3互换，7的左右孩子6和9互换。 💻 解题思路 思路1：递归 (自底向上) 核心思想： 利用二叉树的分治思想。翻转一棵树 = 翻转左子树 + 翻转右子树 + 交换左右指针。 基准情况：如果当前节点为空，直接返回空。 递归拆解：假设 invertTree 函数已经帮我们把左右子树翻好了。 合并结果：将翻好的右子树挂在左边，翻好的左子树挂在右边。 思路1：代码实现 1234567891011121314class Solution: def invertTree(self, root: Optional[TreeNode]) -> Optional[...

204. 计数质数 (Count Primes) 🎯 问题描述（来源于LeetCode） 描述：给定整数 n，返回所有小于 n 的非负质数的数量。 说明： 质数：在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。 注意是 小于 n，不包含 n 本身。 示例： 示例 1：123输入：n = 10输出：4解释：小于 10 的质数一共有 4 个，分别为 2, 3, 5, 7。 示例 2：123输入：n = 0输出：0解释：没有小于 0 的数。 💻 解题思路 思路1：枚举优化（试除法） 这是一个典型的枚举算法应用。我们需要遍历从 2 到 n-1 的每一个数字，并判断其是否为质数。 核心优化点（剪枝）： 单纯枚举 1 到 n 判断是否整除的时间复杂度是 O(N)O(N)O(N)。利用数学性质可以将其优化至 O(N)O(\sqrt{N})O(N​)： 平方根性质：如果一个数 NNN 有因数，那么必然有一个因数小于或等于 N\sqrt{N}N​。 实现：在判断质数函数 Iszhi 中，循环只需要从 2 遍历到 int(n ** 0.5) + 1 即可。 ...