企业官网建设流程全解析

• 教程
• 文档
• 知识库

导读

本文基于 AlgoNote（算法通关手册）LeetCode 300~399 题章节 的 100 道题目解析，系统梳理该区间题目的算法分布与学习路径：从最长递增子序列、零钱兑换等动态规划经典题，到区间和统计、图论并查集、数据结构设计等高阶专题。读完本文，你将掌握这 100 道题的题号—算法—题解文件对应关系，理解每类问题的核心思路，并能结合仓库内的 Python 源码（树状数组、线段树、并查集、完全背包等实现）进行对照学习。

章节概览：300~399 题的整体画像

LeetCode 300~399 题区间是算法题中「承上启下」的一段：它延续了 200~299 题的经典基础，又大量引入动态规划进阶（区间 DP、树形 DP、背包变体）、区间统计（前缀和、树状数组、线段树、归并排序）、数据结构设计、带权并查集等面试高频主题。

从该章节各题解文件头部标注的标签与难度（如 0300. 最长递增子序列 为「数组、二分查找、动态规划 / 中等」，0312. 戳气球 为「数组、动态规划 / 困难」，0303. 区域和检索 - 数组不可变 为「设计、数组、前缀和 / 简单」）可以看出，本章覆盖简单、中等、困难三个难度等级，标签横跨数组、链表、树、图、字符串、位运算、贪心、DP 等几乎所有主流算法分类，是全书「题目解析」部分极具训练价值的一段。

一、动态规划专题：本章的核心重镇

300~399 区间包含了多道 DP 里程碑式题目，覆盖了线性 DP、区间 DP、树形 DP、背包 DP 等主要范式。

1. 线性 DP 与二分优化：0300 最长递增子序列

0300. 最长递增子序列 给出了两套思路：

• 思路 1（朴素 DP）：定义dp[i]为「以nums[i]结尾的最长递增子序列长度」，转移方程为dp[i] = max(dp[i], dp[j] + 1)（0 ≤ j < i且nums[j] < nums[i]），初始dp[i] = 1，最终答案为max(dp)。时间复杂度O(n²)。
• 思路 2（DP + 二分查找）：维护tails[k]表示「长度为k+1的 LIS 的最小末尾元素」，遍历每个元素x时用bisect.bisect_left(tails, x)找到第一个≥ x的位置：若超出数组长度则追加，否则用更小的x覆盖，最终len(tails)即为答案。时间复杂度优化到O(n log n)。

这道题是「线性 DP 如何用贪心 + 二分降复杂度」的经典范本，其思想会复用在 0354. 俄罗斯套娃信封问题（先排序再对第二维做 LIS）等题目中。

2. 背包 DP：0322 零钱兑换（完全背包求最小数量）

0322. 零钱兑换 是「完全背包」的经典变形——每种硬币无限使用，求凑成amount的最少硬币数：

• 定义dp[c]为「凑成总金额c的最少硬币数量」，dp[0] = 0，其余初始化为float('inf')；
• 转移方程：dp[c] = min(dp[c], dp[c - coin] + 1)；
• 外层枚举硬币、内层正序枚举金额（完全背包允许重复取用，因此正序滚动数组即可复用本层结果）。

class Solution: def coinChange(self, coins: List[int], amount: int) -> int: dp = [float('inf')] * (amount + 1) dp[0] = 0 for coin in coins: # 枚举每种硬币 for c in range(coin, amount + 1): # 正序枚举金额（完全背包特征） dp[c] = min(dp[c], dp[c - coin] + 1) return dp[amount] if dp[amount] != float('inf') else -1

该题解同时给出了 BFS 视角（把amount减到0的最短步数问题）。仓库源码 Pack-CompletePack.py 完整实现了完全背包的二维基本版、状态转移优化版与滚动数组正序版三种写法，可对照理解「正序枚举」的来龙去脉；背包问题的系统性讲解可参考 08_06 ~ 08_10 背包问题系列。

3. 区间 DP：0312 戳气球

0312. 戳气球 是区间 DP 的代表题：在nums首尾补两个值为 1 的虚拟气球后，定义dp[i][j]为「戳破开区间(i, j)内所有气球的最大收益」，枚举区间内最后一个被戳破的气球k：

dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j]) (i < k < j)

按区间长度从小到大进行阶段划分，时间复杂度O(n³)，空间O(n²)。同区间的 0327. 区间和的个数、0363. 矩形区域不超过 K 的最大数值和 等则属于「区间统计 + 优化」方向。

4. 树形 DP：0337 打家劫舍 III

0337. 打家劫舍 III 将「打家劫舍」搬到二叉树上：对每个节点cur，递归（后序遍历）返回[选择该节点的最大值, 不选该节点的最大值]：

• 选：root.val + left[不选] + right[不选]；
• 不选：max(left[选], left[不选]) + max(right[选], right[不选])。

自底向上的树形 DP 是面试高频考点，其「每个节点维护两种状态」的套路与 0368. 最大整除子集、0377. 组合总和 Ⅳ、0376. 摆动序列 等一起构成了本章丰富的 DP 题型矩阵。

二、前缀和与区域检索系列：设计题与查询优化

本章有一个完整的「区域检索」子系列，是前缀和 / 线段树 / 树状数组的对比实验场：

• 0303. 区域和检索 - 数组不可变（简单）：朴素思路用前缀和O(1)查询；题解给出线段树实现——构建SegTreeNode数组（4 倍空间），query_interval区间查询，function参数决定聚合方式（求和用lambda x, y: x + y）。
• 0304. 二维区域和检索 - 矩阵不可变：二维前缀和，sumRegion用四块矩形加减容斥得到。
• 0307. 区域和检索 - 数组可修改 与 0308. 二维区域和检索 - 矩阵可修改：支持单点更新的动态区间和，解法切换为树状数组 / 线段树。
• 0370. 区间加法：差分数组的经典应用。

仓库对这几类数据结构的底层实现均有配套源码：tree_binaryindexed_tree.py（树状数组）、tree_segmentTree_update_point.py（点更新线段树）、tree_segmentTree_update_interval_1.py（区间更新线段树），对应理论章节为 05_05 线段树 01、05_06 线段树 02 与 05_07 树状数组。

三、高阶区间统计：0315 与 0327 的三种解法

0315. 计算右侧小于当前元素的个数 与 0327. 区间和的个数 是本章难度最高的区间统计题，每道都给出多套解法：

• 0315 思路 1：归并排序。把元素存为[值, 下标, 右侧小于它的个数]，归并时当left[left_i] ≤ right[right_i]，说明左元素右侧有right_i个更小元素，累加进计数；左半剩余元素同理。时间O(n log n)。
• 0315 思路 2：树状数组。先离散化到[0, len-1]排名区间，再逆序遍历：查询index - 1前缀和得到「已出现的更小元素个数」，随后在该位置update(index, 1)。

class BinaryIndexTree: def __init__(self, n): self.size = n self.tree = [0 for _ in range(n + 1)] def lowbit(self, index): return index & (-index) def update(self, index, delta): while index <= self.size: self.tree[index] += delta index += self.lowbit(index) def query(self, index): res = 0 while index > 0: res += self.tree[index] index -= self.lowbit(index) return res

• 0327 思路 1：前缀和 + 归并排序。令prefix[i]为前缀和，则问题转化为「对每个prefix[j]，统计此前有多少prefix落在[prefix[j] - upper, prefix[j] - lower]」，归并过程中用双指针i、j扫描左右半有序区间累计计数。
• 0327 思路 2：前缀和 + 树状数组。把p、p - lower、p - upper全部收集后离散化，从左到右遍历前缀和：区间查询[p - upper, p - lower]内已有元素个数，再插入当前p。

两道题的共同经验是：「右侧/区间内满足条件的元素个数」可以统一抽象为「逆序扫描 + 离散化 + 树状数组」或「归并过程中的有序性计数」，这正是算法面试中「区间统计四件套」的核心。

四、图论与并查集：0399 带权并查集领衔

1. 除法求值：并查集维护倍数关系

0399. 除法求值 在基础并查集之上维护一个multiples数组记录「节点到根节点的倍数关系」：

• find(x)：递推寻根时累乘倍数，并做路径压缩、更新当前节点倍数；
• union(x, y, multiple)：合并两个集合，更新根节点的倍数multiple * multiples[y] / multiples[x]；
• is_connected(x, y)：同一集合内返回multiples[x] / multiples[y]，否则返回-1.0。

