力扣DAY52-54 | 热100 | 图论：腐烂的橘子、课程表、前缀树

前言

中等 √ 腐烂的橘子用层次遍历，课程表用俩哈希表，前缀树基本与题解一致。however不太规范。

腐烂的橘子

我的题解

层次遍历，先找出所有腐烂的橘子进入队列并记录数量，接着内层遍历第一层腐烂的橘子，上下左右四个方向值为1的橘子都改为2并把它们入队，同时记录该层的入队数量。层次数量-1即为腐烂时间（最后一次循环已无可以传染的橘子，故要-1）。最后遍历数组，如果还有新鲜橘子，返回-1，否则返回腐烂时间。

class Solution {
public:int orangesRotting(vector<vector<int>>& grid) {if (grid.empty())return 0;int m = grid.size();int n = grid[0].size();int time = 0; //层次遍历，time为层数int nums = 0;queue<pair<int, int>> q;for (int i = 0; i < m; i++){for (int j = 0; j < n; j++){if (grid[i][j] == 2){q.push({i, j});nums++;}}}while (!q.empty()){time++;int cur = nums;nums  = 0;while (cur--){int r = q.front().first;int c = q.front().second;q.pop();//上下左右遍历是否为1if (r > 0 && grid[r-1][c] == 1){grid[r-1][c] = 2;q.push({r-1, c});nums++;}if (r < m-1 && grid[r+1][c] == 1){grid[r+1][c] = 2;q.push({r+1, c});nums++;}if (c > 0 && grid[r][c-1] == 1){grid[r][c-1] = 2;q.push({r, c-1});nums++;}if (c < n-1 && grid[r][c+1] == 1){grid[r][c+1] = 2;q.push({r, c+1});nums++;} }}for (int i = 0; i < m; i++){for (int j = 0; j < n; j++){if (grid[i][j] == 1){return -1;}}}return max(time-1, 0);}
};

官方题解

多源广度优先搜索

观察到对于所有的腐烂橘子，其实它们在广度优先搜索上是等价于同一层的节点的。

假设这些腐烂橘子刚开始是新鲜的，而有一个腐烂橘子(我们令其为超级源点)会在下一秒把这些橘子都变腐烂，而这个腐烂橘子刚开始在的时间是 −1 ，那么按照广度优先搜索的算法，下一分钟也就是第 0 分钟的时候，这个腐烂橘子会把它们都变成腐烂橘子，然后继续向外拓展，所以其实这些腐烂橘子是同一层的节点。那么在广度优先搜索的时候，我们将这些腐烂橘子都放进队列里进行广度优先搜索即可，最后每个新鲜橘子被腐烂的最短时间 dis[x][y] 其实是以这个超级源点的腐烂橘子为起点的广度优先搜索得到的结果。

为了确认是否所有新鲜橘子都被腐烂，可以记录一个变量 cnt 表示当前网格中的新鲜橘子数，广度优先搜索的时候如果有新鲜橘子被腐烂，则 cnt=cnt−1 ，最后搜索结束时如果 cnt 大于 0 ，说明有新鲜橘子没被腐烂，返回 −1 ，否则返回所有新鲜橘子被腐烂的时间的最大值即可，也可以在广度优先搜索的过程中把已腐烂的新鲜橘子的值由 1 改为 2，最后看网格中是否有值为 1 即新鲜的橘子即可。

class Solution {int cnt;int dis[10][10];int dir_x[4] = {0, 1, 0, -1};int dir_y[4] = {1, 0, -1, 0};
public:int orangesRotting(vector<vector<int>>& grid) {queue<pair<int, int>>Q;memset(dis, -1, sizeof(dis));cnt = 0;int n = (int)grid.size(), m = (int)grid[0].size(), ans = 0;for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {if (grid[i][j] == 2) {Q.emplace(i, j);dis[i][j] = 0;}else if (grid[i][j] == 1) {cnt += 1;}}}while (!Q.empty()){auto [r, c] = Q.front();Q.pop();for (int i = 0; i < 4; ++i) {int tx = r + dir_x[i];int ty = c + dir_y[i];if (tx < 0|| tx >= n || ty < 0|| ty >= m || ~dis[tx][ty] || !grid[tx][ty]) {continue;}dis[tx][ty] = dis[r][c] + 1;Q.emplace(tx, ty);if (grid[tx][ty] == 1) {cnt -= 1;ans = dis[tx][ty];if (!cnt) {break;}}}}return cnt ? -1 : ans;}
};

