如何建立微网站,网店推广网站,一个主机放几个网站,网站空间怎么续费文章目录 LeetCode#xff1a;图论岛屿数量#xff08;Hot 100#xff09;岛屿的最大面积腐烂的橘子#xff08;Hot 100#xff09;课程表#xff08;Hot 100#xff09; LeetCode#xff1a;图论
岛屿数量#xff08;Hot 100#xff09;
岛屿数量
DFS:
class So… 文章目录 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, vectorvectorchar 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(vectorvectorchar 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, vectorvectorchar grid ){queuepairint, int que; // 存放当前能到达的陆地que.push({posx,posy});grid[posx][posy]0;while(!que.empty()){pairint, 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_next0||posy_nextgrid[0].size()||grid[posx_next][posy_next] 0) continue;que.push({posx_next,posy_next});grid[posx_next][posy_next]0;}}}
public:int numIslands(vectorvectorchar 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(vectorvectorint 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(vectorvectorint 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(vectorvectorint grid, int i, int j){int cur_max 0; // 当前面积queuepairint, 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(vectorvectorint 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(vectorvectorint grid) { int n grid.size(), m grid[0].size(), ans 0; // 存储腐烂的橙子的位置 queuepairint, int que; // 各个位置的橘子的腐烂时间 初始化距离数组为-1表示未访问 vectorvectorintdis(10, vectorint(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, vectorvectorint prerequisites) {// 入度数组各个课程的先修课程数量vectorint indegrees(numCourses, 0);// 邻接表各个课程的先修课程列表vectorvectorint adjacency(numCourses);// 存储当前可以学习的课程queueint 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;}
};
