手撕hot100之图论！看完这篇就AC~（二）

1 题目

207. 课程表

你这个学期必须选修numCourses门课程，记为0到numCourses - 1。

在选修某些课程之前需要一些先修课程。 先修课程按数组prerequisites给出，其中prerequisites[i] = [ai, bi]，表示如果要学习课程ai则必须先学习课程bi。

• 例如，先修课程对[0, 1]表示：想要学习课程0，你需要先完成课程1。

请你判断是否可能完成所有课程的学习？如果可以，返回true；否则，返回false。

示例 1：

输入：numCourses = 2, prerequisites = [[1,0]]输出：true解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。

示例 2：

输入：numCourses = 2, prerequisites = [[1,0],[0,1]]输出：false解释：总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。

提示：

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= 5000
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• prerequisites[i]中的所有课程对互不相同

2 代码实现

思考

这啥意思，这和dfs bfs 有什么关系，首尾相接吗？

题解

c++

class Solution { public: bool canFinish(int numCourses, vector<vector<int>>& prerequisites) { vector<vector<int>> graph(numCourses); vector<int> inDegree (numCourses , 0 ); for (auto &edge : prerequisites){ int a = edge[0]; int b = edge[1]; graph[b].push_back(a); inDegree[a] ++; } queue <int> q ; for (int i = 0 ; i < numCourses ; i ++){ if (inDegree[i] == 0 ){ q.push(i); } } int count = 0 ; while (!q.empty()){ int cur = q.front(); q.pop(); count ++; for (int next : graph[cur]){ inDegree[next] --; if (inDegree[next] == 0){ q.push(next); } } } return count == numCourses ; } };

java

class Solution { public boolean canFinish(int numCourses, int[][] prerequisites) { List<List<Integer>> graph = new ArrayList <> (numCourses); for (int i = 0 ; i < numCourses ; i++){ graph.add(new ArrayList<>()); } int [] inDegree = new int[numCourses]; for ( int [] edge : prerequisites){ int a = edge[0]; int b = edge[1]; graph.get(b).add(a); inDegree[a]++; } Queue<Integer> queue = new LinkedList<>(); for (int i = 0 ; i < numCourses ; i ++){ if (inDegree[i] == 0 ){ queue.offer(i); } } int count = 0 ; while (!queue.isEmpty()){ int cur = queue.poll(); count ++ ; for (int next : graph.get(cur)){ inDegree[next] -- ; if (inDegree[next] == 0 ){ queue.offer(next); } } } return count == numCourses ; } }

prerequisites[i] = [a, b]：学 a 之前必须先学 b

等价于：b → a，建立一条有向边：b 指向 a

例子[1,0]：学 1 先要学 0 →0 → 1

整个问题等价于：给定一个有向图，判断图中是否存在环。

有环 ⇒ 无法完成课程（返回 false）；无环 ⇒ 可以完成（返回 true）

比如[1,0],[0,1]：0→1，1→0，形成环，互相等待，无法学习。

知识点：有向图判环，经典两种算法

1. BFS：拓扑排序（Kahn 算法）
2. DFS：深度优先遍历，标记访问状态，寻找回边

方法 1：BFS 拓扑排序（Kahn 算法，最容易理解）

思路

1. 建图：邻接表保存有向边
2. 统计每个节点入度（有多少门课需要在它前面学）
3. 把入度 = 0的课程入队列（不需要先修课，可以直接学）
4. 不断取出队首课程，学完之后：
   • 它指向的后继课程入度 - 1
   • 如果后继入度变成 0，入队
5. 统计一共学了多少门课
   • 学到课程总数 == numCourses：无环 return true
   • 小于 numCourses：存在环 return false

C++

#include <iostream> #include <vector> #include <queue> using namespace std; class Solution { public: bool canFinish(int numCourses, vector<vector<int>>& prerequisites) { // 1.邻接表建图 vector<vector<int>> graph(numCourses); // 入度数组 vector<int> inDegree(numCourses, 0); for(auto& edge : prerequisites){ int a = edge[0]; int b = edge[1]; // [a,b] 学a先学b => b -> a graph[b].push_back(a); inDegree[a]++; // a的入度+1 } queue<int> q; // 入度为0的节点入队 for(int i = 0; i < numCourses; i++){ if(inDegree[i] == 0){ q.push(i); } } int count = 0; // 能学习的课程数量 while(!q.empty()){ int cur = q.front(); q.pop(); count++; // 遍历当前课程所有后继 for(int next : graph[cur]){ inDegree[next]--; if(inDegree[next] == 0){ q.push(next); } } } // 能学完所有课程 = 无环 return count == numCourses; } }; int main(){ Solution sol; vector<vector<int>> pre1 = {{1,0}}; cout << sol.canFinish(2, pre1) << endl; // 1 true vector<vector<int>> pre2 = {{1,0},{0,1}}; cout << sol.canFinish(2, pre2) << endl; // 0 false return 0; }

