算法

Hailin

Dijkstra 堆优化版

给定一个有向带权图，求从起点到所有其他节点的最短路径长度。图中可能存在重边和自环，边权为正数。 Dijkstra 算法适用于所有边权非负的图。堆优化版本通过优先队列（最小堆）快速取出当前距离最小的未确定节点，在简单图的常见分析中，时间复杂度可写为 O((V + E)log V)；允许任意重边时，应使用下文针对惰性堆的界。 维护一个距离数组 dist，初始时起点距离为 0，其余为无穷大。用最小堆存储 (距离, 节点)，每次取出堆顶距离最小的节点，如果该距离已经大于 dist[u] 则跳过（惰性删除），否则遍历其所有邻边尝试松弛。 松弛成功时将新距离入堆。重复此过程直到堆为空。 dist 数组：记录起点到每个节点的当前最短距离，初始化为无穷大。 优先队列 pq：以 (距离, 节点) 形式存储，Python 的 heapq 默认按第一个元素排序。 惰性删除：if d > dist[u]: continue 用于跳过已经过期的堆元素。节点可能被多次入堆，但只有距离最小的那次才有效。 松弛操作：如果通过 u 到达 v 的距离 d + w 比当前记录 dist[v] 更短，则更新并重新入堆。 时间复杂度：O(V + E log(E+2))。每条边最多触发一次成功松弛，但同一节点可以多次入堆；惰性堆最多保留 O(E) 条记录。在简单图下，也常写为 O((V+E)log V)。 空间复杂度：O(V+E)。距离数组为 O(V)，堆最坏为 O(E)；若计入邻接表，整体仍为 O(V+E)。

算法

Hailin

KMP 算法

给定一个文本串 s 和一个模式串 p，在 s 中查找 p 第一次出现的位置。如果不存在则返回 -1。 暴力匹配的时间复杂度为 O(m × n)，而 KMP 算法通过预处理模式串的"前后缀信息"，将匹配过程优化到 O(m + n)，核心思想是匹配失败时利用已知信息跳过不必要的比较。 KMP 算法的关键在于 next 数组（也称前缀函数）。它记录了模式串截至当前位置的子串的最长相等真前后缀长度；“真”表示不包含整个子串本身。当匹配失败时，模式串指针不回溯到开头，而是跳转到 next 数组指示的位置，从而避免重复匹配。 构建 next 数组：遍历模式串，用双指针计算每个位置的最长相等前后缀长度。前缀指针 j 始终指向当前已匹配前缀的下一个位置，当字符匹配时 j 前移，不匹配时 j 回退到 nxt[j-1]。 匹配过程：遍历文本串，同样用双指针。字符匹配时模式串指针前移，不匹配时利用 next 数组回退。当模式串指针走到末尾，说明匹配成功。 build_next：用模式串自己匹配自己的方式构建 next 数组。nxt[i] 记录 patt[:i+1] 的最长相等前后缀长度，i 从 1 开始，因为单个字符的前后缀长度为 0。 匹配回退：当 s[i] != p[j] 时，j = nxt[j - 1] 是关键一步。它利用已匹配部分的前后缀信息，将模式串向右滑动到合适位置，避免从头开始。 时间复杂度：构建 next 数组和匹配过程都是线性扫描，指针前进次数为线性量级，而每次回退都会减小已匹配长度，总回退次数不超过此前累积的前进次数；不能理解成每个字符单独最多比较两次。 时间复杂度：O(m + n)，其中 m 为模式串长度，n 为文本串长度。构建 next 数组 O(m)，匹配过程 O(n)。 空间复杂度：O(m)，需要存储 next 数组。

算法

Hailin

力扣 2115 从给定原材料中找到所有可以做出的菜

