当前位置：首页 > news >正文

LeetCodeHot100|图、994.腐烂的橘子、207.课程表、208.实现Trie前缀树

news 2026/5/14 14:55:46

图

一种由定点和边组成的非线性数据结构，从链表扩展而来，用于表示复杂的网络关系

1从链表树再到图

图是从链表扩展而来的数据结构。相较于线性关系的链表和分治关系数，网络关系的图的自由度更高，因而会更加的复杂。
![[PixPin_2026-04-27_17-27-35.gif]]

2图的基本概念

图的两个关键的概念是什么

3图的常见类型

图的常见类型有哪些，有哪六种类型

4 图的常见术语

领接、路径、和度是描述图结构的三个核心的术语。依次
![[Pasted image 20260427173817.png]]这里图的有向图和无向图是比较重要的地方，对于无相图，领接就是与顶点相邻的的所有顶点。度就是这个定点拥有的边的个数。比如当前4的领接以及顶点如下图所示：
![[Pasted image 20260427175551.png]]
对于无相图，里面的度是有说法的，分为入度以及出度，下图顶点5的信息就是没有领接顶点同时入度为2，出度为0![[Pasted image 20260427175704.png]]当前1的领接顶点就为{2,3,5}，而入度为0，出度为3.

5 图的表示：领接矩阵

领接矩阵使用n×n大小的矩阵来表示图。元素为1表示两顶点之间存在变，为0表示不存在。对于无向图来说。
这里有张图来方便理解这个问题，对于相连的两个元素，比如第一个顶点链接着第二个顶点，那么就表示为第一行第二列的这个数。
还有两种情况也需要注意：分有向图以及无向图，带权边和不带权边都是不相同的。
![[Pasted image 20260429103827.png]]

6.图的表示：领接表

领接表使用n个链表来表示图，链表的节点存储该顶点的所有领接顶点。相比于领接矩阵更省空间，但是查找效率低。
![[Pasted image 20260429102318.png]]

图的基础操作

分别写出领接矩阵和领接表在无向图中添加一条边的实现思路，并说明各自的时间复杂度
对比删除顶点操作：1.在领接矩阵中时间复杂度是多少？为什么？ 2.在领接表中时间复杂度又是多少？主要耗时在哪
现在有一个顶点很多，但是边很少的稀疏图，应选领接矩阵还是领接表？从空间占用、遍历领接点效率、增删边际效率三个方面说明。

Q1

首先看领接矩阵在无向图中添加一条边，在看领接表如何在无向图中添加一条边，然后会再给出时间复杂度。

200.岛屿数量

给你一个二维网格1陆地以及0水组成的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和竖直方向上相邻的陆地连接形成。可以假设该网格的四条边都被水包围。

题目解析

题目是求岛屿的数量，有岛屿可以分为这几种情况：1、也就是每一个数的上下和左右都没有它就岛屿 2.有一个方向有其他方向没有…
需要解决的问题：

怎么判断连续

将二维网格看成一个无向图，竖直或者水平相邻的1之间有边相连。如果需要求岛屿的数量，可以扫码整个二维网格。如果一个位置为1，就以其为起始节点开始深度优先搜索

