力扣hot100—系列9—图论

这四道题是非常经典的图论/树结构入门必刷题，刚好涵盖了四大核心考点：DFS（深度优先搜索）、BFS（广度优先搜索）、拓扑排序、字典树。

1. 岛屿数量 (Number of Islands)

核心考点：DFS (深度优先搜索) 或 BFS (广度优先搜索)

💡 直观理解：“填海造陆” 或 “踩雷游戏”

想象你站在一个由格子组成的地图上，地图里有陆地（'1'）和水（'0'）。
你想知道一共有几个岛。你可以这样做：

1. 挨个格子找，只要一看到陆地（'1'），岛屿数量就 + 1。
2. 但是为了避免下次再数到同一个岛的另一块地，你每发现一块陆地，就施展“魔法”，顺藤摸瓜把和它连在一起的所有陆地都变成水（'0'）。
3. 接着继续往下找，直到整个地图都被遍历完。

🧠 解题思路 (DFS)

这种“顺藤摸瓜，一路走到黑”的思路就是 DFS。

1. 遍历二维数组。
2. 遇到'1'时，触发 DFS 函数，并将岛屿计数器 +1。
3. DFS 函数内部：检查当前是否越界、是否是水，如果是则停止。如果是陆地，就把它置为'0'，然后递归调用上下左右四个方向。

💻 代码实现

classSolution:defnumIslands(self,grid:list[list[str]])->int:ifnotgrid:return0count=0rows,cols=len(grid),len(grid[0])# 定义 DFS 魔法函数：负责把连在一起的陆地全变成水defdfs(r,c):# 如果越界了，或者当前是水('0')，就停止搜索ifr<0orc<0orr>=rowsorc>=colsorgrid[r][c]=='0':return# 把当前陆地变成水，防止重复遍历grid[r][c]='0'# 顺藤摸瓜，向上下左右四个方向扩散dfs(r-1,c)# 上dfs(r+1,c)# 下dfs(r,c-1)# 左dfs(r,c+1)# 右# 遍历整个地图forrinrange(rows):forcinrange(cols):ifgrid[r][c]=='1':# 发现新大陆！count+=1# 岛屿数量 +1dfs(r,c)# 发动魔法，把这个岛全部淹没returncount

2. 腐烂的橘子 (Rotting Oranges)

核心考点：多源 BFS (广度优先搜索)

💡 直观理解：“丧尸病毒爆发”

一开始有几个坏橘子（丧尸），有很多好橘子（平民）。
丧尸病毒每一分钟都会向上下左右扩散一层。问：所有平民都变成丧尸需要多久？如果有平民永远感染不到（比如被墙/空格子隔开了），就返回 -1。
注意！这里不能用 DFS（一路走到黑），因为病毒是所有坏橘子同时、一圈一圈往外扩散的。这种“像水波纹一样一层层扩散”的思路就是 BFS。

🧠 解题思路

1. 找出第一分钟所有的“初始坏橘子”，把它们的坐标放进一个队列（排队等着去感染别人）。同时数一下一共有多少个好橘子。
2. 开始按分钟计时：每次把队列里当前的坏橘子全拿出来，向四周感染。
3. 感染到一个好橘子，好橘子就变坏了（加入下一轮的队列中），并且好橘子的总数 -1。
4. 直到队列空了，看看好橘子总数是不是 0。如果是，返回分钟数；如果还有好橘子没被感染，返回 -1。

💻 代码实现

fromcollectionsimportdequeclassSolution:deforangesRotting(self,grid:list[list[int]])->int:rows,cols=len(grid),len(grid[0])queue=deque()fresh_count=0# 1. 扫描整个橘子林，记录新鲜橘子数量，把腐烂橘子放进队列forrinrange(rows):forcinrange(cols):ifgrid[r][c]==2:queue.append((r,c))# 烂橘子入队elifgrid[r][c]==1:fresh_count+=1# 统计好橘子# 如果本来就没有好橘子，直接返回 0 分钟iffresh_count==0:return0minutes=0directions=[(-1,0),(1,0),(0,-1),(0,1)]# 上下左右# 2. 开始 BFS 病毒扩散whilequeueandfresh_count>0:minutes+=1# 这一分钟内，当前队列里的所有烂橘子同时向外发威for_inrange(len(queue)):r,c=queue.popleft()fordr,dcindirections:nr,nc=r+dr,c+dc# 如果旁边是新鲜橘子，感染它！if0<=nr<rowsand0<=nc<colsandgrid[nr][nc]==1:grid[nr][nc]=2# 变烂fresh_count-=1# 新鲜橘子减少queue.append((nr,nc))# 新烂的橘子进队列，下一分钟它也要去感染别人# 3. 检查是否还有好橘子幸存returnminutesiffresh_count==0else-1

3. 课程表 (Course Schedule)

核心考点：拓扑排序 (有向图寻找环)

💡 直观理解：“游戏技能树” 或 “大学排课”

你想学课程 A，但必须先修完课程 B 和 C。
你可以把前置条件看作一个**“欠债数量”（专业术语叫：入度 In-degree）**。