心得

笔者思路与官解基本一致，笔者更像是模拟了整个过程而官解记录了所有位置的腐烂时间，另外笔者的做法改变了grid内容而官解开辟了一个10*10的数组存储额外信息。我感觉官解写的不算非常好懂，不过它的思路就是记录新鲜橘子数量、每个橘子腐烂时间（初始化为-1）。遍历grid，腐烂的橘子时间为0，并入队，接着遍历队里的橘子，橘子取出后遍历上下左右四个方向，如果无越界/没腐烂（-1）、在grid里，就变为腐烂，新鲜橘子减1，腐烂时间为上一个橘子时间+1。直到队列为空，如果还有新鲜橘子返回﹣1，否则返回腐烂时间最大值。这次感觉官解没我的好哈哈哈

课程表

我的题解

用两个哈希表记录课与前置课的关系。初始化队列，把没有前置课的课放入队列中。遍历队列，把队列中的课从cur中取出，如果cur为空，说明该门课不需要前置课，把这门课对应的所有课放入列表，直到列表为空。最后如果cur为空说明形成拓扑结构，每门课都可以完成返回true，否则返回false。

class Solution {
public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {unordered_map<int, vector<int>> pre; //键课程号，值rowunordered_map<int, vector<int>> cur; //键课程号，值rowqueue<int> q;  //没有前置课程的课程index，row//初始化两个哈希表for (int i = 0; i < prerequisites.size(); i++){pre[prerequisites[i][1]].push_back(i);cur[prerequisites[i][0]].push_back(i);}//初始化队列for (auto it = pre.begin(); it != pre.end(); ++it){if (cur.find(it->first) == cur.end()){for (int i = 0; i < it->second.size(); i++){q.push(it->second[i]);}}}//遍历队列，把没有前置的课从cur中取出，并加入qwhile (!q.empty() ){int pre_course = prerequisites[q.front()][1];int cur_course = prerequisites[q.front()][0];cur[cur_course].erase(find(cur[cur_course].begin(), cur[cur_course].end(), q.front()));if (cur[cur_course].empty()){cur.erase(cur_course);for (int i = 0; i < pre[cur_course].size(); i++){q.push(pre[cur_course][i]);}   }q.pop();}if (cur.empty())return true;elsereturn false;}
};

官方题解

深度优先搜索

我们可以将深度优先搜索的流程与拓扑排序的求解联系起来，用一个栈来存储所有已经搜索完成的节点。

对于一个节点 u，如果它的所有相邻节点都已经搜索完成，那么在搜索回溯到 u 的时候，u 本身也会变成一个已经搜索完成的节点。这里的「相邻节点」指的是从 u 出发通过一条有向边可以到达的所有节点。

假设我们当前搜索到了节点 u，如果它的所有相邻节点都已经搜索完成，那么这些节点都已经在栈中了，此时我们就可以把 u 入栈。可以发现，如果我们从栈顶往栈底的顺序看，由于 u 处于栈顶的位置，那么 u 出现在所有 u 的相邻节点的前面。因此对于 u 这个节点而言，它是满足拓扑排序的要求的。

这样以来，我们对图进行一遍深度优先搜索。当每个节点进行回溯的时候，我们把该节点放入栈中。最终从栈顶到栈底的序列就是一种拓扑排序。

算法

对于图中的任意一个节点，它在搜索的过程中有三种状态，即：

「未搜索」：我们还没有搜索到这个节点；

「搜索中」：我们搜索过这个节点，但还没有回溯到该节点，即该节点还没有入栈，还有相邻的节点没有搜索完成）；

「已完成」：我们搜索过并且回溯过这个节点，即该节点已经入栈，并且所有该节点的相邻节点都出现在栈的更底部的位置，满足拓扑排序的要求。

通过上述的三种状态，我们就可以给出使用深度优先搜索得到拓扑排序的算法流程，在每一轮的搜索搜索开始时，我们任取一个「未搜索」的节点开始进行深度优先搜索。

我们将当前搜索的节点 u 标记为「搜索中」，遍历该节点的每一个相邻节点 v：

如果 v 为「未搜索」，那么我们开始搜索 v，待搜索完成回溯到 u；

如果 v 为「搜索中」，那么我们就找到了图中的一个环，因此是不存在拓扑排序的；

如果 v 为「已完成」，那么说明 v 已经在栈中了，而 u 还不在栈中，因此 u 无论何时入栈都不会影响到 (u,v) 之前的拓扑关系，以及不用进行任何操作。

当 u 的所有相邻节点都为「已完成」时，我们将 u 放入栈中，并将其标记为「已完成」。

在整个深度优先搜索的过程结束后，如果我们没有找到图中的环，那么栈中存储这所有的 n 个节点，从栈顶到栈底的顺序即为一种拓扑排序。

class Solution {
private:vector<vector<int>> edges;vector<int> visited;bool valid = true;public:void dfs(int u) {visited[u] = 1;for (int v: edges[u]) {if (visited[v] == 0) {dfs(v);if (!valid) {return;}}else if (visited[v] == 1) {valid = false;return;}}visited[u] = 2;}bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {edges.resize(numCourses);visited.resize(numCourses);for (const auto& info: prerequisites) {edges[info[1]].push_back(info[0]);}for (int i = 0; i < numCourses && valid; ++i) {if (!visited[i]) {dfs(i);}}return valid;}
};

广度优先搜索

方法一的深度优先搜索是一种「逆向思维」：最先被放入栈中的节点是在拓扑排序中最后面的节点。我们也可以使用正向思维，顺序地生成拓扑排序，这种方法也更加直观。

我们考虑拓扑排序中最前面的节点，该节点一定不会有任何入边，也就是它没有任何的先修课程要求。当我们将一个节点加入答案中后，我们就可以移除它的所有出边，代表着它的相邻节点少了一门先修课程的要求。如果某个相邻节点变成了「没有任何入边的节点」，那么就代表着这门课可以开始学习了。按照这样的流程，我们不断地将没有入边的节点加入答案，直到答案中包含所有的节点（得到了一种拓扑排序）或者不存在没有入边的节点（图中包含环）。

上面的想法类似于广度优先搜索，因此我们可以将广度优先搜索的流程与拓扑排序的求解联系起来。

算法

我们使用一个队列来进行广度优先搜索。初始时，所有入度为 0 的节点都被放入队列中，它们就是可以作为拓扑排序最前面的节点，并且它们之间的相对顺序是无关紧要的。

在广度优先搜索的每一步中，我们取出队首的节点 u：

我们将 u 放入答案中；

我们移除 u 的所有出边，也就是将 u 的所有相邻节点的入度减少 1。如果某个相邻节点 v 的入度变为 0，那么我们就将 v 放入队列中。

在广度优先搜索的过程结束后。如果答案中包含了这 n 个节点，那么我们就找到了一种拓扑排序，否则说明图中存在环，也就不存在拓扑排序了。

class Solution {
private:vector<vector<int>> edges;vector<int> indeg;public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {edges.resize(numCourses);indeg.resize(numCourses);for (const auto& info: prerequisites) {edges[info[1]].push_back(info[0]);++indeg[info[0]];}queue<int> q;for (int i = 0; i < numCourses; ++i) {if (indeg[i] == 0) {q.push(i);}}int visited = 0;while (!q.empty()) {++visited;int u = q.front();q.pop();for (int v: edges[u]) {--indeg[v];if (indeg[v] == 0) {q.push(v);}}}return visited == numCourses;}
};

心得

这道题是经典拓扑排序题，尽管笔者知道不能成环（dfs）和移除入度为0的点（bfs）两种解法，但还是不太知道如何高效编码出这两个方法，最后居然是用了两个哈希表，一个前缀->课 ≈ 图edges，一个课->前缀 ≈ 入度关系visited，也真是误打误撞了。用哈希表的好处是根本用不到coursenum这个变量，因为无需开辟同等规模的数组存图。最后总结下两种思路“应该”怎么做。开辟coursenum规模的二维数组，存储前缀课程关系，前缀->课。1）dfs中开辟coursenum规模的visited一维数组定义搜索关系，0未搜索，1搜索中，2已完成，if搜索到搜索中的节点说明成环，不符合拓扑关系。2）bfs与笔者思路基本一致，开辟visited一维数组存储每个节点的入度数量，遍历grid初始化（没有相邻变的入度也为0，故都会遍历到）后，把入度为0的节点放入队列，此时cnt++，接着把这些节点相邻的节点入度数量-1，如果为0则放入队列。队列为空时如果cnt等于课程数则返回true，否则为false。这个经典题目需要二刷！另外，原来coursenum其实就是点，图：二维数组存边，每个点开辟一个位置，指向相邻边（单向），根据题目需要加辅助工具 visited记录每个点的搜索状态 indeg记录每个点的入度数。

前缀树

我的题解

26叉树，用数组存储孩子节点指向，同时用bool变量记录当前节点是不是一个单词的终结。插入：遍历字母，如果无指向要开辟新结点存放，直到遍历完成标出为funish=true。查找单词/前缀：基本一致，都是遍历单词顺着放下找，如果中途不存在则返回false，遍历完成前缀直接返回true，单词需要判断末尾的finish是否为true。

class Trie {
public:struct trieNode{trieNode* arr[26] = {};bool finish = false;};trieNode* root;Trie() {root = new trieNode();}void insert(string word) {trieNode* node = root;int n = word.size();for (int i = 0; i < n; i++){if (!node->arr[word[i]-'a']){trieNode* next = new trieNode();node->arr[word[i]-'a'] = next;}node = node->arr[word[i]-'a'];  }node->finish = true;}bool search(string word) {trieNode* node = root;int n = word.size();for (int i = 0; i < n; i++){if (!node->arr[word[i]-'a']){return false;}node = node->arr[word[i]-'a']; }return node->finish;}bool startsWith(string prefix) {trieNode* node = root;int n = prefix.size();for (int i = 0; i < n; i++){if (!node->arr[prefix[i]-'a']){return false;}node = node->arr[prefix[i]-'a']; }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);*/

官方题解

思路与笔者一致，不赘述，但是格式可以参考。

class Trie {
private:vector<Trie*> children;bool isEnd;Trie* searchPrefix(string prefix) {Trie* node = this;for (char ch : prefix) {ch -= 'a';if (node->children[ch] == nullptr) {return nullptr;}node = node->children[ch];}return node;}public:Trie() : children(26), isEnd(false) {}void insert(string word) {Trie* node = this;for (char ch : word) {ch -= 'a';if (node->children[ch] == nullptr) {node->children[ch] = new Trie();}node = node->children[ch];}node->isEnd = true;}bool search(string word) {Trie* node = this->searchPrefix(word);return node != nullptr && node->isEnd;}bool startsWith(string prefix) {return this->searchPrefix(prefix) != nullptr;}
};

心得

这个题目相对比较简单（感觉不太像图），果然不要怀疑自己的想法，虽然好像怪怪的（一个链存一个单词），但是先做出来再说！另外官解的格式我可以参考下，可以随意改变孩子节点数。其实这里应该系统化地复习/学习下怎么写。而且其实我也又想到前缀写法一样，但懒得改了，官解是在private定义写法返回node，public再调用，很优雅。至此图论已做完，咋感觉不够啊，虽然都写出来了但不太顺畅也不是很通用？后面再拿多几道练手吧~

知识点

memset(dis, -1, sizeof(dis)); // 初始化dis为-1

~dis[tx][ty] 等效于 dis[tx][ty] != -1

edges.resize(numCourses);         indeg.resize(numCourses);  定义容器大小