这四道题是非常经典的图论/树结构入门必刷题刚好涵盖了四大核心考点DFS深度优先搜索、BFS广度优先搜索、拓扑排序、字典树。1. 岛屿数量 (Number of Islands)核心考点DFS (深度优先搜索) 或 BFS (广度优先搜索) 直观理解“填海造陆” 或 “踩雷游戏”想象你站在一个由格子组成的地图上地图里有陆地1和水0。你想知道一共有几个岛。你可以这样做挨个格子找只要一看到陆地1岛屿数量就 1。但是为了避免下次再数到同一个岛的另一块地你每发现一块陆地就施展“魔法”顺藤摸瓜把和它连在一起的所有陆地都变成水0。接着继续往下找直到整个地图都被遍历完。 解题思路 (DFS)这种“顺藤摸瓜一路走到黑”的思路就是 DFS。遍历二维数组。遇到1时触发 DFS 函数并将岛屿计数器 1。DFS 函数内部检查当前是否越界、是否是水如果是则停止。如果是陆地就把它置为0然后递归调用上下左右四个方向。 代码实现classSolution:defnumIslands(self,grid:list[list[str]])-int:ifnotgrid:return0count0rows,colslen(grid),len(grid[0])# 定义 DFS 魔法函数负责把连在一起的陆地全变成水defdfs(r,c):# 如果越界了或者当前是水(0)就停止搜索ifr0orc0orrrowsorccolsorgrid[r][c]0:return# 把当前陆地变成水防止重复遍历grid[r][c]0# 顺藤摸瓜向上下左右四个方向扩散dfs(r-1,c)# 上dfs(r1,c)# 下dfs(r,c-1)# 左dfs(r,c1)# 右# 遍历整个地图forrinrange(rows):forcinrange(cols):ifgrid[r][c]1:# 发现新大陆count1# 岛屿数量 1dfs(r,c)# 发动魔法把这个岛全部淹没returncount2. 腐烂的橘子 (Rotting Oranges)核心考点多源 BFS (广度优先搜索) 直观理解“丧尸病毒爆发”一开始有几个坏橘子丧尸有很多好橘子平民。丧尸病毒每一分钟都会向上下左右扩散一层。问所有平民都变成丧尸需要多久如果有平民永远感染不到比如被墙/空格子隔开了就返回 -1。注意这里不能用 DFS一路走到黑因为病毒是所有坏橘子同时、一圈一圈往外扩散的。这种“像水波纹一样一层层扩散”的思路就是 BFS。 解题思路找出第一分钟所有的“初始坏橘子”把它们的坐标放进一个队列排队等着去感染别人。同时数一下一共有多少个好橘子。开始按分钟计时每次把队列里当前的坏橘子全拿出来向四周感染。感染到一个好橘子好橘子就变坏了加入下一轮的队列中并且好橘子的总数 -1。直到队列空了看看好橘子总数是不是 0。如果是返回分钟数如果还有好橘子没被感染返回 -1。 代码实现fromcollectionsimportdequeclassSolution:deforangesRotting(self,grid:list[list[int]])-int:rows,colslen(grid),len(grid[0])queuedeque()fresh_count0# 1. 扫描整个橘子林记录新鲜橘子数量把腐烂橘子放进队列forrinrange(rows):forcinrange(cols):ifgrid[r][c]2:queue.append((r,c))# 烂橘子入队elifgrid[r][c]1:fresh_count1# 统计好橘子# 如果本来就没有好橘子直接返回 0 分钟iffresh_count0:return0minutes0directions[(-1,0),(1,0),(0,-1),(0,1)]# 上下左右# 2. 开始 BFS 病毒扩散whilequeueandfresh_count0:minutes1# 这一分钟内当前队列里的所有烂橘子同时向外发威for_inrange(len(queue)):r,cqueue.popleft()fordr,dcindirections:nr,ncrdr,cdc# 如果旁边是新鲜橘子感染它if0nrrowsand0nccolsandgrid[nr][nc]1:grid[nr][nc]2# 变烂fresh_count-1# 新鲜橘子减少queue.append((nr,nc))# 新烂的橘子进队列下一分钟它也要去感染别人# 3. 检查是否还有好橘子幸存returnminutesiffresh_count0else-13. 课程表 (Course Schedule)核心考点拓扑排序 (有向图寻找环) 直观理解“游戏技能树” 或 “大学排课”你想学课程 A但必须先修完课程 B 和 C。你可以把前置条件看作一个**“欠债数量”专业术语叫入度 In-degree**。如果一门课没有任何前置课程它的入度为 0。这种课你可以直接学当你学完这门课依赖它的那些后续课程的“欠债数量”就可以 -1。只要有课的欠债数量变成 0 了你就可以继续学。如果最后所有课都学完了说明可以排好课如果有些课一直没法学比如互相依赖的死循环A需要BB又需要A就返回 False。 解题思路统计入度与构建依赖表用一个数组in_degree记录每门课有几个前置课用一个字典adj记录学完某门课能解锁哪些后续课。把所有入度为 0没有前置条件可以直接上的课放进队列。从队列中取出课程每取出一门就相当于学完了。把这门课能解锁的后续课程的入度减 1。只要后续课程入度变为 0 了就把后续课程放进队列。最后看看学完的课程总数等不等于numCourses。 代码实现fromcollectionsimportdeque,defaultdictclassSolution:defcanFinish(self,numCourses:int,prerequisites:list[list[int]])-bool:# in_degree 记录每门课的“前置要求数量” (欠债数)in_degree[0]*numCourses# adj 记录学完某门课可以解锁哪些课 {先修课: [后续课1, 后续课2]}adjdefaultdict(list)# 1. 整理依赖关系forcur,preinprerequisites:in_degree[cur]1# 想学 cur先修课多了一门入度 1adj[pre].append(cur)# 学完 pre可以解锁 cur 的进度# 2. 把所有没有先修要求的课入度为0放入队列queuedeque()foriinrange(numCourses):ifin_degree[i]0:queue.append(i)learned_count0# 3. 开始一门门上课whilequeue:coursequeue.popleft()# 上完了一门课learned_count1# 把这门课对应的后续课程的进度解锁入度 -1fornext_courseinadj[course]:in_degree[next_course]-1# 如果某门后续课的前置要求都满足了就可以排进上课计划了ifin_degree[next_course]0:queue.append(next_course)# 4. 判断上完的课是不是等于总课数returnlearned_countnumCourses4. 实现 Trie (前缀树)核心考点树结构的设计 直观理解“带有书签的纸质字典”怎么在字典里查单词 “APPLE”你不会一页页翻而是先翻到A这一部分然后再找P再找P再找L最后是E。前缀树也是这个逻辑我们不需要把单词整体存起来。根节点是空白的。根节点往下有 26 个可能的字母分叉。每个字母节点不仅包含它自己是谁还要记录这里是不是某个单词的结尾比如存了 “APP”在最后一个 P 的节点打个勾 ✅表示这里是一个完整单词。 解题思路先定义一个“字典树节点类TrieNode”包含一个存储子节点的字典/数组和一个布尔值is_word标记是否是单词结尾。插入单词遍历单词的每个字符顺着树往下走如果没有这个字母的子节点就新建一个。走到最后把最后一个节点的is_word设为 True。查找单词遍历单词每个字符顺着树走如果断了说明没这个词直接 False。如果走到底返回当前节点的is_word防止树里有 “APPLE” 但你搜 “APP”“APP” 不是一个存过的单词只是前缀。查找前缀和上面一样只要前缀走到底不断开就直接返回 True有这个前缀就行管他是不是完整单词。 代码实现# 1. 先定义节点classTrieNode:def__init__(self):self.children{}# 记录后续的字母节点self.is_wordFalse# 标记这里是否是一个单词的结尾classTrie:def__init__(self):# 初始化根节点根节点是个空盒子self.rootTrieNode()definsert(self,word:str)-None:nodeself.rootforcharinword:# 如果当前字母不在子节点里就新建一页“书签”ifcharnotinnode.children:node.children[char]TrieNode()# 顺着这页“书签”往下走nodenode.children[char]# 单词全部插入完后在最后一个字母节点打上标记表示这里是一个完整单词node.is_wordTruedefsearch(self,word:str)-bool:nodeself.rootforcharinword:# 查着查着发现路断了说明字典里根本没有这个词ifcharnotinnode.children:returnFalsenodenode.children[char]# 找到了所有字母但还要看这里到底是不是一个被标记过的完整单词returnnode.is_worddefstartsWith(self,prefix:str)-bool:nodeself.rootforcharinprefix:ifcharnotinnode.children:returnFalsenodenode.children[char]# 只要能顺着前缀走通不管它是不是完整单词都说明有这个前缀returnTrue总结这四道题是非常完美的入门台阶岛屿教你什么是“从一个点出发一条道走到黑”DFS。橘子教你什么是“多点同时出发一层层往外扩”BFS。课程表带你认识“有向图”并运用了队列拓扑排序。Trie树打破你对字符串查找的常规认识引入空间换时间的数据结构设计。第一次刷题不用死磕最优解把这四道题的比喻填海、丧尸、技能树、查字典记在脑子里自己手敲一遍上面的代码体会其中逻辑是如何跑通的就算完美过关了加油