左神学习笔记2

2026.01.25开始学习

2026.01.25 11:24

算法讲解049【必备】滑动窗口技巧与相关题目

前置知识 : 无

滑动窗口：维持左、右边界都不回退的一段范围，来求解很多子数组（串）的相关问题

滑动窗口的关键：找到和之间的单调性关系（类似贪心）

滑动过程：滑动窗口可以用或者来维护信息

求解大流程：求子数组在或情况下的答案（开头还是结尾在于个人习惯）

注意：滑动窗口维持最大值或者最小值的，在【必备】课程【单调队列】视频里讲述


题目1
累加和大于等于target的最短子数组长度
给定一个含有 n 个正整数的数组和一个正整数 target
找到累加和 >= target 的长度最小的子数组并返回其长度
如果不存在符合条件的子数组返回0
测试链接 : https://leetcode.cn/problems/minimum-size-subarray-sum/


题目2
无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
测试链接 : 
https://leetcode.cn/problems/longest-substring-without-repeating-characters/

https://www.nowcoder.com/practice/59b4ff4167e245c199922880c2733488


题目3
最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串
如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
测试链接 : https://leetcode.cn/problems/minimum-window-substring/

https://www.nowcoder.com/practice/c466d480d20c4c7c9d322d12ca7955ac


题目4
加油站
在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，
从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升
你从其中的一个加油站出发，开始时油箱为空。
给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周
则返回出发时加油站的编号，否则返回 -1
如果存在解，则 保证 它是 唯一 的。
测试链接 : https://leetcode.cn/problems/gas-station/

题目5
替换子串得到平衡字符串
有一个只含有'Q','W','E','R'四种字符，且长度为n的字符串，n一定为4的整数倍
假如在该字符串中，这四个字符都恰好出现 n/4 次，那么它就是一个「平衡字符串」
给你一个这样的字符串s，请通过「替换一个子串」的方式，
使原字符串s变成一个「平衡字符串」
子串可以替换成由'Q','W','E','R'四种字符组成的任何样子
请返回待替换子串的最小可能长度
如果原字符串自身就是一个平衡字符串，则返回0
测试链接 : https://leetcode.cn/problems/replace-the-substring-for-balanced-string/

题目6
K个不同整数的子数组
给定一个正整数数组 nums和一个整数 k，返回 nums 中 「好子数组」 的数目。
如果 nums 的某个子数组中不同整数的个数恰好为 k
则称 nums 的这个连续、不一定不同的子数组为 「好子数组 」。
例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。
子数组 是数组的 连续 部分。
测试链接 : https://leetcode.cn/problems/subarrays-with-k-different-integers/

题目7
至少有K个重复字符的最长子串
给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串
要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度
如果不存在这样的子字符串，则返回 0。
测试链接 : https://leetcode.cn/problems/longest-substring-with-at-least-k-repeating-characters/
牛客：https://www.nowcoder.com/practice/5aabbcfc45e2443ab7b8c9988bca6616

2026.02.01 22:45

算法讲解050【必备】双指针技巧与相关题目

前置知识 : 无

设置两个指针的技巧，其实这种说法很宽泛，似乎没什么可总结的

1）有时候所谓的双指针技巧，就单纯是代码过程用双指针的形式表达出来而已。没有单调性（贪心）方面的考虑

2）有时候的双指针技巧包含的考虑，牵扯到可能性的取舍。对分析能力的要求会变高。其实是，然后代码变成了。

3）所以，双指针这个“皮”不重要，，这个能力才重要。

常见的双指针类型：

1）同向双指针

2）快慢双指针

3）从两头往中间的双指针

4）其他

题目1
按奇偶排序数组II
给定一个非负整数数组 nums。nums 中一半整数是奇数 ，一半整数是偶数
对数组进行排序，以便当 nums[i] 为奇数时，i也是奇数
当 nums[i] 为偶数时， i 也是 偶数
你可以返回 任何满足上述条件的数组作为答案
测试链接 : https://leetcode.cn/problems/sort-array-by-parity-ii/

牛客：
https://www.nowcoder.com/practice/8dad38b5d6514a51b543b0d9f1bfd88e

不同的说法，同一个题：
给定一个数组arr，请把arr调整成 奇数都在奇数位置 或者 偶数都在偶数位置


题目2
寻找重复数
给定一个包含 n + 1 个整数的数组 nums ，
其数字都在 [1, n] 范围内（包括 1 和 n）
可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。
你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
测试链接 : https://leetcode.cn/problems/find-the-duplicate-number/


题目3
接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，
计算按此排列的柱子，下雨之后能接多少雨水
测试链接 : https://leetcode.cn/problems/trapping-rain-water/
牛客题霸：https://www.nowcoder.com/practice/31c1aed01b394f0b8b7734de0324e00f

注意：二维接雨水问题，会在宽度优先遍历的章节讲述，后续的【必备】课程


题目4
救生艇
给定数组 people
people[i]表示第 i 个人的体重 ，船的数量不限
每艘船可以承载的最大重量为 limit
每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit
返回 承载所有人所需的最小船数
测试链接 : https://leetcode.cn/problems/boats-to-save-people/

扩展：
再增加一个要求，如果两人一船那么体重之和必须是偶数，又该怎么做？（大厂真考过）


题目5
盛最多水的容器
给定一个长度为 n 的整数数组 height
有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i])
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水
返回容器可以储存的最大水量
说明：你不能倾斜容器
测试链接 : https://leetcode.cn/problems/container-with-most-water/
牛客题霸：https://www.nowcoder.com/practice/3d8d6a8e516e4633a2244d2934e5aa47
洛谷：
https://www.luogu.com.cn/problem/U598692
https://www.luogu.com.cn/problem/U653319

题目6
供暖器
冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。
在加热器的加热半径范围内的每个房屋都可以获得供暖。
现在，给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置
请你找出并返回可以覆盖所有房屋的最小加热半径。
说明：所有供暖器都遵循你的半径标准，加热的半径也一样。
测试链接 : https://leetcode.cn/problems/heaters/


题目7
缺失的第一个正数
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
测试链接 : https://leetcode.cn/problems/first-missing-positive/
牛客题霸：https://www.nowcoder.com/practice/50ec6a5b0e4e45348544348278cdcee5

洛谷：
https://www.luogu.com.cn/problem/U266316

玩概念了！

2026.02.03 22:34

尚同

2026.02.04 16:36

算法讲解051【必备】二分答案法与相关题目

前置知识 : 讲解005-对数器、讲解006-基本二分搜索、讲解042-进一步了解对数器

二分答案法

1）估计是什么，可以定的粗略，反正二分不了几次

2）分析和之间的，大部分时候只需要用到

3）建立一个f函数，，判断

4）在，每次用f函数判断，直到二分结束，

核心点：分析单调性、建立f函数

注意：这个技巧常用且重要，一定要引起重视，非常的美、精妙！以后的课还会经常见到

题目1 爱吃香蕉的珂珂

珂珂喜欢吃香蕉。这里有 n 堆香蕉，第 i 堆中有 piles[i] 根香蕉警卫已经离开了，将在 h 小时后回来。珂珂可以决定她吃香蕉的速度 k （单位：根/小时）每个小时，她将会选择一堆香蕉，从中吃掉 k 根如果这堆香蕉少于 k 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。返回她可以在 h 小时内吃掉所有香蕉的最小速度 k（k 为整数）

测试链接 : https://leetcode.cn/problems/koko-eating-bananas/

牛客：https://www.nowcoder.com/practice/1f45caaa90814b89b35c5c7e1974c51b

c++实现：

c++

#include <iostream>
#include <string>
using namespace std;
const int N = 1e4 + 5;
int nums[N];
int len, h;
bool check(int mid) {
  int t = 0;
  for (int i = 0; i < len; i++) { t += (nums[i] + mid - 1) / mid; }
  return t <= h;
}
void solve() {
  int l = 1, r = 0;
  for (int i = 0; i < len; i++) { r = nums[i] > r ? nums[i] : r; }
  while (l < r) {
    int mid = l + ((r - l) >> 1);
    if (check(mid)) {
      r = mid;
    } else {
      l = mid + 1;
    }
  }
  printf("%d", l);
}
int main() {
  string s, temp;
  len = 0;
  getline(cin, s);
  int i, j;
  for (i = 1, j = 1; s[j] != ';'; j++) {
    if (s[j] == ',' || s[j] == ']') {
      temp = s.substr(i, j - i);
      nums[len++] = stoi(temp);
      i = j + 1;
    }
  }
  temp = s.substr(j + 1);
  h = stoi(temp);
  solve();
  return 0;
}



题目2
分割数组的最大值(画匠问题)
给定一个非负整数数组 nums 和一个整数 m
你需要将这个数组分成 m 个非空的连续子数组。
设计一个算法使得这 m 个子数组各自和的最大值最小。
测试链接 : https://leetcode.cn/problems/split-array-largest-sum/
牛客：
https://www.nowcoder.com/practice/767778ca5b38446cba801820df11399d

题目3
机器人跳跃问题
机器人正在玩一个古老的基于DOS的游戏，游戏中有N+1座建筑，从0到N编号，从左到右排列
编号为0的建筑高度为0个单位，编号为i的建筑的高度为H(i)个单位
起初， 机器人在编号为0的建筑处
每一步，它跳到下一个（右边）建筑。假设机器人在第k个建筑，且它现在的能量值是E
下一步它将跳到第个k+1建筑
它将会得到或者失去正比于与H(k+1)与E之差的能量
如果 H(k+1) > E 那么机器人就失去H(k+1)-E的能量值
否则它将得到E-H(k+1)的能量值
游戏目标是到达第个N建筑，在这个过程中，能量值不能为负数个单位
现在的问题是机器人以多少能量值开始游戏，才可以保证成功完成游戏
测试链接 : https://www.nowcoder.com/practice/7037a3d57bbd4336856b8e16a9cafd71
leetcode:
https://leetcode.cn/problems/yBGFyZ/

题目4
找出第K小的数对距离
数对 (a,b) 由整数 a 和 b 组成，其数对距离定义为 a 和 b 的绝对差值。
给你一个整数数组 nums 和一个整数 k
数对由 nums[i] 和 nums[j] 组成且满足 0 <= i < j < nums.length
返回 所有数对距离中 第 k 小的数对距离。
测试链接 : https://leetcode.cn/problems/find-k-th-smallest-pair-distance/

牛客：
https://www.nowcoder.com/practice/26849d7e31dd443c895a6921d67fa273

https://ac.nowcoder.com/acm/problem/235827

洛谷：
https://www.luogu.com.cn/problem/U455662


题目5
同时运行N台电脑的最长时间
你有 n 台电脑。给你整数 n 和一个下标从 0 开始的整数数组 batteries
其中第 i 个电池可以让一台电脑 运行 batteries[i] 分钟
你想使用这些电池让 全部 n 台电脑 同时 运行。
一开始，你可以给每台电脑连接 至多一个电池
然后在任意整数时刻，你都可以将一台电脑与它的电池断开连接，
并连接另一个电池，你可以进行这个操作 任意次
新连接的电池可以是一个全新的电池，也可以是别的电脑用过的电池
断开连接和连接新的电池不会花费任何时间。注意，你不能给电池充电。
请你返回你可以让 n 台电脑同时运行的 最长 分钟数。
测试链接 : https://leetcode.cn/problems/maximum-running-time-of-n-computers/

开始玩概念了：“碎片拼接”！很秒！难想！


题目6
计算等位时间
给定一个数组arr长度为n，表示n个服务员，每服务一个客人的时间
给定一个正数m，表示有m个人等位，如果你是刚来的人，每个客人都遵循有空位就上的原则
请问你需要等多久？
假设m远远大于n，比如n <= 10^3, m <= 10^9，该怎么做是最优解？
谷歌的面试，这个题连考了2个月