方法 2：DFS 有向图判环

思路

每个节点三种状态：0 = 未访问1 = 正在当前递归路径中（递归栈里）2 = 已经访问完成

遍历每个节点：遇到状态 1 ⇒ 找到环，直接返回 false遇到状态 2 ⇒ 跳过未访问：标记为 1，递归遍历所有邻居；递归结束标记为 2

C++

#include <iostream> #include <vector> using namespace std; class Solution { public: bool canFinish(int numCourses, vector<vector<int>>& prerequisites) { vector<vector<int>> graph(numCourses); // 0未访问 1访问中 2访问完成 vector<int> visited(numCourses, 0); // 建图 for(auto& e : prerequisites){ int a = e[0], b = e[1]; graph[b].push_back(a); } for(int i = 0; i < numCourses; i++){ if(visited[i] == 0){ if(dfs(i, graph, visited)){ // 发现环 return false; } } } return true; } // 返回true代表找到环 bool dfs(int cur, vector<vector<int>>& graph, vector<int>& visited){ if(visited[cur] == 1) return true; // 出现环 if(visited[cur] == 2) return false; visited[cur] = 1; // 标记正在访问 for(int next : graph[cur]){ if(dfs(next, graph, visited)){ return true; } } visited[cur] = 2; // 处理完毕 return false; } };

关键疑问解答

1. 和 DFS/BFS 是什么关系？

课程依赖构成有向图

• BFS/DFS 就是用来遍历整张图，检测是否存在环路
• 无环有向图 = DAG，可以拓扑排序（可以排学习顺序）

2. 什么叫首尾相接？

首尾相接就是环：0→1，1→0，从 0 出发绕一圈回到 0，就是环路。一旦存在环路，课程互相前置，永远无法完成。

3. 边千万不要建反！

题目[a,b]：学 a 先要学 b✅ 正确边：b → a❌ 很多新手写成a→b，代码直接全部出错！

复杂度说明

• n=numCourses，m=prerequisites.size()
• 时间：O (n+m)，每个点、每条边只遍历一次
• 空间：O (n+m)，邻接表存储图

如果你想要，我可以一步一步模拟样例numCourses=2, [[1,0],[0,1]]的 BFS 执行流程，直观看懂为什么检测出环。

3 题目

208. 实现 Trie (前缀树)

Trie（发音类似 "try"）或者说前缀树是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。

请你实现 Trie 类：

• Trie()初始化前缀树对象。
• void insert(String word)向前缀树中插入字符串word。
• boolean search(String word)如果字符串word在前缀树中，返回true（即，在检索之前已经插入）；否则，返回false。
• boolean startsWith(String prefix)如果之前已经插入的字符串word的前缀之一为prefix，返回true；否则，返回false。

示例：

输入["Trie", "insert", "search", "search", "startsWith", "insert", "search"] [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]输出[null, null, true, false, true, null, true]解释Trie trie = new Trie(); trie.insert("apple"); trie.search("apple"); // 返回 True trie.search("app"); // 返回 False trie.startsWith("app"); // 返回 True trie.insert("app"); trie.search("app"); // 返回 True

提示：

• 1 <= word.length, prefix.length <= 2000
• word和prefix仅由小写英文字母组成
• insert、search和startsWith调用次数总计不超过3 * 104次

4 代码实现

思考

好难我感觉一点都看不懂。。。。

题解

c++

