Hot100

题目要求 给你一个数组 prices，其中 prices[i] 表示第 i 天的股票价格。 你只能完成一次交易： 选择某一天买入一支股票 选择未来某一天卖出这支股票 返回能获得的最大利润。如果无法盈利，返回 0。 输入输出 输入：prices: List[int] 输出：最大利润 int 只能买一次、卖一次。 买入日必须早于卖出日。 可以选择不交易，此时利润是 0。 示例 输入：prices = [7,1,5,3,6,4] 输出：5 最优做法是在价格为 1 时买入，在价格为 6 时卖出，利润是 6 - 1 = 5。 输入：prices = [7,6,4,3,1] 输出：0 价格一直下降，任何买入后再卖出都会亏钱，所以返回 0。 约束 1 <= prices.length <= 10^5 0 <= prices[i] <= 10^4 Step 1：先固定买卖顺序 先看这个例子： prices = [7,1,5,3,6,4] 如果只看价格差，最大利润来自： 1 -> 6 profit = 5 这是合法的，因为价格 1 出现在价格 6 之前。 ...

题目要求 给你一个整数数组 nums。 你一开始站在下标 0。nums[i] 表示从位置 i 最多可以向右跳多少步。 题目要求判断：能不能到达最后一个下标。 输入输出 输入：nums: List[int] 输出：bool 从下标 0 出发。 每个位置的数字表示最大跳跃长度，不是必须跳这么远。 只需要判断能否到达最后一个下标，不需要返回具体路径。 示例 输入：nums = [2,3,1,1,4] 输出：true 一种跳法是： 0 -> 1 -> 4 从下标 0 可以跳到下标 1，再从下标 1 跳到最后一个下标。 输入：nums = [3,2,1,0,4] 输出：false 无论怎么跳，都会被下标 3 的 0 卡住，无法到达最后一个下标 4。 约束 1 <= nums.length <= 10^4 0 <= nums[i] <= 10^5 Step 1：不要先猜路径，先看覆盖范围 先看失败样例： nums = [3,2,1,0,4] 从下标 0 最多可以跳到下标 3。 看起来选择很多： 0 -> 1 0 -> 2 0 -> 3 当前 baseline 是： ...

题目要求 给你一个 m x n 的二维字符网格 grid： "1" 表示陆地 "0" 表示水 题目要求返回岛屿数量。 一个岛屿由水平或垂直相邻的陆地组成。对角线相邻不算连通。可以认为网格四周都被水包围。 输入输出 输入：grid: List[List[str]] 输出：岛屿数量 int 只看上下左右四个方向。 "0" 水格子不能算作岛屿的一部分。 示例 输入： [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] 输出：1 这些陆地通过上下左右连成一整块，所以答案是 1。 输入： [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ] 输出：3 这里有三块互不连通的陆地，所以答案是 3。 约束 m == grid.length n == grid[i].length 1 <= m, n <= 300 grid[i][j] 只会是 "0" 或 "1" 这一题可以用 DFS 或 BFS 做。这里的目标是练并查集：把每块陆地当成一个节点，把相邻陆地合并，最后留下的陆地连通分量数量就是岛屿数量。 ...

副标题 / 摘要 并查集不是从 find 和 union 这两个函数名开始背。它要解决的问题是：怎样判断两个点是否已经属于同一个集合，并在看到一条连接关系时把两个集合合并。 预计阅读时长：10~12 分钟 标签：Hot100、并查集、Union-Find、DSU、图 SEO 关键词：并查集, Union-Find, DSU, find, union, count, 路径压缩 元描述：用 Python 从零推导并查集模板，讲清 parent、find、union、count、路径压缩和连通分量计数。 A — Algorithm（从集合合并压力开始） 小任务：不断合并集合，并回答连通性 假设有 5 个点： 0, 1, 2, 3, 4 一开始，每个点都是一个独立集合： {0}, {1}, {2}, {3}, {4} 现在依次发生两次合并： union(0, 1) union(1, 2) 我们想回答三个问题： 0 和 2 是否在同一个集合？ 3 和 4 是否在同一个集合？ 当前一共有几个集合？ 手工看答案是： {0, 1, 2}, {3}, {4} 所以： 0 和 2 在同一个集合 3 和 4 不在同一个集合 当前 count = 3 这就是并查集要解决的核心任务： ...

副标题 / 摘要 208 题的难点不在算法变化，而在把 Trie 模板按平台接口写稳：insert 建路径，search 查完整单词，startsWith 只查前缀路径。 预计阅读时长：8~10 分钟 标签：Hot100、Trie、前缀树、LeetCode 208 SEO 关键词：LeetCode 208, Implement Trie, Prefix Tree, startsWith 元描述：从接口要求出发实现 LeetCode 208，讲清 Trie 节点、children、is_end、insert/search/startsWith 的区别。 A — Algorithm（题目与算法） 先看最小操作压力 208 题最关键的操作序列是： Trie trie = new Trie() trie.insert("apple") trie.search("apple") -> true trie.search("app") -> false trie.startsWith("app") -> true trie.insert("app") trie.search("app") -> true 这个例子说明： app 可以是 apple 的前缀 但只有插入过 app 后，search("app") 才能返回 True 所以这题不是“路径存在就算命中”。 我们必须同时维护： 路径是否存在 这条路径是否刚好是完整单词 题目接口 设计一个 Trie，也叫前缀树，支持三个操作： ...

