文章目录
- LeetCode：图论
- 岛屿数量（Hot 100）
- 岛屿的最大面积
- 腐烂的橘子（Hot 100）
- 课程表（Hot 100）
LeetCode：图论
岛屿数量（Hot 100）
岛屿数量
DFS:
class Solution {
private:int direction[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};void dfs(int posx, int posy, vector<vector<char>>& grid) { // 越界了或者访问过的 或者是海洋的if (posx < 0 || posx >= grid.size() || posy < 0 || posy >= grid[0].size() || grid[posx][posy] == '0') { return; } grid[posx][posy] = '0'; // 访问过，标记为海洋for (int i = 0; i < 4; i++) { int posx_next = posx + direction[i][0]; int posy_next = posy + direction[i][1]; dfs(posx_next, posy_next, grid); } }
public:int numIslands(vector<vector<char>>& grid) {int m = grid.size();if (m == 0) return 0;int n = grid[0].size();int result = 0;for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(grid[i][j] == '1'){ // 没有访问过且是陆地的result++; // 遇到没访问过的陆地，+1dfs(i, j, grid); // 将与其链接的陆地都标记上 true}}}return result;}
};
BFS:
class Solution {private:int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};void bfs(int posx, int posy, vector<vector<char>>& grid ){queue<pair<int, int>> que; // 存放当前能到达的陆地que.push({posx,posy});grid[posx][posy]='0';while(!que.empty()){pair<int, int> cur = que.front();posx = cur.first;posy = cur.second;que.pop();for(int i = 0; i < 4; i++){int posx_next = posx + dir[i][0];int posy_next = posy + dir[i][1];if(posx_next < 0 || posx_next >= grid.size()||posy_next<0||posy_next>=grid[0].size()||grid[posx_next][posy_next] == '0') continue;que.push({posx_next,posy_next});grid[posx_next][posy_next]='0';}}}
public:int numIslands(vector<vector<char>>& grid) {int m = grid.size();int n = grid[0].size();int result = 0;for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(grid[i][j] == '1'){result++;bfs(i,j,grid);}}}return result;}
};
岛屿的最大面积
岛屿的最大面积
class Solution {
private:int di[4] = {0, 0, 1, -1};int dj[4] = {1, -1, 0, 0};int dfs(vector<vector<int>>& grid, int cur_i, int cur_j) {if (cur_i < 0 || cur_j < 0 || cur_i == grid.size() || cur_j == grid[0].size() || grid[cur_i][cur_j] != 1) {return 0;}grid[cur_i][cur_j] = 0;int cur_max = 1;for (int index = 0; index != 4; ++index) {int next_i = cur_i + di[index], next_j = cur_j + dj[index];cur_max += dfs(grid, next_i, next_j);}return cur_max;}
public:int maxAreaOfIsland(vector<vector<int>>& grid) {int ans = 0;for (int i = 0; i != grid.size(); ++i) {for (int j = 0; j != grid[0].size(); ++j) {if(grid[i][j] == 1) {int cur_max = dfs(grid, i, j);ans = max(ans,cur_max);}}}return ans;}
};
BFS
class Solution {
private:int di[4] = {0, 0, 1, -1};int dj[4] = {1, -1, 0, 0};int bfs(vector<vector<int>>& grid, int i, int j){int cur_max = 0; // 当前面积queue<pair<int, int>> q; // 存放当前能到达的陆地q.push({i, j}); grid[i][j] = 0; // 将当前单元格标记为已访问++cur_max; // 当前面积+1while (!q.empty()) {auto [cur_i, cur_j] = q.front();q.pop();for (int index = 0; index < 4; ++index) {int next_i = cur_i + di[index], next_j = cur_j + dj[index];if (next_i >= 0 && next_j >= 0 && next_i < grid.size() && next_j < grid[0].size() && grid[next_i][next_j] == 1) {q.push({next_i, next_j}); grid[next_i][next_j] = 0; // 标记为已访问++cur_max; // 当前面积+1}}}return cur_max;}
public:int maxAreaOfIsland(vector<vector<int>>& grid) {int ans = 0;for (int i = 0; i < grid.size(); ++i) {for (int j = 0; j < grid[0].size(); ++j) {if (grid[i][j] == 1) { // 只有在发现新的岛屿时才计算面积int cur_max = bfs(grid, i, j);ans = max(ans, cur_max); // 更新最大面积}}}return ans; }
};
腐烂的橘子（Hot 100）
腐烂的橘子
class Solution {
private:int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
public: int orangesRotting(vector<vector<int>>& grid) { int n = grid.size(), m = grid[0].size(), ans = 0; // 存储腐烂的橙子的位置 queue<pair<int, int>> que; // 各个位置的橘子的腐烂时间 初始化距离数组为-1，表示未访问 vector<vector<int>>dis(10, vector<int>(10, -1));// 计数器，用于记录还有多少个新鲜的橙子 int cnt = 0; // 遍历所有位置for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (grid[i][j] == 2) { // 找到腐烂的橙子并加入队列 que.emplace(i, j); dis[i][j] = 0; // 这个橘子本身已经腐烂 } else if (grid[i][j] == 1) { // 记录新鲜橙子的数量 cnt += 1; } } } // bfswhile (!que.empty()){ auto [x, y] = que.front();que.pop(); // 只考虑[x, y]腐烂的橘子，计算与其连接的其他橘子的腐烂时间 for (int i = 0; i < 4; ++i) { int nx = x + dir[i][0]; // 下一个位置的x坐标 int ny = y + dir[i][1]; // 下一个位置的y坐标 // 越界 或者 已经被访问过 或者 空单元格, 则跳过if (nx < 0 || nx >= n || ny < 0 || ny >= m || dis[nx][ny] !=-1 || grid[nx][ny]== 0 ) continue; // 如果这个位置是新鲜的橙子 dis[nx][ny] = dis[x][y] + 1; // 更新腐烂时间que.emplace(nx, ny); // 将新的腐烂橙子加入队列 cnt--; // 更新计数器ans = max(ans, dis[nx][ny]); // 更新答案 // 如果所有的新鲜橙子都腐烂了，则可以提前结束循环 if (cnt == 0) break; } } // 如果还有新鲜橙子(cnt != 0)未腐烂，则返回-1；否则返回腐烂所需的时间 return cnt ? -1 : ans; }
};
课程表（Hot 100）
课程表
class Solution {
public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {// 入度数组：各个课程的先修课程数量vector<int> indegrees(numCourses, 0);// 邻接表：各个课程的先修课程列表vector<vector<int>> adjacency(numCourses);// 存储当前可以学习的课程queue<int> q; // 获取每个课程的入度和邻接关系for (const auto& temp : prerequisites) {int cur = temp[0];int pre = temp[1];indegrees[cur]++; // cur的先修课程数量+1adjacency[pre].push_back(cur); // pre是cur的先修课程}// 将所有入度为0的课程加入队列，入度为0的课程不依赖于其他课程// 意味着学生可以直接学习这门课程，而不需要先完成其他任何课程。for (int i = 0; i < numCourses; ++i) {if (indegrees[i] == 0) q.push(i);}// bfswhile (!q.empty()) {int pre = q.front();q.pop();numCourses--; // 表示已经完成一门课程 // adjacency[pre]： 学习完pre，才可以学习的课程for (int cur : adjacency[pre]) {indegrees[cur]--; // 学习cur的还需要学习的先修课程减1if (indegrees[cur] == 0) q.push(cur);}}// 如果所有课程都能完成，则返回truereturn numCourses == 0;}
};