题目7
刀砍毒杀怪兽问题
怪兽的初始血量是一个整数hp，给出每一回合刀砍和毒杀的数值cuts和poisons
第i回合如果用刀砍，怪兽在这回合会直接损失cuts[i]的血，不再有后续效果
第i回合如果用毒杀，怪兽在这回合不会损失血量，但是之后每回合都损失poisons[i]的血量
并且你选择的所有毒杀效果，在之后的回合会叠加
两个数组cuts、poisons，长度都是n，代表你一共可以进行n回合
每一回合你只能选择刀砍或者毒杀中的一个动作
如果你在n个回合内没有直接杀死怪兽，意味着你已经无法有新的行动了
但是怪兽如果有中毒效果的话，那么怪兽依然会不停扣血，直到血量耗尽的那回合死掉
返回至少多少回合怪兽会死掉
数据范围 : 1<=n<=10^5；1<=hp<=10^9；1<=cuts[i]、poisons[i]<=10^9
真实大厂算法笔试题

2026.02.11 15:54

尚同

2026.02.16 20:52

算法讲解052【必备】单调栈-上

前置知识 : 讲解013-用数组方式实现栈(常数时间比语言自己提供的好)

单调栈最经典的用法是解决如下问题：每个位置都求： 0）当前位置的左侧比当前位置的数字小，且距离最近的位置在哪 1）当前位置的右侧比当前位置的数字小，且距离最近的位置在哪或者每个位置都求： 0）当前位置的左侧比当前位置的数字大，且距离最近的位置在哪 1）当前位置的右侧比当前位置的数字大，且距离最近的位置在哪

用单调栈的方式可以做到：求解过程中，单调栈所有调整的总代价为O(n)，单次操作的均摊代价为O(1)

注意：这是单调栈最经典的用法，可以解决很多题目，下节课将继续介绍其他的用法注意：单调栈可以和很多技巧交叉使用！比如：动态规划+单调栈优化，会在【扩展】课程里讲述

题目1
单调栈最经典用法的模版
测试链接 : https://www.nowcoder.com/practice/2a2c00e7a88a498693568cef63a4b7bb


题目2
每日温度
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer
其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后
如果气温在这之后都不会升高，请在该位置用 0 来代替。
测试链接 : https://leetcode.cn/problems/daily-temperatures/

题目3
子数组的最小值之和
给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。
由于答案可能很大，因此 返回答案模 10^9 + 7
测试链接 : https://leetcode.cn/problems/sum-of-subarray-minimums/

注意这道题答案很大，要求取模
对取模不熟悉的同学可以看一下：讲解041-同余原理的部分，讲了为什么要取模以及怎么取模


题目4
柱状图中最大的矩形
给定 n 个非负整数，用来表示柱状图中各个柱子的高度
每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积
测试链接：https://leetcode.cn/problems/largest-rectangle-in-histogram
牛客题霸：https://www.nowcoder.com/practice/b0fbb688d01a4f2c8c17e5efd85d5824

题目5
最大矩形
给定一个仅包含 0 和 1 、大小为 rows * cols 的二维二进制矩阵
找出只包含 1 的最大矩形，并返回其面积
测试链接：https://leetcode.cn/problems/maximal-rectangle/
牛客题霸：https://www.nowcoder.com/practice/5720efc1bdff4ca3a7dad37ca012cb60

2026.02.17 22:57

尚同

2026.02.27 17:35

单调栈-下

前置知识 : 讲解052-单调栈-上

除了单调栈最经典的用法之外，在很多问题里单调栈还可以

1）单调栈里的所有对象按照

2）当某个对象进入单调栈时，会从依次淘汰单调栈里的对象

3）每个对象从栈顶弹出的时，随后这个对象不再参与后续求解答案的过程

4）其实是进而发现单调性，然后利用去实现

注意：单调栈可以和很多技巧交叉使用！比如：动态规划+单调栈优化，会在【扩展】课程里讲述

题目1
最大宽度坡
给定一个整数数组 A，坡是元组 (i, j)，其中  i < j 且 A[i] <= A[j]
这样的坡的宽度为 j - i，找出 A 中的坡的最大宽度，如果不存在，返回 0
测试链接 : https://leetcode.cn/problems/maximum-width-ramp/


题目2
去除重复字母保证剩余字符串的字典序最小
给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次
需保证 返回结果的字典序最小
要求不能打乱其他字符的相对位置
测试链接 : https://leetcode.cn/problems/remove-duplicate-letters/


题目3
大鱼吃小鱼问题
给定一个数组arr，每个值代表鱼的体重
每一轮，每条鱼都会吃掉右边离自己最近比自己体重小的鱼，每条鱼向右找只吃一条
但是吃鱼这件事是同时发生的，也就是同一轮在A吃掉B的同时，A也可能被别的鱼吃掉
如果有多条鱼在当前轮找到的是同一条小鱼，那么在这一轮，这条小鱼同时被这些大鱼吃
请问多少轮后，鱼的数量就固定了
比如 : 8 3 1 5 6 7 2 4
第一轮 : 8吃3；3吃1；5、6、7吃2；4没有被吃。数组剩下 8 5 6 7 4
第二轮 : 8吃5；5、6、7吃4。数组剩下 8 6 7
第三轮 : 8吃6。数组剩下 8 7
第四轮 : 8吃7。数组剩下 8
过程结束，返回4
测试链接 : https://www.nowcoder.com/practice/77199defc4b74b24b8ebf6244e1793de


题目4
统计全1子矩形的数量
给你一个 m * n 的矩阵 mat，其中只有0和1两种值
请你返回有多少个 子矩形 的元素全部都是1
测试链接 : https://leetcode.cn/problems/count-submatrices-with-all-ones/

注意：讲解052-单调栈-上，里面的“柱状图中最大的矩形”+“全是1的最大矩形”问题要先理解

2026.03.02 22:38

尚同

NOTE

已知一个数组，

一个数 x，寻找 x 的左边和右边的第一个比 x 小的数的位置，

使用的单调栈自栈底到栈顶的数是从小到大的单调递增栈

左边第一个比它小的数的位置为 a，右边第一个比它小的数的位置为 b，

那么 (a, b) 之间的数都比 x 大，x 就是 (a, b) 之间的数的最小值

同样的，已知一个数组，一个数 x，寻找 x 的左边和右边的第一个比 x 小的数的位置，

使用的单调栈自栈底到栈顶的数是从大到小的单调递减栈

左边第一个比它大的数的位置为 a，右边第一个比它大的数的位置为 b，

那么 (a, b) 之间的数都比 x 小，x 就是 (a, b) 之间的数的最大值

单调栈逻辑模板

NOTE

场景：确定元素 $x$ 能作为最值覆盖的最大范围。

Case 1: 求最小值范围

维护一个单调递增栈 （自栈底到栈顶的数是从小到大的单调递增栈）。
弹出栈顶时，当前元素即为栈顶元素右侧第一个更小的值。
栈中下一个元素即为栈顶元素左侧第一个更小的值。
结果：栈顶元素是 (left_bound, right_bound) 区间内的最小值。

Case 2: 求最大值范围

维护一个单调递减栈（自栈底到栈顶的数是从大到小的单调递减栈）。
弹出栈顶时，当前元素即为栈顶元素右侧第一个更大的值。
栈中下一个元素即为栈顶元素左侧第一个更大的值。
结果：栈顶元素是 (left_bound, right_bound) 区间内的最大值。

2026.03.19 19:27

算法讲解054【必备】单调队列-上

前置知识 :

讲解013-用数组方式实现队列(常数时间比语言自己提供的好)

讲解049-滑动窗口

单调队列最经典的用法是解决如下问题：

滑动窗口在滑动时，r++代表右侧数字进窗口，l++代表左侧数字出窗口

这个过程中，想随时得到当前滑动窗口的

窗口滑动的过程中，

图解一下！

注意：这是单调队列最经典的用法，可以解决很多题目，下节课将继续介绍其他的用法

注意：单调队列可以和很多技巧交叉使用！比如：动态规划+单调队列优化，会在【扩展】课程里讲述



题目1
滑动窗口最大值（单调队列经典用法模版）
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧
你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
测试链接 : https://leetcode.cn/problems/sliding-window-maximum/

题目2
绝对差不超过限制的最长连续子数组
给你一个整数数组 nums ，和一个表示限制的整数 limit
请你返回最长连续子数组的长度
该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit
如果不存在满足条件的子数组，则返回 0
测试链接 : https://leetcode.cn/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/


题目3
接取落水的最小花盆
老板需要你帮忙浇花。给出 N 滴水的坐标，y 表示水滴的高度，x 表示它下落到 x 轴的位置
每滴水以每秒1个单位长度的速度下落。你需要把花盆放在 x 轴上的某个位置
使得从被花盆接着的第 1 滴水开始，到被花盆接着的最后 1 滴水结束，之间的时间差至少为 D
我们认为，只要水滴落到 x 轴上，与花盆的边沿对齐，就认为被接住
给出 N 滴水的坐标和 D 的大小，请算出最小的花盆的宽度 W
测试链接 : https://www.luogu.com.cn/problem/P2698

2026.3.23 20:30

算法讲解055【必备】单调队列-下

前置知识 : 讲解054-单调队列-上

除了单调队列最经典的用法之外，在很多问题里单调队列还可以维持求解答案的可能性

1）单调队列里的所有对象按照规定好的单调性来组织

2）当某个对象从队尾进入单调队列时，会从队头或者队尾依次淘汰单调队列里，对后续求解答案没有帮助的对象

3）每个对象一旦从单调队列弹出，可以结算此时这个对象参与的答案，随后这个对象不再参与后续求解答案的过程

4）其实是先有对题目的分析！进而发现单调性，然后利用单调队列的特征去实现

注意：

单调队列可以和很多技巧交叉使用！

比如：动态规划+单调队列优化，会在【扩展】课程里讲述

题目1
和至少为K的最短子数组
给定一个数组arr，其中的值有可能正、负、0
给定一个正数k
返回累加和>=k的所有子数组中，最短的子数组长度
测试链接 : https://leetcode.cn/problems/shortest-subarray-with-sum-at-least-k/

注意：本题用到构建前缀和的技巧，不熟悉的同学可以去看，讲解046-构建前缀信息的技巧



题目2
满足不等式的最大值
给你一个数组 points 和一个整数 k
数组中每个元素都表示二维平面上的点的坐标，并按照横坐标 x 的值从小到大排序
也就是说 points[i] = [xi, yi]
并且在 1 <= i < j <= points.length 的前提下，xi < xj 总成立
请你找出 yi + yj + |xi - xj| 的 最大值，
其中 |xi - xj| <= k 且 1 <= i < j <= points.length
题目测试数据保证至少存在一对能够满足 |xi - xj| <= k 的点。
测试链接 : https://leetcode.cn/problems/max-value-of-equation/




题目3
你可以安排的最多任务数目
给你 n 个任务和 m 个工人。每个任务需要一定的力量值才能完成
需要的力量值保存在下标从 0 开始的整数数组 tasks 中，
第i个任务需要 tasks[i] 的力量才能完成
每个工人的力量值保存在下标从 0 开始的整数数组workers中，
第j个工人的力量值为 workers[j]
每个工人只能完成一个任务，且力量值需要大于等于该任务的力量要求值，即workers[j]>=tasks[i]
除此以外，你还有 pills 个神奇药丸，可以给 一个工人的力量值 增加 strength
你可以决定给哪些工人使用药丸，但每个工人 最多 只能使用 一片 药丸
给你下标从 0 开始的整数数组tasks 和 workers 以及两个整数 pills 和 strength
请你返回 最多 有多少个任务可以被完成。
测试链接 : https://leetcode.cn/problems/maximum-number-of-tasks-you-can-assign/

注意：本题大思路用到二分答案法，不熟悉的同学可以去看，讲解051-二分答案法

2026.03.24 18:38

尚同

2026.03.26 17:10

算法讲解056【必备】并查集-上

前置知识 : 无

并查集的使用是如下的场景

1）一开始每个元素都拥有自己的集合，在自己的集合里只有这个元素自己

2）int find(i)：查找i所在集合的代表元素，代表元素来代表i所在的集合

3）boolean isSameSet(a, b)：判断a和b在不在一个集合里

4）void union(a, b)：a所在集合所有元素与 b所在集合所有元素合并成一个集合

5）各种操作单次调用的均摊时间复杂度为O(1)

并查集原理图解

注意：带权并查集、可持久化并查集、可撤销并查集，都是备战算法竞赛的同学必学的内容这些内容会在【挺难】阶段的课程里安排讲述

优化