副标题 / 摘要 Trie 的重点不是背代码，而是理解“一个节点代表一个前缀”。只要这个模型稳定，插入、完整单词查询和前缀查询都会变成同一个循环。 预计阅读时长：8~10 分钟 标签：Hot100、Trie、前缀树、字典树 SEO 关键词：Trie, 前缀树, 字典树, children, is_end 元描述：用 Python 写一个最小 Trie 模板，讲清节点字段、children 走法、结束标记和循环 invariant。 A — Algorithm（从一个小任务开始） 小任务：同时回答完整单词和前缀 假设已经插入： app apple bat 现在要问： app 是不是完整单词？ ap 是不是某个单词的前缀？ apply 是否存在？ 这个小任务暴露了两个缺口： 只用哈希集合，可以快速判断完整单词，但不能自然回答前缀问题 只看路径存在，又会把 app 和 apple 的前缀关系混成一件事 Trie 要解决的就是：让很多字符串共享公共前缀，同时还能区分“前缀存在”和“完整单词存在”。 从压力反推要支持什么 我们先不管任何题目接口，只定义一个自己的模板： insert(word)：把一个单词插入 Trie search(word)：判断完整单词是否存在 starts_with(prefix)：判断是否存在以 prefix 开头的单词 最小结构图 插入 app 和 apple 后，结构可以想成： root └─ a └─ p └─ p [end] └─ l └─ e [end] 这里最重要的是： ...

题目要求 给你一个 n x n 的矩阵 isConnected，其中有 n 个城市。 如果 isConnected[i][j] == 1，说明城市 i 和城市 j 直接相连；如果两个城市可以通过若干个直接相连的城市互相到达，它们就属于同一个省份。 题目要求返回省份的总数。 这里最容易误解的一点是：题目不是让我们数矩阵里有多少个 1，也不是只看直接相连的城市对。它真正要数的是： 直接或间接连接在一起的城市组有多少个。 换成图的语言，就是： 给定一个无向图的邻接矩阵，返回这个图的连通分量数量。 输入输出 输入：isConnected: List[List[int]] 输出：省份数量 int 城市编号可以按 0..n-1 理解。 isConnected[i][j] == 1 表示城市 i 和城市 j 之间有边。 isConnected[i][j] == 0 表示城市 i 和城市 j 没有直接边。 示例 1 输入：isConnected = [ [1, 1, 0], [1, 1, 0], [0, 0, 1] ] 输出：2 城市 0 和城市 1 直接相连，所以它们属于同一个省份。 ...

题目要求 输入输出 输入：整数数组 nums nums[i] 表示第 i 间房子的金额 不能偷相邻房子 输出：返回最多能偷到的金额 约束：1 <= nums.length <= 100，0 <= nums[i] <= 400 示例 输入：nums = [1,2,3,1] 输出：4 解释：偷下标 0 和下标 2，金额 1 + 3 = 4 输入：nums = [2,7,9,3,1] 输出：12 解释：偷下标 0、2、4，金额 2 + 9 + 1 = 12 这篇只用 Python，从这个二选一冲突推出一维 DP。 从 [1,2,3,1] 的相邻冲突开始 看例子： nums = [1,2,3,1] 如果偷下标 2 的房子，金额是 3，那么下标 1 和下标 3 都不能偷。 如果不偷下标 2，答案可能来自前面下标 0..1 的最优结果。 所以走到某一间房时，核心选择只有两个： ...

题目要求 输入输出 输入：整数数组 nums 输出：返回连续非空子数组的最大和 子数组必须连续 至少选一个元素 约束：1 <= nums.length <= 10^5，-10^4 <= nums[i] <= 10^4 示例 输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：[4,-1,2,1] 的和最大，为 6 输入：nums = [1] 输出：1 这篇只用 Python，从 dp[i] 的含义一步一步推出 Kadane 算法。 从 [-2,1,-3,4] 的断点开始 看一个前缀例子： nums = [-2, 1, -3, 4] 如果走到 4，有两种选择： 把前面的某个连续子数组接到 4 前面 从 4 自己重新开始 这里的关键不是“所有子数组怎么枚举”，而是： 当我们决定一个最优子数组必须以当前位置结尾时，它的来源只有两种：接上前一个位置的最优结尾，或者从当前位置重新开始。 这就是一维 DP 的入口。 Step 1：先定义一个更小的问题 直接问“整个数组的最大子数组和是多少”太大。我们先强加一个限制： 如果子数组必须以第 i 个元素结尾，它的最大和是多少？ 这个值记为 dp[i]。 这里的 dp[i] 不是“前 i 个元素里的最大子数组和”。它更窄： ...

题目要求 输入输出 输入：nums，长度 1 <= nums.length <= 10 元素范围：-10 <= nums[i] <= 10 所有元素互不相同 输出：返回 nums 的所有可能子集 顺序：结果顺序不限，子集内部不需要考虑排列顺序 示例 输入：nums = [1,2,3] 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] 这篇只用 Python 构造一个最小可运行解法。 从 [1,2] 的搜索树开始 最小但有分叉的例子是： nums = [1,2] 答案应该是： [], [1], [1,2], [2] 注意这里没有 [2,1]。这说明问题不是“随便排列所有选择”，而是“每个元素选或不选，且同一组元素只出现一次”。 如果把构造过程画成树： [] |- [1] | |- [1,2] |- [2] 这棵树暴露出两个事实： 每个节点都是一个合法子集。 进入 [1] 之后，后面只能继续看 2，不能回头再选 1 或生成 [2,1]。 Step 1：先说清楚一个递归层在解决什么 如果当前已经选出一个 path，剩下的问题是： 从某个起点之后的元素里，继续选择若干个元素，扩展当前 path。 这个“某个起点”必须被记下来。否则 [1,2] 和 [2,1] 会从不同路径重复出现。 先写最小骨架。它只保留两个状态： ...