class UnionFind: def __init__(self, n): self.parent = [i for i in range(n)] self.multiples = [1 for _ in range(n)] def find(self, x): multiple = 1.0 origin = x while x != self.parent[x]: multiple *= self.multiples[x] x = self.parent[x] self.parent[origin] = x self.multiples[origin] = multiple return x def union(self, x, y, multiple): root_x, root_y = self.find(x), self.find(y) if root_x == root_y: return self.parent[root_x] = root_y self.multiples[root_x] = multiple * self.multiples[y] / self.multiples[x] def is_connected(self, x, y): root_x, root_y = self.find(x), self.find(y) if root_x != root_y: return -1.0 return self.multiples[x] / self.multiples[y]

仓库基础并查集实现见 tree_unionFind_UnoinByRank.py（按秩合并 + 隔代压缩），理论讲解见 05_08 并查集；该目录下还有 QuickFind、QuickUnion、按大小合并 等多个变体源码可供对照。

2. 本章其他图论题目

• 0305. 岛屿数量 II：动态加点并查集，每次 union 成功后陆地连通块数量减一。
• 0310. 最小高度树：拓扑排序「逐层剥叶子」找树的中心。
• 0323. 无向图中连通分量的数目：并查集 / DFS 计数。
• 0332. 重新安排行程：欧拉路径（Hierholzer 算法）的经典应用。
• 0317. 离建筑物最近的距离：多源 BFS 累积距离。

仓库图论基础源码（邻接表、邻接矩阵、BFS、DFS、拓扑排序、最小生成树、最短路径等）位于 codes/python/06_graph/，对应理论章节为 06_01 ~ 06_12。其中 Graph-BFS.py 展示了基于队列 +visited集合的标准 BFS 骨架，与 0317 等多源 BFS 题的思路同源。

五、堆、优先队列与桶排序：0347 前 K 个高频元素

0347. 前 K 个高频元素 综合了哈希表 + 大顶堆：先用哈希表统计频数，再去重后基于二叉堆构建优先队列（堆顶为频数最高元素），连续出堆k次得到答案。题解甚至手写实现了heapAdjust/heapify/heappush/heappop全套大顶堆操作，是理解堆原理的绝佳素材。相关题目还有：

• 0373. 查找和最小的 K 对数字：多路归并，用小顶堆维护候选对。
• 0378. 有序矩阵中第 K 小的元素：堆 / 二分答案两种解法。

堆排序的完整实现可参考仓库 array_sort_maxheap_sort.py 与 array_maxheap.py，理论章节见 01_09 堆排序。

六、数据结构设计专题：O(1) 操作的艺术

300~399 区间集中了十余道「设计」类题目，考察用多个基础数据结构组合出特定复杂度：

• 0380. O(1) 时间插入、删除和获取随机元素：数组 + 哈希表。哈希表记录元素下标，删除时把待删元素与数组末尾元素交换再 pop，保证insert / remove / getRandom全部O(1)。

class RandomizedSet: def __init__(self): self.dict = dict() self.list = list() def insert(self, val: int) -> bool: if val in self.dict: return False self.dict[val] = len(self.list) self.list.append(val) return True def remove(self, val: int) -> bool: if val in self.dict: idx = self.dict[val] last = self.list[-1] self.list[idx] = last # 与末尾元素交换 self.dict[last] = idx self.list.pop() self.dict.pop(val) return True return False def getRandom(self) -> int: return random.choice(self.list)

• 同类题：0381. 允许重复的版本（哈希表存下标集合）、0346. 数据流中的移动平均值（队列 + 窗口和）、0352. 数据流变为不相交区间、0353. 贪吃蛇、0355. 设计推特（推文时间线合并）、0359. 日志速率限制器、0362. 敲击计数器（滑动窗口计数）、0379. 电话目录、0382. 链表随机节点（蓄水池抽样）、0384. 打乱数组（Fisher–Yates 洗牌）、0398. 随机数索引（蓄水池抽样）。

七、栈与字符串专题

• 0394. 字符串解码（中等）：双栈解法——stack1保存左括号前已解码字符串，stack2保存重复次数，遇到]时弹出并拼合。时间、空间均为O(n)。