并查集的两个优化，都发生在find方法里

1）扁平化（一定要做）
2）小挂大（可以不做，原论文中是秩的概念，可以理解为粗略高度或者大小）

并查集的小扩展（下节课的题目重点展示）

可以定制信息：并查集目前有多少个集合，以及给每个集合打上标签信息

并查集时间复杂度的理解

作为如此简单、小巧的结构，

感性理解单次调用的均摊时间复杂度为O(1)即可，其实为α(n)，反阿克曼函数

当n=10^80次方即可探明宇宙原子量，α(n)的返回值也不超过6，那就可以认为是O(1)

并查集的发明者Bernard A. Galler和Michael J. Fischer，

从1964年证明到1989年才证明完毕，建议记住即可，理解证明难度很大！

题目1
并查集模版(牛客)
路径压缩 + 小挂大
测试链接 : 
https://www.nowcoder.com/practice/e7ed657974934a30b2010046536a5372


题目2
并查集模版(洛谷)
用递归函数实现路径压缩
一般情况下小挂大的优化可以省略的写法
测试链接 : https://www.luogu.com.cn/problem/P3367



题目3
情侣牵手
n对情侣坐在连续排列的 2n 个座位上，想要牵到对方的手
人和座位由一个整数数组 row，表示其中 row[i] 是坐在第 i 个座位上的人的ID
情侣们按顺序编号，第0对是 (0, 1)，第1对是 (2, 3)，以此类推
返回 最少交换座位的次数，以便每对情侣可以并肩坐在一起
每次交换可选择任意两人，让他们站起来交换座位
测试链接 : https://leetcode.cn/problems/couples-holding-hands/




题目4
相似字符串组
如果交换字符串 X 中的两个不同位置的字母，使得它和字符串 Y 相等
那么称 X 和 Y 两个字符串相似
如果这两个字符串本身是相等的，那它们也是相似的
例如，"tars" 和 "rats" 是相似的 (交换 0 与 2 的位置)；
"rats" 和 "arts" 也是相似的，但是 "star" 不与 "tars"，"rats"，或 "arts" 相似
总之，它们通过相似性形成了两个关联组：{"tars", "rats", "arts"} 和 {"star"}
注意，"tars" 和 "arts" 是在同一组中，即使它们并不相似
形式上，对每个组而言，要确定一个单词在组中，只需要这个词和该组中至少一个单词相似。
给你一个字符串列表 strs列表中的每个字符串都是 strs 中其它所有字符串的一个字母异位词。
返回 strs 中有多少字符串组
测试链接 : https://leetcode.cn/problems/similar-string-groups/

题目5
岛屿数量
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成
此外，你可以假设该网格的四条边均被水包围
测试链接 : https://leetcode.cn/problems/number-of-islands/

注意：本题还可以用洪水填充算法求解，后续【必备】课程会讲述洪水填充算法

2026.03.28 19:59

算法讲解057【必备】并查集-下

前置知识 : 讲解056-并查集-上

本节课讲解并查集的更多题目

并查集的小扩展可以定制信息：并查集目前有多少个集合，以及给每个集合打上标签信息

注意：带权并查集、可持久化并查集、可撤销并查集，都是备战算法竞赛的同学必学的内容这些内容会在【挺难】阶段的课程里安排讲述

题目1
移除最多的同行或同列石头
n 块石头放置在二维平面中的一些整数坐标点上。每个坐标点上最多只能有一块石头
如果一块石头的 同行或者同列 上有其他石头存在，那么就可以移除这块石头
给你一个长度为 n 的数组 stones ，
其中 stones[i] = [xi, yi] 表示第 i 块石头的位置
返回 可以移除的石子 的最大数量。
测试链接 : 
https://leetcode.cn/problems/most-stones-removed-with-same-row-or-column/


题目2
找出知晓秘密的所有专家
给你一个整数 n ，表示有 n 个专家从 0 到 n - 1 编号
另外给你一个下标从 0 开始的二维整数数组 meetings
其中 meetings[i] = [xi, yi, timei]，表示专家 xi 和专家 yi 在时间 timei 要开一场会
一个专家可以同时参加 多场会议 。最后，给你一个整数 firstPerson
专家 0 有一个 秘密 ，最初，他在时间 0 将这个秘密分享给了专家 firstPerson
接着，这个秘密会在每次有知晓这个秘密的专家参加会议时进行传播
更正式的表达是，每次会议，如果专家 xi 在时间 timei 时知晓这个秘密
那么他将会与专家 yi 分享这个秘密，反之亦然。秘密共享是 瞬时发生 的
也就是说，在同一时间，一个专家不光可以接收到秘密，还能在其他会议上与其他专家分享
在所有会议都结束之后，返回所有知晓这个秘密的专家列表，你可以按 任何顺序 返回答案
链接测试 : https://leetcode.cn/problems/find-all-people-with-secret/


题目3
好路径的数目
给你一棵 n 个节点的树（连通无向无环的图）
节点编号从0到n-1，且恰好有n-1条边
给你一个长度为 n 下标从 0 开始的整数数组 vals
分别表示每个节点的值。同时给你一个二维整数数组 edges
其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间有一条 无向 边
好路径需要满足以下条件：开始和结束节点的值相同、 路径中所有值都小于等于开始的值
请你返回不同好路径的数目
注意，一条路径和它反向的路径算作 同一 路径
比方说， 0 -> 1 与 1 -> 0 视为同一条路径。单个节点也视为一条合法路径
测试链接 : https://leetcode.cn/problems/number-of-good-paths/


题目4
尽量减少恶意软件的传播 II
给定一个由 n 个节点组成的网络，一定是无向图，用 n * n 个邻接矩阵 graph 表示
在节点网络中，只有当 graph[i][j] = 1 时，节点 i 能够直接连接到另一个节点 j。
一些节点 initial 最初被恶意软件感染。只要两个节点直接连接，
且其中至少一个节点受到恶意软件的感染，那么两个节点都将被恶意软件感染。
这种恶意软件的传播将继续，直到没有更多的节点可以被这种方式感染。
假设 M(initial) 是在恶意软件停止传播之后，
整个网络中感染恶意软件的最终节点数。
我们可以从 initial 中删除一个节点，
并完全移除该节点以及从该节点到任何其他节点的任何连接。
请返回移除后能够使 M(initial) 最小化的节点。
如果有多个节点满足条件，返回索引 最小的节点 。initial 中每个整数都不同
测试链接 : https://leetcode.cn/problems/minimize-malware-spread-ii/

2026.03.30 18:16

尚同

2026.04.12 18:25

算法讲解058【必备】洪水填充

前置知识 : 讲解038-常见经典递归过程解析，其中的带路径的递归过程解析

洪水填充是一种很简单的技巧，设置路径信息进行剪枝和统计，类似感染的过程

路径信息不撤销，来保证每一片的感染过程可以得到区分

看似是暴力递归过程，其实时间复杂度非常好，遍历次数和样本数量的规模一致

题目：

题目1
岛屿数量
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成
此外，你可以假设该网格的四条边均被水包围
测试链接 : https://leetcode.cn/problems/number-of-islands/


题目2
被围绕的区域
给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域
并将这些区域里所有的 'O' 用 'X' 填充。
测试链接 : https://leetcode.cn/problems/surrounded-regions/

题目3
最大人工岛
给你一个大小为 n * n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。
返回执行此操作后，grid 中最大的岛屿面积是多少？
岛屿 由一组上、下、左、右四个方向相连的 1 形成
测试链接 : https://leetcode.cn/problems/making-a-large-island/


题目4
打砖块
有一个 m * n 的二元网格 grid ，其中 1 表示砖块，0 表示空白
砖块 稳定（不会掉落）的前提是：
一块砖直接连接到网格的顶部，或者
至少有一块相邻（4 个方向之一）砖块 稳定 不会掉落时
给你一个数组 hits ，这是需要依次消除砖块的位置
每当消除 hits[i] = (rowi, coli) 位置上的砖块时，对应位置的砖块（若存在）会消失
然后其他的砖块可能因为这一消除操作而 掉落
一旦砖块掉落，它会 立即 从网格 grid 中消失（即，它不会落在其他稳定的砖块上）
返回一个数组 result ，其中 result[i] 表示第 i 次消除操作对应掉落的砖块数目。
注意，消除可能指向是没有砖块的空白位置，如果发生这种情况，则没有砖块掉落。
测试链接 : https://leetcode.cn/problems/bricks-falling-when-hit/

2026.04.13 14:47

算法讲解059【必备】建图、链式前向星、拓扑排序

（1）总体知识点

前置知识：讲解013-数组实现队列、讲解019-算法笔试更推荐静态空间的方式、讲解025-堆结构。

图论题的输入一般有两类：

给你节点数 n 和边集，需要你自己建图。
直接给你一个图结构，但题目通常还是会考你怎么存、怎么遍历、怎么处理入度或出度。

这节课先解决两个基础问题：

图怎么建。
有向无环图怎么做拓扑排序。

（2）图的三种表示

适合点数不大、需要快速判断两点之间是否有边的场景。空间是 $O (n^{2})$ ，点多时很容易爆。

最常用的建图方式。每个点维护一个边集合，遍历某个点的出边很方便，空间一般是 $O (n + m)$ 。

本质上也是“邻接表”的静态数组版本，优点是空间稳定、常数小，特别适合比赛和大规模静态建图。

（3）链式前向星

链式前向星图解

链式前向星可以理解成：把“同一个起点的所有边”按加入顺序连成一条链，然后从 head[u] 开始一路顺着 ne 往后找。

四个数组的含义：

head[u]：点 u 的第一条边编号
e[i]：第 i 条边指向的终点
weight[i]：第 i 条边的权重
ne[i]：第 i 条边的下一条同起点边编号

以及一个边编号计数器：

cnt：当前可用边编号，通常从 1 开始，0 作为“空指针”哨兵

它的访问链就是：

u -> head[u] -> ne[head[u]] -> ne[ne[head[u]]] -> ...

沿着这条链，就能遍历 u 的全部出边。

头插法模板

c++

#include <cstring>
#include <iostream>
using namespace std;

// 点的最大数量
const int MAXN = 11;
// 边的最大数量（无向图要 ×2）
const int MAXM = 21;

// 链式前向星核心数组
int head[MAXN];    // 每个点的第一条边
int ne[MAXM];      // 下一条边（C++ 不能用 ne 关键字，改名 ne）
int e[MAXM];       // 边指向的点
int weight[MAXM];  // 边权
int cnt;           // 边的编号计数器

// 初始化链式前向星（清空）
void build(int n) {
  cnt = 1;
  // 清空 1~n 号点的 head
  memset(head + 1, 0, n * sizeof(int));
}

// 加边：u -> v，权值 w
void addEdge(int u, int v, int w) {
  ne[cnt] = head[u];
  e[cnt] = v;
  weight[cnt] = w;
  head[u] = cnt++;
}

// 遍历链式前向星
void traversal(int n) {
  cout << "链式前向星:" << endl;
  for (int i = 1; i <= n; ++i) {
    cout << i << "(邻居、边权) : ";
    for (int ei = head[i]; ei > 0; ei = ne[ei]) {
      cout << "(" << e[ei] << "," << weight[ei] << ") ";
    }
    cout << endl;
  }
}

// ===================== 测试示例=====================
int main() {
  // 测试 1：有向图
  cout << "=== 有向带权图 ===" << endl;
  int n1 = 4;
  int edges1[6][3] = {{1, 3, 6}, {4, 3, 4}, {2, 4, 2},
                      {1, 2, 7}, {2, 3, 5}, {3, 1, 1}};
  build(n1);
  for (auto& edge : edges1) { addEdge(edge[0], edge[1], edge[2]); }
  traversal(n1);

  // 测试 2：无向图
  cout << "\n=== 无向带权图 ===" << endl;
  int n2 = 5;
  int edges2[7][3] = {{3, 5, 4}, {4, 1, 1}, {3, 4, 2}, {5, 2, 4},
                      {2, 3, 7}, {1, 5, 5}, {4, 2, 6}};
  build(n2);
  for (auto& edge : edges2) {
    addEdge(edge[0], edge[1], edge[2]);
    addEdge(edge[1], edge[0], edge[2]);
  }
  traversal(n2);

  return 0;
}