• 如果一门课没有任何前置课程，它的入度为 0。这种课你可以直接学！
• 当你学完这门课，依赖它的那些后续课程的“欠债数量”就可以 -1。
• 只要有课的欠债数量变成 0 了，你就可以继续学。
• 如果最后所有课都学完了，说明可以排好课；如果有些课一直没法学（比如互相依赖的死循环：A需要B，B又需要A），就返回 False。

🧠 解题思路

1. 统计入度与构建依赖表：用一个数组in_degree记录每门课有几个前置课；用一个字典adj记录学完某门课能解锁哪些后续课。
2. 把所有入度为 0（没有前置条件可以直接上）的课放进队列。
3. 从队列中取出课程，每取出一门，就相当于学完了。把这门课能解锁的后续课程的入度减 1。
4. 只要后续课程入度变为 0 了，就把后续课程放进队列。
5. 最后看看学完的课程总数等不等于numCourses。

💻 代码实现

fromcollectionsimportdeque,defaultdictclassSolution:defcanFinish(self,numCourses:int,prerequisites:list[list[int]])->bool:# in_degree 记录每门课的“前置要求数量” (欠债数)in_degree=[0]*numCourses# adj 记录学完某门课可以解锁哪些课 {先修课: [后续课1, 后续课2]}adj=defaultdict(list)# 1. 整理依赖关系forcur,preinprerequisites:in_degree[cur]+=1# 想学 cur，先修课多了一门，入度 +1adj[pre].append(cur)# 学完 pre，可以解锁 cur 的进度# 2. 把所有没有先修要求的课（入度为0）放入队列queue=deque()foriinrange(numCourses):ifin_degree[i]==0:queue.append(i)learned_count=0# 3. 开始一门门上课whilequeue:course=queue.popleft()# 上完了一门课learned_count+=1# 把这门课对应的后续课程的进度解锁（入度 -1）fornext_courseinadj[course]:in_degree[next_course]-=1# 如果某门后续课的前置要求都满足了，就可以排进上课计划了ifin_degree[next_course]==0:queue.append(next_course)# 4. 判断上完的课是不是等于总课数returnlearned_count==numCourses

4. 实现 Trie (前缀树)

核心考点：树结构的设计

💡 直观理解：“带有书签的纸质字典”

怎么在字典里查单词 “APPLE”？
你不会一页页翻，而是先翻到A这一部分，然后再找P，再找P，再找L，最后是E。
前缀树也是这个逻辑：

• 我们不需要把单词整体存起来。
• 根节点是空白的。根节点往下有 26 个可能的字母分叉。
• 每个字母节点不仅包含它自己是谁，还要记录：这里是不是某个单词的结尾？（比如存了 “APP”，在最后一个 P 的节点打个勾 ✅，表示这里是一个完整单词）。

🧠 解题思路

1. 先定义一个“字典树节点类TrieNode”：包含一个存储子节点的字典/数组，和一个布尔值is_word（标记是否是单词结尾）。
2. 插入单词：遍历单词的每个字符，顺着树往下走，如果没有这个字母的子节点，就新建一个。走到最后，把最后一个节点的is_word设为 True。
3. 查找单词：遍历单词每个字符，顺着树走，如果断了说明没这个词，直接 False。如果走到底，返回当前节点的is_word（防止树里有 “APPLE” 但你搜 “APP”，“APP” 不是一个存过的单词，只是前缀）。
4. 查找前缀：和上面一样，只要前缀走到底不断开，就直接返回 True（有这个前缀就行，管他是不是完整单词）。

💻 代码实现

# 1. 先定义节点classTrieNode:def__init__(self):self.children={}# 记录后续的字母节点self.is_word=False# 标记这里是否是一个单词的结尾classTrie:def__init__(self):# 初始化根节点，根节点是个空盒子self.root=TrieNode()definsert(self,word:str)->None:node=self.rootforcharinword:# 如果当前字母不在子节点里，就新建一页“书签”ifcharnotinnode.children:node.children[char]=TrieNode()# 顺着这页“书签”往下走node=node.children[char]# 单词全部插入完后，在最后一个字母节点打上标记，表示这里是一个完整单词node.is_word=Truedefsearch(self,word:str)->bool:node=self.rootforcharinword:# 查着查着发现路断了，说明字典里根本没有这个词ifcharnotinnode.children:returnFalsenode=node.children[char]# 找到了所有字母，但还要看这里到底是不是一个被标记过的完整单词returnnode.is_worddefstartsWith(self,prefix:str)->bool:node=self.rootforcharinprefix:ifcharnotinnode.children:returnFalsenode=node.children[char]# 只要能顺着前缀走通，不管它是不是完整单词，都说明有这个前缀returnTrue

总结

这四道题是非常完美的入门台阶：

1. 岛屿教你什么是“从一个点出发一条道走到黑”（DFS）。
2. 橘子教你什么是“多点同时出发，一层层往外扩”（BFS）。
3. 课程表带你认识“有向图”并运用了队列（拓扑排序）。
4. Trie树打破你对字符串查找的常规认识，引入空间换时间的数据结构设计。

第一次刷题不用死磕最优解，把这四道题的比喻（填海、丧尸、技能树、查字典）记在脑子里，自己手敲一遍上面的代码，体会其中逻辑是如何跑通的，就算完美过关了！加油！