class Solution: def decodeString(self, s: str) -> str: stack1, stack2 = [], [] num, res = 0, "" for ch in s: if ch.isdigit(): num = num * 10 + int(ch) elif ch == '[': stack1.append(res) stack2.append(num) res, num = "", 0 elif ch == ']': cur_res, cur_num = stack1.pop(), stack2.pop() res = cur_res + res * cur_num else: res += ch return res

• 0316. 去除重复字母：单调栈 + 频数剪枝，保证字典序最小。
• 0331. 验证二叉树的前序序列化：用「槽位」计数或栈验证前序序列化合法性。
• 0340. 至多包含 K 个不同字符的最长子串、0395. 至少有 K 个重复字符的最长子串：滑动窗口 + 计数。
• 字符串基础与匹配算法可回溯到 04 字符串章节 和仓库 codes/python/04_string/。

八、树遍历与链表操作

• 0314. 二叉树的垂直遍历：BFS + 哈希表，为根节点分配列坐标 0（左子 -1、右子 +1），按列坐标分组输出；BFS 保证同列内从上到下、同层从左到右。
• 0366. 寻找二叉树的叶子节点：后序遍历按「高度/深度」分组收集叶子。
• 0333. 最大二叉搜索子树：后序遍历向上传递子树 BST 信息。
• 0328. 奇偶链表：odd、even双指针拆分两条链再首尾相接，空间O(1)、时间O(n)。
• 0369. 给单链表加一：链表反转后从低位进位。
• 树与链表的基础实现见 05 树结构章节 与 02 链表章节。

九、位运算与贪心算法

• 0371. 两整数之和：不用+/-求和。a ^ b得到无进位和，(a & b) << 1得到进位，循环直到进位为 0；注意 Python 无限长整数的处理：用a &= 0xFFFFFFFF截断为 32 位无符号整数，最后按MAX_INT = 0x7FFFFFFF判断映射回有符号结果。
• 0330. 按要求补齐数组（困难）：贪心维护miss表示当前可覆盖连续区间[1, miss)，当nums[i] ≤ miss时扩展miss += nums[i]，否则补充miss并miss += miss，这是「用最小的补充代价最大化覆盖区间」的经典贪心。
• 0392. 判断子序列：双指针贪心。
• 0358. K 距离间隔重排字符串：贪心 + 优先队列/桶。
• 位运算基础可参考 07_06 位运算 与仓库 07 基础算法章节。

十、完整题解索引：LeetCode 300~399 题（100 道）

以下为本章全部 100 道题解，均位于docs/solutions/0300-0399/目录，点击题号即可进入对应解析：

如何高效使用本章

1. 按算法专题批量刷：把本章与全书「基础讲解」章节一一对应，先学理论再刷题效果最佳——动态规划对应 08 动态规划章节，并查集对应 05_08，树状数组/线段树对应 05_05 ~ 05_07，图论对应 06 图章节。
2. 先独立思考，再对照题解：每篇题解都包含「题目大意、数据范围、示例、多思路讲解、完整 Python 代码、复杂度分析」，建议先尝试写出代码，再对照 0300-0399 目录 中对应题解验证思路。
3. 结合仓库源码深挖原理：当题解中出现树状数组、线段树、并查集、背包等数据结构时，可同步阅读 codes/python/05_tree/ 与 codes/python/08_dynamic_programming/ 下的独立实现，理解每个方法（如lowbit、update、query、union、find）的底层细节，做到「知其然更知其所以然」。
4. 由本章延伸到后续章节：300~399 的题目风格在 400~599 区间（如 0400~0499、0500~0599）中继续深化，本章打下的 DP、区间统计、数据结构设计基础可直接复用。

结语

LeetCode 300~399 题区间是 AlgoNote 题目解析体系中极具代表性的 100 道：既有「最长递增子序列」「零钱兑换」「戳气球」这样的 DP 基石，也有「计算右侧小于当前元素的个数」「除法求值」这类融合树状数组与带权并查集的高阶题目，还集中了「O(1) 随机集合」「设计推特」等数据结构设计实战。结合本文的专题导读与完整索引，读者可以按图索骥、逐题攻克，在算法面试中真正做到心中有数。

• 教程
• 文档
• 知识库