使用方式

有向图：每条边只加一次。
无向图：同一条边要反向再加一次。

常见注意点

无向图要把边数组开大一倍，否则会越界。
每组数据都要重新 build(n)，不然旧图会残留。
如果题目点编号是 0...n-1，初始化和遍历下标都要同步改。
0 作为空指针哨兵时，cnt 就不要从 0 开始。

（4）拓扑排序

拓扑排序只适用于有向无环图（DAG）。

每个节点的前置节点都在这个节点之前

要求：有向图、没有环

拓扑排序的顺序可能不只一种。拓扑排序也可以用来判断有没有环。

1）在图中找到所有入度为0的点

2）把所有入度为0的点在图中删掉，重点是删掉影响！继续找到入度为0的点并删掉影响

3）直到所有点都被删掉，依次删除的顺序就是正确的拓扑排序结果

4）如果无法把所有的点都删掉，说明有向图里有环

注意：本节课讲解拓扑排序直接使用解决的题目，下节课会讲拓扑排序扩展技巧解决的题目

（5）题目对应

题目1
三种方式的建图和遍历


题目2
拓扑排序模版
邻接表建图（动态方式）
链式前向星建图（静态方式）
测试链接 : https://leetcode.cn/problems/course-schedule-ii
测试链接 : https://www.nowcoder.com/practice/88f7e156ca7d43a1a535f619cd3f495c


题目3
字典序最小的拓扑排序
要求返回所有正确的拓扑排序中 字典序最小 的结果
建图请使用链式前向星方式，因为比赛平台用其他建图方式会卡空间
测试链接 : https://www.luogu.com.cn/problem/U107394

注意：解决该问题需要使用小根堆，不熟悉的同学去看，讲解025-堆结构


题目4
火星词典
现有一种使用英语字母的火星语言
这门语言的字母顺序对你来说是未知的。
给你一个来自这种外星语言字典的字符串列表 words
words 中的字符串已经 按这门新语言的字母顺序进行了排序 。
如果这种说法是错误的，并且给出的 words 不能对应任何字母的顺序，则返回 ""
否则，返回一个按新语言规则的 字典递增顺序 排序的独特字符串
如果有多个解决方案，则返回其中任意一个
words中的单词一定都是小写英文字母组成的
测试链接 : https://leetcode.cn/problems/alien-dictionary（会员）
非会员测试链接 : https://leetcode.cn/problems/Jf1JuT/description/



题目5
戳印序列
你想最终得到"abcbc"，认为初始序列为"?????"。印章是"abc"
那么可以先用印章盖出"??abc"的状态，
然后用印章最左字符和序列的0位置对齐，就盖出了"abcbc"
这个过程中，"??abc"中的a字符，被印章中的c字符覆盖了
每次盖章的时候，印章必须完全盖在序列内
给定一个字符串target是最终的目标，长度为n，认为初始序列为n个'?'
给定一个印章字符串stamp，目标是最终盖出target，但是印章的使用次数必须在10*n次以内
返回一个数组，该数组由每个回合中被印下的最左边字母的索引组成
上面的例子返回[2,0]，表示印章最左字符依次和序列2位置、序列0位置对齐盖下去，就得到了target
如果不能在10*n次内印出序列，就返回一个空数组
测试链接 : https://leetcode.cn/problems/stamping-the-sequence

2026.04.13 20:07

算法讲解060【必备】拓扑排序的扩展技巧

（1）知识点讲解

前置知识 :

讲解041-同余原理

讲解059~讲解065都是【必备】课程有关图的内容，建议从头开始学习

本节课继续讲解拓扑排序的题目

注意：这个技巧已经是树型dp的内容了，不过即便不会动态规划，本节课也能听懂

动态规划专题（包括树型dp）会在后续【必备】课程里讲述

（2）题目

题目1
最大食物链计数
a -> b，代表a在食物链中被b捕食
给定一个有向无环图，返回
这个图中从最初级动物到最顶级捕食者的食物链有几条
测试链接 : https://www.luogu.com.cn/problem/P4017

注意：本题答案很大，需要取模，不了解的同学看一下，讲解041-同余原理


题目2
喧闹和富有
从 0 到 n - 1 编号，其中每个人都有不同数目的钱，以及不同程度的安静值
给你一个数组richer，其中richer[i] = [ai, bi] 表示 
person ai 比 person bi 更有钱
还有一个整数数组 quiet ，其中 quiet[i] 是 person i 的安静值
richer 中所给出的数据 逻辑自洽
也就是说，在 person x 比 person y 更有钱的同时，不会出现
person y 比 person x 更有钱的情况
现在，返回一个整数数组 answer 作为答案，其中 answer[x] = y 的前提是,
在所有拥有的钱 肯定不少于 person x 的人中，
person y 是最安静的人（也就是安静值 quiet[y] 最小的人）。
测试链接 : https://leetcode.cn/problems/loud-and-rich/



题目3
并行课程 III
给你一个整数 n ，表示有 n 节课，课程编号从 1 到 n
同时给你一个二维整数数组 relations ，
其中 relations[j] = [prevCoursej, nextCoursej]
表示课程 prevCoursej 必须在课程 nextCoursej 之前 完成（先修课的关系）
同时给你一个下标从 0 开始的整数数组 time
其中 time[i] 表示完成第 (i+1) 门课程需要花费的 月份 数。
请你根据以下规则算出完成所有课程所需要的 最少 月份数：
如果一门课的所有先修课都已经完成，你可以在 任意 时间开始这门课程。
你可以 同时 上 任意门课程 。请你返回完成所有课程所需要的 最少 月份数。
注意：测试数据保证一定可以完成所有课程（也就是先修课的关系构成一个有向无环图）
测试链接 : https://leetcode.cn/problems/parallel-courses-iii/


题目4
参加会议的最多员工数
一个公司准备组织一场会议，邀请名单上有 n 位员工
公司准备了一张 圆形 的桌子，可以坐下 任意数目 的员工
员工编号为 0 到 n - 1 。每位员工都有一位 喜欢 的员工
每位员工 当且仅当 他被安排在喜欢员工的旁边，他才会参加会议
每位员工喜欢的员工 不会 是他自己。给你一个下标从 0 开始的整数数组 favorite
其中 favorite[i] 表示第 i 位员工喜欢的员工。请你返回参加会议的 最多员工数目
测试链接 : 
https://leetcode.cn/problems/maximum-employees-to-be-invited-to-a-meeting/

2026.04.14 16:05

尚同

2026.04.15 11:52

算法讲解061【必备】最小生成树

前置知识 : 讲解025、026、027 - 堆的内容、讲解056、057 - 并查集的内容

讲解059~讲解065都是【必备】课程有关图的内容，建议从头开始学习

补充理解：

最小生成树可能不只一棵，只要总权值最小，就是正确答案。
如果无向带权图有 n 个点，并且图是连通的，那么最小生成树一定有 n - 1 条边。
如果图本身不连通，那么严格来说不存在生成树，只能得到最小生成森林。
最小生成树一定是最小瓶颈树，也就是说，在所有生成树里，它能把“最大边权”压到最优。

常见选择：

边比较少时，Kruskal 很自然。
图比较稠密，或者更习惯从点出发扩展时，可以用 Prim。
Kruskal 最适合和并查集配套；Prim 最适合和堆配套。
本节课先掌握最基础、最常用的写法，比赛里再按题目特性选优化版。

1. Kruskal算法（最常用）

核心思想：从小到大挑边，只要不会形成环，就把这条边加入答案。

步骤：

把所有边按权值从小到大排序。
依次考察每条边，判断这条边连接的两个点是否已经在同一个集合里。
如果不在同一个集合里，就选这条边，并把两个集合合并。
如果在同一个集合里，说明再加这条边会成环，直接舍弃。
当选了 n - 1 条边时，最小生成树已经完成。

实现关键：并查集。

时间复杂度：O(m * log m) + O(m * α(n)) + O(n)，通常直接记成 O(m * log m)

适用场景：边集可以直接拿到，且排序成本可接受。

2. Prim算法（不算常用）

核心思想：从任意一个点出发，不断把“能把新点接进来”的最小代价边加进来。

步骤：

任选一个点作为起点，把它加入已解锁点集合 set。
把起点发出的所有边都放进小根堆 heap。
每次从 heap 弹出权值最小的边 e，查看它通向的点 x。
如果 x 已经在 set 中，说明这条边无法带来新点，直接忽略。
如果 x 不在 set 中，就把这条边加入答案，并把 x 加入 set。
然后把 x 发出的所有边继续加入 heap，重复上述过程。
当 heap 为空时，整个连通块的最小生成树就完成了。

实现关键：小根堆 + “已加入集合”的判断。

时间复杂度：O(n + m) + O(m * log m)

适用场景：从点向外扩展更自然，或者题目已经是邻接表结构。

Prim算法的优化（比较难，不感兴趣可以跳过）请一定要对堆很熟悉！

小根堆里放 (节点，到达该节点的最小代价)，堆按“到达代价”组织。
每次弹出 (u, y)，说明以 y 的代价把 u 加入生成树，先把 y 累加到答案里。
然后枚举 u 出发的每条边，设 u 连向 v，边权为 w。
如果 v 已经确定加入生成树了，直接忽略这条边。
如果 v 之前没有进过堆，就加入 (v, w)。
如果 v 之前进过堆，且当前记录是 (v, x)：

若 w < x，就把记录更新成 (v, w)，并调整堆。
若 w >= x，忽略这条边。

重复上述过程，直到堆为空。

时间复杂度：O(n + m) + O((m + n) * log n)

说明：这里是“优化版 Prim”的思路，核心是用堆维护每个未加入点的当前最优连接代价。

常见坑：

Prim 默认要求图连通；不连通时只能处理一个连通块，想覆盖全部点要对每个未访问点再跑一遍。
Kruskal 处理的是“边”，Prim 处理的是“点的连接代价”，两者思路不同。
如果题目数据很大，优先考虑静态建图和并查集/堆的常数优化。
题目问“最少改造多少条路、最大边权尽量小”，本质上就是最小生成树。

3. 代码实现

题目链接：https://www.luogu.com.cn/problem/P3366

3.1 Kruskal算法：

c++

#include <algorithm>
#include <iostream>
using namespace std;
const int N = 5005;
const int M = 4e5 + 5;
int n, m;
struct Edge {
  int a, b, c;
  Edge() {}
  Edge(int a, int b, int c) : a(a), b(b), c(c) {}
  bool operator<(const Edge& e) const { return c < e.c; }
};
Edge edges[M];
int p[N];
void init() {
  for (int i = 0; i < N; i++) { p[i] = i; }
}
int find(int a) {
  if (p[a] == a) {
    return a;
  } else {
    return p[a] = find(p[a]);
  }
}
void Kruskal() {
  int result = 0;
  sort(edges, edges + m);
  init();
  int cnt = 0;
  for (int i = 0; i < m; i++) {
    int a = find(edges[i].a), b = find(edges[i].b);
    if (a != b) {
      result += edges[i].c;
      p[a] = b;
      cnt++;
    }
  }
  if (cnt < n - 1) {
    printf("orz");
  } else {
    printf("%d", result);
  }
}
int main() {
  scanf("%d %d", &n, &m);
  int a, b, c;
  for (int i = 0; i < m; i++) {
    scanf("%d %d %d", &edges[i].a, &edges[i].b, &edges[i].c);
  }
  Kruskal();
  return 0;
}

3.2 Prim算法

1）写法一:

邻接表建图，使用小根堆维护当前可选边的最小代价，适合比赛平台空间限制较紧的情况

c++