给定一个字符串数组 recipes（食谱）、一个二维字符串数组 ingredients（每个食谱所需的食材列表）以及一个字符串数组 supplies（当前拥有的所有食材）。每道菜做好后也可以作为其他菜的食材。返回所有可以做出的食谱列表。 本题的核心在于处理食谱与食材之间的依赖关系。一道菜依赖若干种食材，而做好的菜又可以作为其他菜的食材，这种"前置条件满足后才能解锁"的特性决定了可以使用拓扑排序来解决。 将每种食材和食谱都看作图上的节点，从食材向需要它的食谱连有向边，同时记录每个食谱的入度（即所需食材的种类数）。初始时，所有 supplies 中的食材都是可用的，将它们作为 BFS 的起点。每当一个食谱的所有前置食材都备齐（入度减为 0），该食谱便可被做出，并作为新的可用节点去解锁更多食谱。 建图与初始化入度：遍历每个食谱，将其每种食材与食谱建立有向边，并记录每个食谱的入度。 BFS 拓扑遍历：将已有食材入队，依次出队并减少依赖它的食谱的入度，当某个食谱入度为 0 时将其入队并加入答案。 返回结果：所有能做出的食谱即为答案。 邻接表 g：以食材/食谱为键，值为依赖该食材的食谱列表，实现了从食材到食谱的快速查找。 入度表 deg：记录每个食谱当前尚未满足的食材种类数，初始值为食谱所需的食材总数。 队列 q：存储当前可用的所有资源（包括初始原料和已做出的菜），是整个拓扑排序的驱动核心。 BFS 过程：每次从队列中取出一个可用资源，将其所有出边的目标节点（食谱）的入度减 1，当入度归零时意味着该食谱可以做出。 时间复杂度：O(N+M+S)，N 为食谱数，M 为食材依赖总数，S 为初始原料数。建图遍历依赖，队列初始化和处理还需计入 S。 空间复杂度：O(N+M+S)，计入邻接表、入度表以及最多 O(N+S) 个可用资源的队列。这里沿用题目中初始原料名称互异、每份食谱的食材不重复且非空的约束。

算法

Hailin

力扣 210. 课程表 II

现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites，其中 prerequisites[i] = [ai, bi]，表示在选修课程 ai 前必须先选修 bi。 请你返回一个可以修完所有课程的学习顺序。如果不可能完成所有课程（即存在环），返回一个空数组。 本题是经典的拓扑排序问题。课程之间的先修关系构成一个有向图，需要找到一个拓扑序，使得对于每条有向边 bi -> ai，bi 在拓扑序中出现在 ai 之前。 建图：使用邻接表 g 存储有向图，g[y] 表示所有以 y 为先修课的课程列表。 统计入度：in_edge[x] 记录课程 x 的入度（即有多少门先修课）。 初始化队列：将所有入度为 0 的课程（即没有先修课的课程）加入队列。 BFS 遍历： 从队列中取出一个课程 x，将其加入结果集。 遍历 x 的所有后继课程 y，将其入度减 1。 若 y 的入度变为 0，说明其所有先修课都已修完，将 y 加入队列。 判断是否有解：如果结果集中的课程数等于 numCourses，说明所有课程都可以修完；否则存在环，返回空数组。 时间复杂度：O(V + E)，其中 V 为课程数 numCourses，E 为先修关系数。建图和 BFS 遍历每条边和每个节点各一次。 空间复杂度：O(V + E)，邻接表存储图需要 O(E) 空间，队列和入度数组需要 O(V) 空间。

算法

Hailin

力扣 1391. 检查网格中是否存在有效路径

本题要求判断能否从网格左上角 (0, 0) 走到右下角 (m-1, n-1)，其中每个格子代表一种街道类型（1~6），每种街道只允许特定方向通行。 核心思想是使用 BFS（广度优先搜索） 遍历所有可达位置，并在移动时验证 双向连通性：即当前格子允许通往下一格，且下一格也允许从当前格进入。 关键点 街道建模：将6种街道抽象为方向对，便于程序处理。 双向验证：仅当两个相邻格子互相“认可”对方方向时，才视为可通行。 BFS遍历：保证按层扩展，最终判断终点是否可达。 复杂度 时间复杂度：O(m × n)，每个格子最多入队一次。 空间复杂度：O(m × n)，用于 vis 数组和队列。