classSolution{public:// 主函数：计算岛屿数量intnumIslands(vector<vector<char>>&grid){// 边界判断：如果网格为空，直接返回0个岛屿if(grid.empty()||grid[0].empty()){return0;}// 获取网格的 总行数 和 总列数introw=grid.size();intcol=grid[0].size();// 记录最终的岛屿数量，初始为0intres=0;// 1. 遍历整个二维网格的每一个格子for(inti=0;i<row;i++){for(intj=0;j<col;j++){// 2. 如果当前格子是陆地 '1'if(grid[i][j]=='1'){// 发现一座新岛屿，数量 +1res++;// 3. 调用DFS：把这座岛屿的所有陆地都变成水 '0'（沉岛）dfs(grid,i,j);}}}// 遍历完成，返回岛屿总数returnres;}private:// DFS 深度优先搜索：淹没当前岛屿，将相连的陆地全部置为0// grid：二维网格（引用传递，直接修改原数据）// r：当前所在行// c：当前所在列voiddfs(vector<vector<char>>&grid,intr,intc){// 获取网格总行数、总列数intnr=grid.size();intnc=grid[0].size();// 核心：把当前陆地标记为水，避免重复访问grid[r][c]='0';// 【向上】搜索：上面不越界 + 是陆地 → 递归DFSif(r-1>=0&&grid[r-1][c]=='1'){dfs(grid,r-1,c);}// 【向下】搜索：下面不越界 + 是陆地 → 递归DFSif(r+1<nr&&grid[r+1][c]=='1'){dfs(grid,r+1,c);}// 【向左】搜索：左边不越界 + 是陆地 → 递归DFSif(c-1>=0&&grid[r][c-1]=='1'){dfs(grid,r,c-1);}// 【向右】搜索：右边不越界 + 是陆地 → 递归DFSif(c+1<nc&&grid[r][c+1]=='1'){dfs(grid,r,c+1);}}};

关键问题

dfs是如何实现的。
是如何识别多个岛屿的

q1

在这个题目中只有一个作用：就是报道一个陆地’1’，一直往深处走，把所有连在一起的陆地全部变成水’0’,就像你站在一个小岛上吧整个岛全部淹掉。

voiddfs(vector<vector<char>&grid,intr,intc){// 1.获取网格的大小行以及列intnr=grid.size();intnc=grid[0].size// 2.把当前陆地变成水grid[r][c]='0';// 3.上下左右四个方向递归搜索if(r-1>=0&&grid[r-1][c]=='1')dfs(grid,r-1,c);// 上if(r+1<nr&&grid[r+1][c]=='1')dfs(grid,r+1,c);}

994.腐烂的橘子

给定的 m * n的网格中，每个单元格有三个值之一：
值0代表空单元格；
值1代表新鲜橘子
值2代表腐烂的橘子
每分钟，腐烂的橘子周围4个方向上相邻的新鲜橘子都会腐烂。

返回最小分钟数：直接单元格没有新鲜橘子为止所需比经过的最小分钟数。如果不可能，返回01

问题

题目需要求最小分钟数，从一个感染到其他怎么用代码表示？

优先搜索
while(fresh&&!q.empty()){

ans++; // 经过一分钟 vector<pair<int, int>> nxt; for (auto& [x, y] : q) { // 已经腐烂的橘子 for (auto d : DIRECTIONS) { // 四方向 int i = x + d[0], j = y + d[1]; if (0 <= i && i < m && 0 <= j && j < n && grid[i][j] == 1) { // 新鲜橘子 fresh--; grid[i][j] = 2; // 变成腐烂橘子 nxt.emplace_back(i, j); } } } q = move(nxt); }

周围四个相邻的怎么表示？
怎么使用BFS以及层序遍历
什么是广度优先搜索，具体的算法如何实现
从起点出发，每次的尝试访问同一层的节点，如果同一层访问完成再继续访问下一层，最后广度优先搜索找到的路径就是从起点开始的最短合法路径

207.课程表

你这个学期必须选修numCourses门课程，记为0到numCourses - 1在选修某些课程之前需要一些先修课程。先修课程按数组prerequisites给出，其中prerequisites[i] = [ai, bi],表示如果要学习课程ai则必须先学习课程bi。

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

思路分析

题目要求是判断是否可能完成所有课程的学习，就是需要一些先修课程，这里的规则是什么？
题目中给的参数各个之间关系是为什么？
这里的可能和不可能指的是什么？
怎么判断有像以及无向，如何判断是否是一个拓扑图？
整个算法的流程是什么样的？

代码

classSolution{public:boolcanFinish(intnumCourses,vector<vector<int>>&prerequisites){vector<vector<int>>g(numCourses);// ？语法for(auto&p:prerequisites){g[p[1]].push_back(p[0]);}vector<int>colors(numCourses);// 返回true表示找到了环autodfs=[&](thisauto&&dfs,intx)->bool{colors[x]=1;// x 正在访问中for(inty:g[x]){if(colors[y]==1||colors[y]==0&&dfs(y)){returntrue;// 找到了环}}colors[x]=2;// x完全访问完毕，从x出发无法找到环returnfalse;};for(inti=0;i<numCourses;i++){if(colors[i]==0&&dfs(i)){returnfalse;// 有环}}returntrue;// 没有环}};

208.实现Trie前缀树

Trie或者说是前缀树是一种树形数据结构，是用来高效存储和检索字符串数据集中的键。
常用于自动补全和拼写检查。
实现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

思路分析

题目是需要你去实现一个前缀树的
需要你实现的是三个功能+一个构造
示例中的案例是在干嘛？

这里的核心思路是需要去实现一个前缀树，这个树就是专门用来存放字符串的树，它的特点是。按字母一层层的存，共享前缀不重复，能想到这一点就很好了，所有它查单词、查前缀特别快。
然后接下来你必须实现3个功能和一个构造：1.需要去写一个Trie的类，里面有这四个东西1️⃣Trie，创建一颗空的前缀树，啥都不用做，初始化就可以

代码解析

classTrie{private:boolisEnd;// 标记当前的节点是否是某个单词的结束位置Trie*next[26];public:Trie(){isEnd=false;memset(next,0,sizeof(next));}voidinsert(string word){Trie*node=this;for(charc:word){if(node->next[c-'a']==NULL){// c-'a' 是转为0 ~ 25的索引node->next[c-'a']=newTrie();// 如果当前字符路径不存在，新建节点}node=node->next[c-'a'];// 移动到子节点}node->isEnd=true;}// 查询单词是否存在于字典树中boolsearch(string word){Trie*node=this;//就是从根节点出发开始遍历。for(charc:word){node=node->next[c-'a'];if(node==NULL){returnfalse;}}returnnode->isEnd;}boolstartsWith(string prefix){Trie*node=this;for(charc:prefix){node=node->next[c-'a'];if(node==NULL){returnfalse;}}returntrue;}};/** * 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); */