#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int N = 5e3 + 5, M = 4e5 + 5;
int n, m, x, y, z;
vector<pair<int, int>> graph[N];
bool isVisited[N];
// 小顶堆
struct cmp {
  bool operator()(const pair<int, int>& a, const pair<int, int>& b) const {
    return a.second > b.second;
  }
};
// 邻居 权重
priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> que;
int main() {
  scanf("%d%d", &n, &m);
  memset(isVisited, false, sizeof(isVisited));
  for (int i = 1; i <= m; i++) {
    scanf("%d%d%d", &x, &y, &z);
    graph[x].emplace_back(y, z);
    graph[y].emplace_back(x, z);
  }
  for (int i = 0; i < graph[1].size(); i++) {
    que.emplace(graph[1][i].first, graph[1][i].second);
  }
  int cnts = 1;
  isVisited[1] = true;
  int ans = 0;
  while (que.size()) {
    auto cur = que.top();
    que.pop();
    if (isVisited[cur.first] == false) {
      ans += cur.second, isVisited[cur.first] = true, cnts++;
      for (int i = 0; i < graph[cur.first].size(); i++) {
        que.emplace(graph[cur.first][i].first, graph[cur.first][i].second);
      }
    }
  }
  if (cnts == n) {
    printf("%d", ans);
  } else {
    printf("orz");
  }
  return 0;
}

2）写法二：

链式前向星建图，使用小根堆维护当前可选边的最小代价，适合比赛平台空间限制较紧的情况

c++

#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int N = 1e4 + 5;
const int M = 5e5 + 10;  // 无向图边数通常要开大一点，或者理解为逻辑边数
const int INF = 0x3f3f3f3f;

// 链式前向星存图
int h[N], e[M], ne[M], w[M], idx;
bool visited[N];  // 标记节点是否已加入最小生成树集合
int minDist[N];   // 记录每个点到“最小生成树集合”的最短距离
int n, m;         // n个点，m条边

void init() {
  memset(h, -1, sizeof(h));
  memset(visited, false, sizeof(visited));
  memset(minDist, 0x3f, sizeof(minDist));
  idx = 0;
}

// a --> b, 权重为c (无向图需要加两次)
void add(int a, int b, int c) {
  e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

struct cmp {
  // <节点, 该节点到生成树集合的距离>
  bool operator()(const pair<int, int>& a, const pair<int, int>& b) const {
    return a.second > b.second;  // 小顶堆
  }
};

// Prim 算法求最小生成树
void Prim(int srt) {
  long long total_weight = 0;  // 最小生成树的总权值
  int cnt = 0;                 // 记录加入生成树的节点数

  minDist[srt] = 0;
  // 小顶堆
  priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
  pq.emplace(srt, 0);

  while (!pq.empty()) {
    auto cur = pq.top();
    pq.pop();

    int to = cur.first;

    // 如果该点已经加入生成树，跳过
    if (visited[to]) { continue; }

    // 将该点加入生成树
    visited[to] = true;
    total_weight += cur.second;  // 累加边权
    cnt++;

    // 更新邻接点到生成树的距离
    for (int i = h[to]; i != -1; i = ne[i]) {
      int j = e[i];
      // 如果点j不在树中，且 to到j 的边权 小于 j当前到树的最短距离
      if (!visited[j] && minDist[j] > w[i]) {
        minDist[j] = w[i];
        pq.emplace(j, minDist[j]);
      }
    }
  }

  // 如果 cnt < n，说明图不连通，不存在最小生成树
  if (cnt < n) {
    printf("orz");  // 或者输出 impossible
  } else {
    printf("%lld", total_weight);
  }
}

int main() {
  init();
  // 输入点数和边数
  scanf("%d %d", &n, &m);

  int a, b, c;
  for (int i = 0; i < m; i++) {
    scanf("%d %d %d", &a, &b, &c);
    // Prim通常处理无向图，所以需要添加双向边
    add(a, b, c);
    add(b, a, c);
  }

  // 从节点 1 开始构建生成树（任意节点均可）
  Prim(1);

  return 0;
}

3）写法三：

链式前向星建图，手写堆结构维护当前可选边的最小代价，适合比赛平台空间限制较紧的情况（反向索引堆）

c++

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;

const int MAXN = 5001;
const int MAXM = 400001;

int n, m;

// 链式前向星建图
int head[MAXN];
int next_[MAXM];  // 避免和关键字next冲突
int to[MAXM];
int weight[MAXM];
int cnt;

// 手写堆结构
int heap[MAXN][2];
// where[v] = -1 未入堆, -2 已弹出, >=0 在堆中位置
int where[MAXN];
int heapSize;

// 已找到的节点数量
int nodeCnt;

// 堆顶弹出的节点和权值
int u;
int w;

void build() {
  cnt = 1;
  heapSize = 0;
  nodeCnt = 0;
  memset(head, 0, sizeof(int) * (n + 1));
  memset(where, -1, sizeof(int) * (n + 1));
}

void addEdge(int u, int v, int w) {
  next_[cnt] = head[u];
  to[cnt] = v;
  weight[cnt] = w;
  head[u] = cnt++;
}

// 交换堆中 i 和 j 位置
void swap(int i, int j) {
  int a = heap[i][0];
  int b = heap[j][0];
  where[a] = j;
  where[b] = i;
  swap(heap[i], heap[j]);
}

// 堆向上调整
void heapInsert(int i) {
  while (heap[i][1] < heap[(i - 1) / 2][1]) {
    swap(i, (i - 1) / 2);
    i = (i - 1) / 2;
  }
}

// 堆向下调整
void heapify(int i) {
  int l = i * 2 + 1;
  while (l < heapSize) {
    int best = (l + 1 < heapSize && heap[l + 1][1] < heap[l][1]) ? l + 1 : l;
    best = heap[best][1] < heap[i][1] ? best : i;
    if (best == i) break;
    swap(best, i);
    i = best;
    l = i * 2 + 1;
  }
}

// 添加/更新/忽略边
void addOrUpdateOrIgnore(int ei) {
  int v = to[ei];
  int w = weight[ei];
  if (where[v] == -1) {
    heap[heapSize][0] = v;
    heap[heapSize][1] = w;
    where[v] = heapSize++;
    heapInsert(where[v]);
  } else if (where[v] >= 0) {
    heap[where[v]][1] = min(heap[where[v]][1], w);
    heapInsert(where[v]);
  }
}

// 弹出堆顶
void pop() {
  u = heap[0][0];
  w = heap[0][1];
  swap(0, --heapSize);
  heapify(0);
  where[u] = -2;
  nodeCnt++;
}

// 判断堆是否为空
bool isEmpty() { return heapSize == 0; }

// Prim算法核心
int prim() {
  // 从 1 号节点出发
  nodeCnt = 1;
  where[1] = -2;
  for (int ei = head[1]; ei > 0; ei = next_[ei]) { addOrUpdateOrIgnore(ei); }
  int ans = 0;
  while (!isEmpty()) {
    pop();
    ans += w;
    for (int ei = head[u]; ei > 0; ei = next_[ei]) { addOrUpdateOrIgnore(ei); }
  }
  return ans;
}

// 主函数（快速读写，洛谷专用）
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> n >> m;
  build();
  for (int i = 0, u, v, w; i < m; ++i) {
    cin >> u >> v >> w;
    addEdge(u, v, w);
    addEdge(v, u, w);
  }
  int ans = prim();
  if (nodeCnt == n) {
    cout << ans << '\n';
  } else {
    cout << "orz\n";
  }
  return 0;
}

9. 题目

题目1
实现Kruskal算法
返回最小生成树的最小权值和
测试链接 : https://www.luogu.com.cn/problem/P3366

题目2
实现Prim算法
普通版 + 优化版
返回最小生成树的最小权值和
测试链接 : https://www.luogu.com.cn/problem/P3366


题目3
水资源分配优化
村里面一共有 n 栋房子。我们希望通过建造水井和铺设管道来为所有房子供水。
对于每个房子 i，我们有两种可选的供水方案：一种是直接在房子内建造水井
成本为 wells[i - 1] （注意 -1 ，因为 索引从0开始 ）
另一种是从另一口井铺设管道引水，数组 pipes 给出了在房子间铺设管道的成本，
其中每个 pipes[j] = [house1j, house2j, costj] 
代表用管道将 house1j 和 house2j连接在一起的成本。连接是双向的。
请返回 为所有房子都供水的最低总成本
测试链接 : https://leetcode.cn/problems/optimize-water-distribution-in-a-village/ （需要会员）

洛谷同题链接 : https://www.luogu.com.cn/problem/P1194




题目4
检查边长度限制的路径是否存在
给你一个 n 个点组成的无向图边集 edgeList
其中 edgeList[i] = [ui, vi, disi] 表示点 ui 和点 vi 之间有一条长度为 disi 的边
请注意，两个点之间可能有 超过一条边 。
给你一个查询数组queries ，其中 queries[j] = [pj, qj, limitj]
你的任务是对于每个查询 queries[j] ，判断是否存在从 pj 到 qj 的路径
且这条路径上的每一条边都 严格小于 limitj 。
请你返回一个 布尔数组 answer ，其中 answer.length == queries.length
当 queries[j] 的查询结果为 true 时， answer 第 j 个值为 true ，否则为 false
测试链接 : 
https://leetcode.cn/problems/checking-existence-of-edge-length-limited-paths/


题目5
繁忙的都市
一个非常繁忙的大都市，城市中的道路十分的拥挤，于是市长决定对其中的道路进行改造
城市的道路是这样分布的：城市中有n个交叉路口，有些交叉路口之间有道路相连
两个交叉路口之间最多有一条道路相连接，这些道路是双向的
且把所有的交叉路口直接或间接的连接起来了
每条道路都有一个分值，分值越小表示这个道路越繁忙，越需要进行改造
但是市政府的资金有限，市长希望进行改造的道路越少越好，于是他提出下面的要求：
1. 改造的那些道路能够把所有的交叉路口直接或间接的连通起来
2. 在满足要求1的情况下，改造的道路尽量少
3. 在满足要求1、2的情况下，改造的那些道路中分值最大的道路分值尽量小
作为市规划局的你，应当作出最佳的决策，选择哪些道路应当被修建
返回选出了几条道路 以及 分值最大的那条道路的分值是多少
测试链接 : https://www.luogu.com.cn/problem/P2330

2026.04.16 19:46

尚同

2026.04.21 19:23

算法讲解062【必备】宽度优先遍历及其扩展

前置知识

会使用队列、双端队列、优先级队列（堆）

讲解036-二叉树上的宽度优先遍历

讲解038-经典递归过程解析，之前所有递归的内容需要好好理解，后面的课用到递归越来越多

讲解059~讲解065都是【必备】课程有关图的内容，建议从头开始学习

本节课核心目标：

建立“见题选 BFS 变种”的判断框架。
掌握单源 BFS、多源 BFS、01BFS、堆优化 BFS 的统一视角。
掌握 BFS + DFS 配合生成所有最短路径的套路。

1. 宽度优先遍历总览

bfs 的本质：按“距离层”扩散。谁先出队，谁当前最短。

当图满足“每条边代价一致（通常都为1）”时，bfs 从源点扩散到目标点的层数，就是最短路长度。

常见形态：

单源 bfs：一个起点出发，求到所有点或某个目标点的最短距离。
多源 bfs：多个起点同时出发，等价于建立“超级源点”后单源 bfs。
0/1 边权最短路：使用 01bfs。
非负边权最短路：使用堆优化 bfs（本质是 Dijkstra）。

一句话选型：

边权全相同 -> bfs。
边权只有 0/1 -> 01bfs。
边权非负且不只 0/1 -> 堆优化 bfs（Dijkstra）。

2. 单源 BFS 与多源 BFS

2.1 单源 BFS 模板思维

队列初始化：源点入队。
距离初始化：distance[source] = 0，其余为无穷大。
标记时机：节点一旦入队就标记 visited，防止重复入队。
出队扩展：遍历当前点的所有邻居，满足条件就入队并更新距离。
终止策略：

求单目标最短路，可在目标第一次出队时结束。
求全图最短路，要跑到队列为空。

时间复杂度：O(节点数量 + 边数量)

2.2 多源 BFS 模板思维

把所有起点在一开始全部入队，且它们的 distance 都置为 0。

其余过程与单源 bfs 完全一致。

典型语义：

每个点到“最近源点”的距离。
波纹扩散类问题（火焰传播、感染、海陆最远距离等）。

3. 01BFS（双端队列）

为什么不用普通 bfs：普通 bfs 默认每条边代价相同；0/1 边权不满足这个前提。

核心机制：

distance[i] 表示源点到 i 的最短距离，初始为无穷大。
源点入双端队列，distance[source] = 0。
队头弹出 x，枚举 x 的每条边 x -> y（权重 w）。
若 distance[y] > distance[x] + w，执行松弛：