struct TrieNode { TrieNode* children[26]; bool isEnd; TrieNode() { // 全部初始化为空指针 memset(children, 0, sizeof(children)); isEnd = false; } }; class Trie { private: TrieNode* root; public: // 构造函数：创建根节点 Trie() { root = new TrieNode(); } // 插入单词 void insert(string word) { TrieNode* cur = root; for (char c : word) { int idx = c - 'a'; if (!cur->children[idx]) { cur->children[idx] = new TrieNode(); } cur = cur->children[idx]; } cur->isEnd = true; } // 查找完整单词 bool search(string word) { TrieNode* cur = root; for (char c : word) { int idx = c - 'a'; if (!cur->children[idx]) { return false; } cur = cur->children[idx]; } return cur->isEnd; } // 判断是否存在该前缀 bool startsWith(string prefix) { TrieNode* cur = root; for (char c : prefix) { int idx = c - 'a'; if (!cur->children[idx]) { return false; } cur = cur->children[idx]; } return true; } }; /** * Your Trie object will be instantiated and called as such: * Trie* obj = new Trie(); * obj->insert(word); * bool param_2 = obj->search(word); * bool param_3 = obj->startsWith(prefix); */

java

class TrieNode { // 26个小写英文字母 TrieNode[] children; boolean isEnd; public TrieNode() { children = new TrieNode[26]; isEnd = false; } } class Trie { private TrieNode root; public Trie() { root = new TrieNode(); } // 插入单词 public void insert(String word) { TrieNode cur = root; for (char c : word.toCharArray()) { int idx = c - 'a'; if (cur.children[idx] == null) { cur.children[idx] = new TrieNode(); } cur = cur.children[idx]; } cur.isEnd = true; } // 查找完整单词，必须匹配完整单词 public boolean search(String word) { TrieNode cur = root; for (char c : word.toCharArray()) { int idx = c - 'a'; if (cur.children[idx] == null) { return false; } cur = cur.children[idx]; } return cur.isEnd; } // 判断是否存在以prefix为前缀的单词 public boolean startsWith(String prefix) { TrieNode cur = root; for (char c : prefix.toCharArray()) { int idx = c - 'a'; if (cur.children[idx] == null) { return false; } cur = cur.children[idx]; } return true; } } /** * Your Trie object will be instantiated and called as such: * Trie obj = new Trie(); * obj.insert(word); * boolean param_2 = obj.search(word); * boolean param_3 = obj.startsWith(prefix); */

先抓核心思想，再看代码，最后拆解易错点。

一、什么是前缀树（Trie）

普通存储单词：apple、app直接存两个完整字符串，查找前缀效率低。 前缀树思想：共享公共前缀apple和app共用a → p → p这条路径。

规则：

1. 树上不存完整单词，路径代表字符
2. 每一个节点，最多有 26 条出路（小写字母 a~z）
3. 关键标记：isEnd
   • isEnd = true：走到这个节点，代表到此是一个完整单词
   • isEnd = false：只是中间前缀，不是单词

举例子： 插入apple路径：root →a→p→p→l→ee节点isEnd = true第三个p的isEnd = false此时：

• search ("app") → 能走到第三个 p，但isEnd=false→ 返回 false
• startsWith ("app") → 路径存在 → 返回 true

再插入app：把第三个p的isEnd = truesearch ("app") 就变成 true。

一句话区分两个函数：search(word)：路径能走完并且终点 isEnd=truestartsWith(prefix)：只要路径能走完就行，不管终点是不是单词

二、节点结构体设计

struct TrieNode{ // 26个子节点指针，初始都是nullptr TrieNode* children[26]; // 是否是某个单词的结尾 bool isEnd; // 构造函数 TrieNode(){ memset(children, 0, sizeof(children)); isEnd = false; } };

• children[0]代表字母a
• children[1]代表字母b
• 字符转下标公式：c - 'a'

外层Trie类只需要保存一个根节点：

class Trie { private: TrieNode* root; public: Trie(){ root = new TrieNode(); } // 下面三个方法 };

⚠️ 根节点不存放任何字母，只是遍历起点！

三、逐个函数思路拆解

1. insert (string word) 插入单词

思路流程：

1. 定义指针cur从根节点root出发
2. 依次遍历单词中每一个字符c
   • 计算下标idx = c - 'a'
   • 如果cur->children[idx] == nullptr：说明这条路径不存在，新建节点
   • 指针移动：cur = cur->children[idx]
3. 所有字符遍历完成，当前 cur 标记为单词结尾cur->isEnd = true

void insert(string word) { TrieNode* cur = root; for(char c : word){ int idx = c - 'a'; if(!cur->children[idx]){ cur->children[idx] = new TrieNode(); } cur = cur->children[idx]; } cur->isEnd = true; }

2. search (string word) 查找完整单词

思路流程：

1. cur从根出发
2. 遍历每个字符：
   • 算出下标
   • 如果子节点为空 → 路径断了，直接 return false
   • 指针向后移动
3. 字符全部走完后：不能直接返回 true！必须看 cur->isEnd

很多人这里翻车！ 只存在前缀不代表存在单词。

bool search(string word) { TrieNode* cur = root; for(char c : word){ int idx = c - 'a'; if(!cur->children[idx]){ return false; } cur = cur->children[idx]; } return cur->isEnd; }

3. startsWith (string prefix) 判断前缀是否存在

思路流程：和 search 前面几乎一模一样！ 唯一区别：遍历完所有前缀字符后，不需要判断 isEnd，直接返回 true只要路径存在，就说明有单词以这个前缀开头。

四、完整可直接提交代码

#include <cstring> #include <string> using namespace std; struct TrieNode{ TrieNode* children[26]; bool isEnd; TrieNode(){ memset(children, 0, sizeof(children)); isEnd = false; } }; class Trie { private: TrieNode* root; public: Trie() { root = new TrieNode(); } void insert(string word) { TrieNode* cur = root; for(char c : word){ int idx = c - 'a'; if(!cur->children[idx]){ cur->children[idx] = new TrieNode(); } cur = cur->children[idx]; } cur->isEnd = true; } bool search(string word) { TrieNode* cur = root; for(char c : word){ int idx = c - 'a'; if(!cur->children[idx]){ return false; } cur = cur->children[idx]; } return cur->isEnd; } bool startsWith(string prefix) { TrieNode* cur = root; for(char c : prefix){ int idx = c - 'a'; if(!cur->children[idx]){ return false; } cur = cur->children[idx]; } return true; } };

五、模拟题目样例走一遍，打通逻辑

Trie trie; trie.insert("apple"); 树路径：root-a-p-p-l-e，e.isEnd=true trie.search("apple"); 走完a p p l e，e.isEnd=true → true trie.search("app"); 走到第三个p，p.isEnd=false → false trie.startsWith("app"); 成功走完a p p → true trie.insert("app"); 走到第三个p，设置 p.isEnd=true trie.search("app"); 走到第三个p，isEnd=true → true

和样例输出完全对应。

六、高频坑总结（面试常问）

1. ❌ search 忘记 return cur->isEnd，直接返回 true
2. ❌ 混淆节点：字符存在边上，节点本身不存字符
3. ❌ 根节点误以为存字母，根只是起点
4. ❌ insert 最后忘记设置 isEnd
5. 拓展：这道代码没有写内存释放，刷题平台无所谓；工程代码需要写析构递归释放节点，防止内存泄漏。

七、面试思考

Trie 适合什么场景？

• 单词前缀匹配、自动补全、拼写词典 优势：查询一个单词 / 前缀时间复杂度 O (len (word))，和单词总数无关。

5 小结

207 课程表

题意：课程有先修依赖，[a,b]学 a 先学 b → 边b→a，有向图判环。有环返回 false，无环 true。

方法 1：Kahn BFS 拓扑排序

建邻接表graph、inDegree入度数组 遍历prerequisites建边，统计入度 入度为0节点入队列 count=0 while队列非空： cur出队，count++ 遍历cur后继，入度-1，入度0入队 return count == numCourses

面试口述：课程为节点，依赖是有向边。入度代表剩余前置课程。先把无前置课入队，学完一课就减少后继的前置；能学完全部课程说明无环。

注意：边不能建反；图可能不连通；复杂度 O (n+m)

方法 2：DFS 判环

状态：0 未访问，1 递归栈中，2 访问完成伪代码

dfs(cur): if visited[cur]==1 return True //找到环 if visited[cur]==2 return False visited[cur]=1 for next: if dfs(next) return True visited[cur]=2 return False 遍历所有节点，发现环返回false，否则true

注意：不能只用 bool 访问标记，区分 “正在路径上” 和 “已经处理完”

208 Trie 前缀树

核心：字符存边上，节点存children[26]、isEnd标记单词结尾，共享公共前缀。

Node{ children[26]全null; isEnd=false; } root = new Node insert(word): cur=root for c: idx=c-'a' 无孩子就新建节点 cur=cur.children[idx] cur.isEnd=true search(word): cur=root for c:路径断了return false return cur.isEnd //重点！判断是否单词结尾 startsWith(prefix): cur=root for c:路径断了return false return true //只看路径存在，不用isEnd

面试口述：前缀树复用公共前缀，插入顺着字符建路径，isEnd标记完整单词。search 必须判断isEnd，startsWith 只需要路径存在。查询时间 O (单词长度)。

易错：

1. search 不要直接 return true，漏判isEnd
2. 根节点不存字符，只是起点
3. insert 末尾设置isEnd

面试速记总结

1. 207 课程表

• BFS (Kahn)：入度，拓扑计数；适合口述写代码
• DFS：三色状态判环；处理有向图环
• 大坑：边方向[a,b] → b→a

1. 208 Trie

• 节点：26 孩子数组 + isEnd 标记
• insert 建路径打结尾标记
• search：路径存在 + isEnd；startsWith 仅路径存在
• 大坑：search 忘记isEnd