更新 distance[y]。
若 w == 0，y 从队头入队。
若 w == 1，y 从队尾入队。

双端队列为空时结束。

时间复杂度：O(节点数量 + 边数量)

关键理解：

01bfs 不一定要用 visited 数组，按 distance 是否被更优更新来控制即可。
同一个点可能多次入队，但只有更优距离才有意义。

4. 宽度优先遍历与优先级队列结合

当边权是非负整数且不止 0/1 时，使用优先级队列维护“当前距离最小”的状态扩展。

这就是 Dijkstra 的核心过程，可视为 bfs 在“距离度量不再等步长”时的升级版。

流程要点：

小根堆弹出当前最小距离状态。
对所有邻边做松弛。
可配合“过期状态判断”剪枝（如果弹出距离大于当前记录就跳过）。

复杂度常见写法：O((节点数量 + 边数量) * log 节点数量)

5. BFS 与 DFS 结合生成所有最短路径

代表题：单词接龙 II。

核心套路：

bfs 只做一件事：分层，得到每个点的最短层数（或构建“最短路 DAG”）。
dfs 再做一件事：只沿着“层数 +1”的合法边回溯/搜索，生成全部最短路径。

为什么要分两步：

直接 dfs 会爆炸。
先 bfs 锁定最短层，再 dfs 只走最短路边，复杂度可控。

6. 网格 BFS 常见实现细节

方向数组固定写法：up/down/left/right。
越界判断单独函数化，减少漏判。
访问标记与入队同步，避免重复扩展。
如果题目允许“状态变化”（钥匙、次数、方向），visited 要带维度。
目标可提前结束时，尽量早停。

7. 易错点总结

把“无权最短路”与“带权最短路”混用，导致算法选错。
visited 标记过晚（出队才标），导致同点反复入队。
多源 bfs 忘记把所有源点初始入队。
01bfs 中 0 边和 1 边入队位置写反。
Dijkstra 忘记写“过期状态剪枝”，导致超时。
网格题忘记状态维度，导致错误去重。

8. 本节题目与方法映射

地图分析：多源 bfs。
贴纸拼词：状态图 bfs（常与记忆化搜索互相验证）。
到达角落移除障碍最小数目：01bfs。
使网格至少有一条有效路径最小代价：01bfs。
二维接雨水：堆优化 bfs（最小堆按边界高度扩展）。
单词接龙 II：bfs 分层 + dfs 还原所有最短路径。

4. 题目

题目1
地图分析
你现在手里有一份大小为 n x n 的 网格 grid
上面的每个 单元格 都用 0 和 1 标记好了其中 0 代表海洋，1 代表陆地。
请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的
并返回该距离。如果网格上只有陆地或者海洋，请返回 -1。
我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：
(x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。
测试链接 : https://leetcode.cn/problems/as-far-from-land-as-possible/



题目2
贴纸拼词
我们有 n 种不同的贴纸。每个贴纸上都有一个小写的英文单词。
您想要拼写出给定的字符串 target ，方法是从收集的贴纸中切割单个字母并重新排列它们
如果你愿意，你可以多次使用每个贴纸，每个贴纸的数量是无限的。
返回你需要拼出 target 的最小贴纸数量。如果任务不可能，则返回 -1
注意：在所有的测试用例中，所有的单词都是从 1000 个最常见的美国英语单词中随机选择的
并且 target 被选择为两个随机单词的连接。
测试链接 : https://leetcode.cn/problems/stickers-to-spell-word/


题目3
到达角落需要移除障碍物的最小数目
给你一个下标从 0 开始的二维整数数组 grid ，数组大小为 m x n
每个单元格都是两个值之一：
0 表示一个 空 单元格，
1 表示一个可以移除的 障碍物
你可以向上、下、左、右移动，从一个空单元格移动到另一个空单元格。
现在你需要从左上角 (0, 0) 移动到右下角 (m - 1, n - 1) 
返回需要移除的障碍物的最小数目
测试链接 : https://leetcode.cn/problems/minimum-obstacle-removal-to-reach-corner/


题目4
使网格图至少有一条有效路径的最小代价
给你一个 m * n 的网格图 grid 。 grid 中每个格子都有一个数字
对应着从该格子出发下一步走的方向。 grid[i][j] 中的数字可能为以下几种情况：
1 : 往右   2：往左   3：往下   4：往上
注意网格图中可能会有无效数字 ，因为它们可能指向grid以外的区域
从最左上角的格子 (0,0) 出发，有效路径为每一步都顺着数字对应方向走
最终在最右下角的格子 (m - 1, n - 1) 结束的路径
有效路径 不需要是最短路径
可以花费1的代价修改一个格子中的数字，但每个格子中的数字只能修改一次
返回让网格图至少有一条有效路径的最小代价
测试链接 : https://leetcode.cn/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid/description/



题目5
二维接雨水
给你一个 m * n 的矩阵，其中的值均为非负整数，代表二维高度图每个单元的高度
请计算图中形状最多能接多少体积的雨水。
测试链接 : https://leetcode.cn/problems/trapping-rain-water-ii/

前置题目：
讲解050 - 双指针技巧 - 题目3 - 一维接雨水问题
强烈建议看过这个题再听这道题的解析


题目6
单词接龙 II
按字典 wordList 完成从单词 beginWord 到单词 endWord 转化
一个表示此过程的 转换序列 是形式上像 
beginWord -> s1 -> s2 -> ... -> sk 这样的单词序列，并满足：
每对相邻的单词之间仅有单个字母不同
转换过程中的每个单词 si（1 <= i <= k）必须是字典 wordList 中的单词
注意，beginWord 不必是字典 wordList 中的单词
sk == endWord
给你两个单词 beginWord 和 endWord ，以及一个字典 wordList
请你找出并返回所有从 beginWord 到 endWord 的 最短转换序列
如果不存在这样的转换序列，返回一个空列表
每个序列都应该以单词列表 [beginWord, s1, s2, ..., sk] 的形式返回
测试链接 : https://leetcode.cn/problems/word-ladder-ii/

2026.04.22 11:15

尚同

2026.04.22 19:10

算法讲解063【必备】双向广搜

前置知识

前置知识: 讲解038-经典递归过程解析、讲解043-根据数据量猜解法、讲解062-宽度优先遍历及其扩展

讲解059~讲解065都是【必备】课程有关图的内容，建议从头开始学习

算法讲解

（1）双向广搜常见用途1：小优化

bfs的剪枝策略，分两侧展开分支，，可以在某些情况下减少搜索空间，达到加速的效果。

（2）双向广搜常见用途2：重要！本体！用于解决特征很明显的一类问题

特征：全量样本不允许递归完全展开，但是半量样本可以完全展开

过程：把数据分成两部分，每部分各自展开计算结果，然后设计两部分结果的整合逻辑

题目


题目1
单词接龙
字典 wordList 中从单词 beginWord 和 endWord 的 转换序列
是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk ：
每一对相邻的单词只差一个字母。
对于 1 <= i <= k 时，每个 si 都在 wordList 中
注意， beginWord 不需要在 wordList 中。sk == endWord
给你两个单词 beginWord 和 endWord 和一个字典 wordList
返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目
如果不存在这样的转换序列，返回 0 。
测试链接 : https://leetcode.cn/problems/word-ladder



题目2
零食问题 & 世界冰球锦标赛
牛牛准备参加学校组织的春游, 出发前牛牛准备往背包里装入一些零食, 牛牛的背包容量为w
牛牛家里一共有n袋零食, 第i袋零食体积为v[i]
牛牛想知道在总体积不超过背包容量的情况下
一共有多少种零食放法(总体积为0也算一种放法)
数据量描述:
1 <= n <= 40, 1 <= w <= 2 * 10^9, 0 <= v[i] <= 10^9
测试链接 : https://www.nowcoder.com/practice/d94bb2fa461d42bcb4c0f2b94f5d4281
测试链接 : https://www.luogu.com.cn/problem/P4799


题目3
最接近目标值的子序列和
给你一个整数数组 nums 和一个目标值 goal
你需要从 nums 中选出一个子序列，使子序列元素总和最接近 goal
也就是说，如果子序列元素和为 sum ，你需要 最小化绝对差 abs(sum - goal)
返回 abs(sum - goal) 可能的 最小值
注意，数组的子序列是通过移除原始数组中的某些元素（可能全部或无）而形成的数组。
数据量描述:
1 <= nums.length <= 40
-10^7 <= nums[i] <= 10^7
-10^9 <= goal <= 10^9
测试链接 : https://leetcode.cn/problems/closest-subsequence-sum

2026.04.24 19:48

尚同

2026.04.28 11:02

算法讲解064【必备】Dijkstra算法、分层图最短路

前置知识

讲解025、026、027-堆结构

讲解032-位图，用一个整型变量最多可以表示32个状态，并且非常方便、快速

讲解059-建图、链式前向星

讲解061-最小生成树，里面的 Prim 优化用了反向索引堆，强烈建议回看

讲解062-宽度优先遍历及其扩展

讲解059~讲解065都是【必备】课程有关图的内容，建议从头开始学习

本节核心内容：

Dijkstra 最短路的适用条件与本质。
普通堆写法、反向索引堆写法的区别。
分层图最短路的建模方法，也叫扩点最短路。
这些题目为什么可以统一成“状态图上的最短路”。

1. Dijkstra 的总览

Dijkstra 解决的是：给定一个源点，求源点到其它所有点的最短距离。

适用条件：

本质理解：

每次从“当前已知距离最小”的点开始扩展。
一旦某个点以全局最小代价弹出，这个点的最短路就被最终确定了。
之后再出现到它的更长路径，都可以忽略。

和 BFS 的关系：

BFS 是“边权都相等”的最短路。
Dijkstra 是“边权非负但不一定相等”的最短路。
01BFS 可以看成 Dijkstra 的特化版。

2. 普通堆实现的 Dijkstra

这是最常用的写法，也是比赛里最容易落地的版本。

（1）核心变量

distance[i]：源点到 i 的当前最短距离估计。
visited[i]：节点 i 是否已经被最终弹出并确定最短路。
小根堆：维护 (节点, 当前距离)，按距离从小到大弹出。

（2）核心流程

初始化时，distance[source] = 0，其余为无穷大。
源点入堆。
每次弹出堆顶 (u, du)。
1. 如果 u 已经被确认过（visited[u] == true），直接跳过。
2. 否则把 u 标记为已确认（visited[u] = true），然后枚举 u 的所有出边 u -> v，边权为 w。
3. 如果 distance[u] + w < distance[v]，就更新 distance[v]，并把 (v, distance[v]) 再次加入堆。
直到堆空为止。

（3）为什么可以重复入堆

普通堆版本不做“原地删改”，而是允许同一个点多次入堆。

新的更优距离会直接压入堆。
旧的较差记录以后弹出时，会被 visited 或“过期状态”直接跳过。

这就是最常见的“懒删除”思想。

（4）复杂度（n表示节点数量，m表示边数量）

常见写法：O((n + m) * log m)，因为每条边最多入堆一次。
也可以近似记作 O(m * log m)

（5）适用场景

想快速写出稳定版本。
不想手写堆的原地更新。
题目数据规模不逼到极致时，这是首选。

3. 反向索引堆优化

反向索引堆的目标，是把“更新堆中某个点的距离”变成 O(log n) 的原地调整，而不是重复插入。

（1）反向索引堆解决什么问题, What is the weakness?

反向索引堆额外维护“点在堆中的位置”，于是就能做到：

某个点第一次进入堆：插入。
某个点距离变小：直接定位到堆中的位置并调整。
某个点一旦弹出：标记为已经确定，之后忽略。

（2）三种状态

通常会给每个点维护位置状态：

-1：从未进堆。
>=0：当前在堆中，且知道它的位置。
-2：已经弹出过，最短路已确定。

（3）核心流程

源点入堆，距离设为 0。
每次弹出堆顶的 (u, du)。
枚举 u 的每条边 u -> v，边权为 w。
1. 如果 v 从未进过堆（状态为 -1），就插入 (v, du + w)。
2. 如果 v 正在堆里（状态为 >=0），且 du + w 更小，就原地更新并上浮/下沉。
3. 如果 v 已经弹出过（状态为 -2），就忽略。

（4）复杂度（n表示节点数量，m表示边数量）

O((n + m) * log n)，因为每条边最多入堆一次。
在一些实现里，它比普通懒删除堆更稳定，也更接近“真正的 decrease-key”。

（5）什么时候值得写

节点数和边数都很大。
需要更严格的常数控制。
题目或模板已经在用反向索引堆。

（6）代码实现

cpp

#include <cstring>
#include <iostream>
using namespace std;
const int N = 1e5 + 5, M = 2e5 + 5;
int head[N], e[M], ne[M], w[M], idx;
int d[N];
int heap[N], pos[N], heapSize;
int n, m, s;
void init() {
  idx = 0;
  memset(head, -1, sizeof(head));
  memset(d, 0x3f, sizeof(d));
  memset(pos, -1, sizeof(pos));
  heapSize = 0;
}
void add(int a, int b, int c) {
  e[idx] = b, ne[idx] = head[a], w[idx] = c, head[a] = idx++;
}
// a 表示点， c表示新的到点a的代价
// pos[a] == -1, 加入
// pos[a] >= 0 判断大小
// pos[a] == -2 已经弹出堆了，忽略
// 小顶堆
void swap2(int a, int b) {
  swap(heap[a], heap[b]);
  pos[heap[a]] = a, pos[heap[b]] = b;
}
// down和down2是两种不同的堆调整写法，功能一样，选一种写就行了
// 小顶堆
void down(int k) {
  int l = 2 * k + 1;
  while (l < heapSize) {
    int best = l + 1 < heapSize && d[heap[l + 1]] < d[heap[l]] ? l + 1 : l;
    best = d[heap[best]] < d[heap[k]] ? best : k;
    if (best == k) { break; }
    swap2(k, best);
    k = best;
    l = 2 * k + 1;
  }
}

void down2(int k) {
  int temp = heap[k];
  int temp_dist = d[heap[k]];
  for (int i = 2 * k + 1; i < heapSize; i = 2 * i + 1) {
    if (i < heapSize - 1 && d[heap[i]] > d[heap[i + 1]]) { i++; }
    if (d[heap[i]] > temp_dist) { break; }
    heap[k] = heap[i];
    pos[heap[k]] = k;
    k = i;
  }
  heap[k] = temp;
  pos[heap[k]] = k;
}
int pop() {
  int ans = heap[0];
  swap2(0, --heapSize);
  down2(0);
  pos[ans] = -2;
  return ans;
}
void up(int k) {
  while (k >= 1 && d[heap[k]] < d[heap[(k - 1) / 2]]) {
    swap2(k, (k - 1) / 2);
    k = (k - 1) / 2;
  }
}

void solve(int a, int c) {
  if (pos[a] == -1) {
    heap[heapSize] = a;
    pos[a] = heapSize++;
    d[a] = c;
    up(pos[a]);
  } else if (pos[a] >= 0) {
    if (d[a] > c) {
      d[a] = c;
      up(pos[a]);
    }
  }
}
int main() {
  int a, b, c;
  scanf("%d%d%d", &n, &m, &s);
  init();
  for (int i = 0; i < m; i++) {
    scanf("%d%d%d", &a, &b, &c);
    add(a, b, c);
  }
  solve(s, 0);
  while (heapSize) {
    int cur = pop();
    for (int i = head[cur]; i != -1; i = ne[i]) { solve(e[i], d[cur] + w[i]); }
  }
  for (int i = 1; i <= n; i++) { printf("%d ", d[i]); }
  return 0;
}

4. Dijkstra 的本质判断

看到题目时，先问三个问题：

是不是“从一个起点到其他点”的最短路？
边权是不是非负？
是不是需要维护“某个状态的最短距离”？

如果答案分别是“是、是、是”，大概率就是 Dijkstra 或它的变种。

5. 分层图最短路

分层图最短路，又叫扩点最短路。

它的核心不是换算法，而是换“图的建模方式”。

（1）核心思想

不要只把“实际位置”当成点，而要把“实际位置 + 状态”一起当成点。

也就是说：

原图中的一个位置，在新图里可能对应多个状态点。
每个状态点之间的边，表示一次状态转移。
然后在这个新图上直接跑 BFS / 01BFS / Dijkstra。

（2）分层图在做什么

分层图本质上就是把原来的点复制多份，按状态分层。

例如：

第 0 层表示没有使用特殊能力。
第 1 层表示已经使用过一次特殊能力。
第 k 层表示使用过 k 次特殊能力。

这样一来，原来“一个点”的问题，就变成了“多层状态点”的问题。

（3）什么时候需要扩点

当题目里出现这些信息时，就要想到状态图：

是否用了某个道具。
已经拿了哪些钥匙。
已经用了几次免费机会。
当前所在方向、颜色、模式、层数。
是否满足某个限制条件。

（4）分层图怎么连边

通常有两类边：

同层边：不改变状态，只在同一层里移动。
跨层边：状态发生变化，从当前层跳到下一层或别的层。

边权怎么定，取决于题目：

如果移动代价都一样，用 BFS。
如果有 0/1 成本，用 01BFS。
如果是非负代价，用 Dijkstra。

（5）分层图最短路的难点

难点不在算法，而在建模：

状态要不要记完整。
每个状态能向哪里转移。
转移代价是多少。
终点状态怎么定义。

只要这四件事想清楚，后面就只是套 BFS / Dijkstra 了。

（6）个人理解：代码层面来说，visited和distance数据的维度始终都是相同的，都是“位置 + 状态”维度的组合

即：visited[position][状态] 和 distance[position][状态]，状态维度的设计，直接决定了分层图的结构和合法路径的定义

6. 本节题目对应关系

Dijkstra 算法模板：普通堆 / 反向索引堆。
最小体力消耗路径：状态图上的最短路，常规做法是 Dijkstra。
水位上升的泳池中游泳：按高度扩展的最短路，典型 Dijkstra。
获取所有钥匙的最短路径：分层图最短路，状态包含“已获得钥匙集合”。
电动车游城市：分层图最短路，状态包含“电量/充电策略”等信息。
飞行路线：分层图最短路，状态包含“免费航线使用次数”。

7. 常见易错点

把有负权边的题直接套 Dijkstra。
普通堆版本忘记处理旧记录，导致重复扩展过多。
反向索引堆没有维护“点在堆中的位置状态”。
分层图里状态设计不完整，导致路径合法性丢失。
状态转移写对了，但终点判断错在“层数”或“钥匙集合”上。
把 BFS、01BFS、Dijkstra 混成一锅，没有先判断边权类型。

8. 题目

题目1
Dijkstra算法模版
普通堆的实现
反向索引堆的实现
测试链接 : https://leetcode.cn/problems/network-delay-time
测试链接 : https://www.luogu.com.cn/problem/P4779




题目2
最小体力消耗路径
你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights
其中 heights[row][col] 表示格子 (row, col) 的高度
一开始你在最左上角的格子 (0, 0) ，且你希望去最右下角的格子 (rows-1, columns-1) 
（注意下标从 0 开始编号）。你每次可以往 上，下，左，右 四个方向之一移动
你想要找到耗费 体力 最小的一条路径
一条路径耗费的体力值是路径上相邻格子之间，高度差绝对值的最大值
请你返回从左上角走到右下角的最小 体力消耗值
测试链接 ：https://leetcode.cn/problems/path-with-minimum-effort/




题目3
水位上升的泳池中游泳
在一个 n x n 的整数矩阵 grid 中
每一个方格的值 grid[i][j] 表示位置 (i, j) 的平台高度
当开始下雨时，在时间为 t 时，水池中的水位为 t
你可以从一个平台游向四周相邻的任意一个平台，但是前提是此时水位必须同时淹没这两个平台
假定你可以瞬间移动无限距离，也就是默认在方格内部游动是不耗时的
当然，在你游泳的时候你必须待在坐标方格里面。
你从坐标方格的左上平台 (0，0) 出发
返回 你到达坐标方格的右下平台 (n-1, n-1) 所需的最少时间
测试链接 : https://leetcode.cn/problems/swim-in-rising-water/


题目4
获取所有钥匙的最短路径
给定一个二维网格 grid ，其中：
'.' 代表一个空房间、'#' 代表一堵墙、’@' 是起点
小写字母代表钥匙、大写字母代表锁
从起点开始出发，一次移动是指向四个基本方向之一行走一个单位空间
不能在网格外面行走，也无法穿过一堵墙
如果途经一个钥匙，我们就把它捡起来。除非我们手里有对应的钥匙，否则无法通过锁。
假设 k 为 钥匙/锁 的个数，且满足 1 <= k <= 6，
字母表中的前 k 个字母在网格中都有自己对应的一个小写和一个大写字母
换言之，每个锁有唯一对应的钥匙，每个钥匙也有唯一对应的锁
另外，代表钥匙和锁的字母互为大小写并按字母顺序排列
返回获取所有钥匙所需要的移动的最少次数。如果无法获取所有钥匙，返回 -1 。
测试链接：https://leetcode.cn/problems/shortest-path-to-get-all-keys


题目5
电动车游城市
小明的电动车电量充满时可行驶距离为 cnt
每行驶 1 单位距离消耗 1 单位电量，且花费 1 单位时间
小明想选择电动车作为代步工具。地图上共有 N 个景点，景点编号为 0 ~ N-1
他将地图信息以 [城市 A 编号,城市 B 编号,两城市间距离] 格式整理在在二维数组 paths，
表示城市 A、B 间存在双向通路。
初始状态，电动车电量为 0。每个城市都设有充电桩，
charge[i] 表示第 i 个城市每充 1 单位电量需要花费的单位时间。
请返回小明最少需要花费多少单位时间从起点城市 start 抵达终点城市 end
测试链接 : https://leetcode.cn/problems/DFPeFJ/


题目6
飞行路线
Alice和Bob现在要乘飞机旅行，他们选择了一家相对便宜的航空公司
该航空公司一共在n个城市设有业务，设这些城市分别标记为0 ~ n−1
一共有m种航线，每种航线连接两个城市，并且航线有一定的价格
Alice 和 Bob 现在要从一个城市沿着航线到达另一个城市，途中可以进行转机
航空公司对他们这次旅行也推出优惠，他们可以免费在最多k种航线上搭乘飞机
那么 Alice 和 Bob 这次出行最少花费多少
测试链接 : https://www.luogu.com.cn/problem/P4568

2026.05.03 20:13

尚同

2026.05.05 20:25

尚同

2026.05.06 14:09

尚同

2026.05.07 15:09

算法讲解065【必备】A*、Floyd、Bellman-Ford 与 SPFA

前置知识

讲解059-建图、链式前向星

讲解062-宽度优先遍历及其扩展

讲解064-Dijkstra 算法、分层图最短路

讲解059~讲解065都是【必备】课程有关图的内容，建议从头开始学习

注意：【必备】标签下的课程都是最基础、最高频的内容，有关图的更多内容会在后续【扩展】、【挺难】标签下讲述。

1. 四种算法的总览与选型

当看到最短路问题时，先判断这几个维度：

维度	Dijkstra	A*	Floyd	Bellman-Ford / SPFA
单源/全对	单源	单源（有目标点）	全对	单源
边权约束	非负	非负	任意（无负环）	任意（无负环）
时间复杂度	O((n+m)logn)	通常更快	O(n³)	O(nm)
适用场景	一般图、无目标优化	有明确目标点	小图、需要任意两点距离	有负权边、小图

选型决策树：

是否有负权边？
- 无 -> Dijkstra（如果有目标点可考虑 A*）
- 有 -> Bellman-Ford/SPFA
是否需要任意两点距离？
- 是 -> Floyd
- 否 -> 看是否有目标点
有明确目标点？
- 是 -> A*（配合好的启发函数）
- 否 -> Dijkstra

2. A* 算法

（1）什么是 A*

A* 是带启发式函数的 Dijkstra。

核心改动：在堆中不再比较 distance[u]，而是比较 distance[u] + h(u, target)。

其中 h(u, target) 是启发函数，表示"当前点 u 到目标点的预估距离"。

（2）启发函数的要求

可以接纳性（Admissibility）：
- 这是保证 A* 找到最优路径的必要条件。
单调性（Consistency）：h(u, v) ≤ distance(u, v) + h(v, target)。
- 更强的条件，保证路径一致性。
越接近越好：在保证可以接纳性的前提下，h 的值越接近真实距离越好。
- 这能减少扩展的节点数，提升速度。

（3）常见启发函数

对于网格或坐标问题：

曼哈顿距离：|x1 - x2| + |y1 - y2|
- 适用于 4 方向移动的网格。
欧式距离：sqrt((x1-x2)² + (y1-y2)²)
- 适用于可以对角移动的场景。
对角线距离：max(|x1-x2|, |y1-y2|)
- 适用于可以自由对角移动的场景。

（4）实现细节

A* 的实现和 Dijkstra 几乎一样，只是改一个排序键：

堆排序键 = distance[u] + h(u, target)

剩余逻辑完全相同。

（5）何时用 A* vs Dijkstra

如果没有明确的目标点，用 Dijkstra。
如果有目标点但网格规模不大，Dijkstra 够用。
如果有目标点且网格很大，A* 能显著减少搜索范围。

3. Floyd 算法

（1）适用场景

Floyd 用来求图中任意两点之间的最短距离。

适用于：

需要查询任意两点最短路的题目。
图中可能有负权边，但没有负环。
图比较小（n ≤ 500）。

（1）核心转移方程

distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])

表示：i 到 j 的距离，可能通过中间点 k 来优化。

（1）为什么要先枚举 k

这是 Floyd 的精妙之处。必须按"枚举 k -> 枚举 i -> 枚举 j"的顺序。

为什么不能先枚举 i、j？

如果先枚举 i、j，那么在计算 distance[i][j] 时，某些中间点 k 的 distance 值可能还没被更新到最优。结果就是拿到了"部分优化后"的 distance，导致结果错误。

为什么这个顺序对？

在枚举 k 时，distance[i][k] 和 distance[k][j] 都是"只经过 0 到 k-1 的点"的最短路。

这就保证了逐层逐层地考虑更多的中间点，最终得到的是通过全部点的最短路。

（3）复杂度与特点

时间复杂度：O( $n^{3}$ )，因为三重循环。
空间复杂度：O( $n^{2}$ )，需要存储任意两点的距离。
常数小，实现简单。

4. Bellman-Ford 算法

（1）核心概念：松弛操作

假设源点为 s，当前 distance[u] 表示 s 到 u 的已知最短距离。

如果存在边 u -> v，权重为 w，且 distance[u] + w < distance[v]，那么说这条边"松弛了"distance[v]。

松弛就是：通过某条边，使某个点的距离估计变得更小。

（2）算法流程

初始化：distance[source] = 0，其余为无穷大。
进行 n-1 轮迭代（n 是点数）。
每轮考察所有边，尝试进行松弛操作。
若某轮发现没有任何边被松弛，可提前终止。

为什么是 n-1 轮？最短路最多经过 n-1 条边。

（3）时间复杂度

O(n * m)，其中 n 是节点数，m 是边数。

在小图上可以接受，大图会超时。

（4）负环检测

在标准 Bellman-Ford 之后，再进行第 n 轮：

如果第 n 轮仍有边被松弛，说明存在可达到的负环。
从源点出发能到达这个负环的点的 distance 值会无限减小。

5. SPFA 优化

（1）核心观察

普通 Bellman-Ford 每轮遍历所有边太浪费。

关键观察：只有距离刚被更新的点，其出边才可能引起进一步的松弛。

所以用队列只维护"这一轮距离变化过的点"，下一轮只检查这些点的出边。

（2）流程

初始化：distance[source] = 0，source 入队。
从队列弹出 u。
枚举 u 的所有出边 u -> v。
若 distance[u] + w < distance[v]，就松弛并将 v 入队（如果 v 还不在队里）。
重复直到队空。

（3）时间复杂度

理论复杂度：O(nm)，和普通 Bellman-Ford 一样。

实际复杂度：在随机图上通常是 O(n + m)，但最坏情况可以很差。

（4） SPFA 的风险

数据卡：某些特殊构造的图会让 SPFA 退化到最坏复杂度。
已死论：网上流传"SPFA 已死"，指的是竞赛圈有人设计数据专门卡 SPFA。
薛定谔的 SPFA：有时候快（AC），有时候慢（TLE）。

（5） SPFA 的适用场景

题目明确有负权边且数据规模小（n ≤ 5000）。
需要判断负环。
没有其他办法时的退路。

（6）何时用 SPFA vs Bellman-Ford

数据小且随机 -> SPFA（优化常数）。
数据大或可能被卡 -> 纯 Bellman-Ford（保险）。
没有负边 -> Dijkstra（必须）。

6. 本节题目对应关系

A* 算法模板：带启发式函数的 Dijkstra，对比验证。
Floyd 算法模板：最短路任意两点、可含负权。
Bellman-Ford 应用：有负权边的单源最短路。
SPFA + 负环检测：找可达的负环。

7. 常见易错点

A 的启发函数过大*：违反可以接纳性，找不到最优路。
Floyd 的枚举顺序：先 i、j 再 k 会导致结果错误。
Bellman-Ford 轮数：少于 n-1 轮会漏掉最短路。
负环判断：需要第 n 轮判断，只判断 n-1 轮找不到。
SPFA 入队重复：需要记录点是否已在队里，避免重复入队。
边的方向：有向图和无向图建边方式不同。

8. 本节题目

题目1
A*算法模版
A*算法 vs Dijkstra算法
采用对数器验证




题目2
Floyd算法模版（洛谷）
测试链接 : https://www.luogu.com.cn/problem/P2910


题目3
Bellman-Ford算法应用（Leetcode）
测试链接 : https://leetcode.cn/problems/cheapest-flights-within-k-stops/


题目4
Bellman-Ford + SPFA优化（洛谷）
给定一个 n个点的有向图
请求出图中是否存在从顶点 1 出发能到达的负环
负环的定义是：一条边权之和为负数的回路。
测试链接 : https://www.luogu.com.cn/problem/P3385

2026.05.10 11:04

尚同

算法总结

浅记

NOTE

对于一个网格图，使用广度优先遍历的时候，visited 数组的标记时机非常重要，

而对于使用Dijkstra算法的题目，使用优先级队列时，

杂

画图：所有图算法进行对比，包括时间复杂度、空间复杂度、适用条件、核心思想、代码模板等维度的对比总结。

在线Debug 时间限制（2s）

https://www.acwing.com/problem/content/4903/

相似题目

https://leetcode.cn/problems/trapping-rain-water/

https://leetcode.cn/problems/container-with-most-water/

https://leetcode.cn/problems/trapping-rain-water-ii/

https://leetcode.cn/problems/largest-rectangle-in-histogram

左神学习笔记2 ​

2026.01.25 11:24 ​

算法讲解049【必备】滑动窗口技巧与相关题目 ​

2026.02.01 22:45 ​

算法讲解050【必备】双指针技巧与相关题目 ​

2026.02.03 22:34 ​

2026.02.04 16:36 ​

算法讲解051【必备】二分答案法与相关题目 ​

2026.02.11 15:54 ​

2026.02.16 20:52 ​

算法讲解052【必备】单调栈-上 ​

2026.02.17 22:57 ​

2026.02.27 17:35 ​

单调栈-下 ​

2026.03.02 22:38 ​

2026.03.19 19:27 ​

算法讲解054【必备】单调队列-上 ​

2026.3.23 20:30 ​

算法讲解055【必备】单调队列-下 ​

2026.03.24 18:38 ​

2026.03.26 17:10 ​

算法讲解056【必备】并查集-上 ​

前置知识 : 无 ​

优化 ​

2026.03.28 19:59 ​

算法讲解057【必备】并查集-下 ​

2026.03.30 18:16 ​

2026.04.12 18:25 ​

算法讲解058【必备】洪水填充 ​

2026.04.13 14:47 ​

算法讲解059【必备】建图、链式前向星、拓扑排序 ​

（1）总体知识点 ​

（2）图的三种表示 ​

（3）链式前向星 ​

头插法模板 ​

使用方式 ​

常见注意点 ​

（4）拓扑排序 ​

（5）题目对应 ​

2026.04.13 20:07 ​

算法讲解060【必备】拓扑排序的扩展技巧 ​

2026.04.14 16:05 ​

2026.04.15 11:52 ​

算法讲解061【必备】最小生成树 ​

1. Kruskal算法（最常用） ​

2. Prim算法（不算常用） ​

3. 代码实现 ​

3.1 Kruskal算法： ​

3.2 Prim算法 ​

9. 题目 ​

2026.04.16 19:46 ​

2026.04.21 19:23 ​

算法讲解062【必备】宽度优先遍历及其扩展 ​

前置知识 ​

1. 宽度优先遍历总览 ​

2. 单源 BFS 与多源 BFS ​

2.1 单源 BFS 模板思维 ​

2.2 多源 BFS 模板思维 ​

3. 01BFS（双端队列） ​

4. 宽度优先遍历与优先级队列结合 ​

5. BFS 与 DFS 结合生成所有最短路径 ​

6. 网格 BFS 常见实现细节 ​

7. 易错点总结 ​

8. 本节题目与方法映射 ​

4. 题目 ​

2026.04.22 11:15 ​

2026.04.22 19:10 ​

算法讲解063【必备】双向广搜 ​

前置知识 ​

算法讲解 ​

题目 ​

2026.04.24 19:48 ​

2026.04.28 11:02 ​

算法讲解064【必备】Dijkstra算法、分层图最短路 ​

前置知识 ​

1. Dijkstra 的总览 ​

2. 普通堆实现的 Dijkstra ​

3. 反向索引堆优化 ​

4. Dijkstra 的本质判断 ​

5. 分层图最短路 ​

左神学习笔记2

2026.01.25 11:24

算法讲解049【必备】滑动窗口技巧与相关题目

2026.02.01 22:45

算法讲解050【必备】双指针技巧与相关题目

2026.02.03 22:34

2026.02.04 16:36

算法讲解051【必备】二分答案法与相关题目

2026.02.11 15:54

2026.02.16 20:52

算法讲解052【必备】单调栈-上

2026.02.17 22:57

2026.02.27 17:35

单调栈-下

2026.03.02 22:38

2026.03.19 19:27

算法讲解054【必备】单调队列-上

2026.3.23 20:30

算法讲解055【必备】单调队列-下

2026.03.24 18:38

2026.03.26 17:10

算法讲解056【必备】并查集-上

前置知识 : 无

优化

2026.03.28 19:59

算法讲解057【必备】并查集-下

2026.03.30 18:16

2026.04.12 18:25

算法讲解058【必备】洪水填充

2026.04.13 14:47

算法讲解059【必备】建图、链式前向星、拓扑排序

（1）总体知识点

（2）图的三种表示

（3）链式前向星

头插法模板

使用方式

常见注意点

（4）拓扑排序

（5）题目对应

2026.04.13 20:07

算法讲解060【必备】拓扑排序的扩展技巧

2026.04.14 16:05

2026.04.15 11:52

算法讲解061【必备】最小生成树

1. Kruskal算法（最常用）

2. Prim算法（不算常用）

3. 代码实现

3.1 Kruskal算法：

3.2 Prim算法

9. 题目

2026.04.16 19:46

2026.04.21 19:23

算法讲解062【必备】宽度优先遍历及其扩展

前置知识

1. 宽度优先遍历总览

2. 单源 BFS 与多源 BFS

2.1 单源 BFS 模板思维

2.2 多源 BFS 模板思维

3. 01BFS（双端队列）

4. 宽度优先遍历与优先级队列结合

5. BFS 与 DFS 结合生成所有最短路径

6. 网格 BFS 常见实现细节

7. 易错点总结

8. 本节题目与方法映射

4. 题目

2026.04.22 11:15

2026.04.22 19:10

算法讲解063【必备】双向广搜

前置知识

算法讲解

题目

2026.04.24 19:48

2026.04.28 11:02

算法讲解064【必备】Dijkstra算法、分层图最短路

前置知识

1. Dijkstra 的总览

2. 普通堆实现的 Dijkstra

3. 反向索引堆优化

4. Dijkstra 的本质判断

5. 分层图最短路