用别人代码搭建网站,微信公众号开通商城,个人做企业网站制作要多少钱,设计网站的合同文章目录 题目描述算法原理代码实现CJava 题目描述
题目链接#xff1a;200.岛屿数量 PS:注意题目中每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。也就是说斜角是不算了#xff0c; 例如示例二#xff0c;是三个岛屿。
算法原理
这道题目是 DFS#xff0… 文章目录 题目描述算法原理代码实现CJava 题目描述
题目链接200.岛屿数量 PS:注意题目中每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。也就是说斜角是不算了 例如示例二是三个岛屿。
算法原理
这道题目是 DFSBFS并查集基础题目因为本博客属于BFS专题所以只会讲解如何用BFS解决具体如下 遍历整个矩阵每次找到⼀块陆地的时候
说明找到⼀个岛屿记录到最终结果 ret ⾥⾯并且将这个陆地相连的所有陆地也就是这块岛屿全部变成海洋。这样的话我们下次遍历到这块岛屿的时候它已经是海洋了不会影响最终结果。PS可以在原数组上改也可以用一个 bool 类型的visited数组标记笔试可以直接改面试能不能改需要询问面试官其中变成海洋的操作可以利⽤深搜和宽搜解决其实就是 733. 图像渲染这道题~
这样当我们遍历完全部的矩阵的时候 ret 存的就是最终结果。 三个箭头是每次遇到新岛屿的时候将vis数组标记为true剩下的在陆地在每次q.push的时候标记为true。 不少同学用广搜做这道题目的时候超时了。 就是因为这里有一个广搜中很重要的细节根本原因是只要加入队列就代表走过就需要标记而不是从队列拿出来的时候再去标记走过。 很多同学可能说这有区别吗 如果从队列拿出节点再去标记这个节点走过就会发生这样的结果会导致很多节点重复加入队列。 代码实现
C
class Solution {typedef pairint, int PII;int dx[4] {0, 0, -1, 1};int dy[4] {-1, 1, 0, 0};bool vis[301][301];int m, n;public:int numIslands(vectorvectorchar grid) {int ret 0;m grid.size(), n grid[0].size();for (int i 0; i m; i) {for (int j 0; j n; j) {if (grid[i][j] 1 !vis[i][j]){bfs(grid, i, j);ret;}}}return ret;}void bfs(vectorvectorchar grid, int i, int j) {queuePII q;q.push({i, j});vis[i][j] true;while (!q.empty()) {auto [a, b] q.front();q.pop();for (int k 0; k 4; k) {int x a dx[k], y b dy[k];if (x 0 x m y 0 y n grid[x][y] 1 !vis[x][y]){q.push({x, y});vis[x][y] true;}}}}
};Java
class Solution {int[] dx { 0, 0, -1, 1 };int[] dy { 1, -1, 0, 0 };boolean[][] vis new boolean[301][301];int m, n;public int numIslands(char[][] grid) {m grid.length;n grid[0].length;int ret 0;for (int i 0; i m; i) {for (int j 0; j n; j) {if (grid[i][j] 1 !vis[i][j]) {ret;bfs(grid, i, j);}}}return ret;}public void bfs(char[][] grid, int i, int j) {Queueint[] q new LinkedList();q.add(new int[] { i, j });vis[i][j] true;while (!q.isEmpty()) {int[] t q.poll();int a t[0], b t[1];for (int k 0; k 4; k) {int x a dx[k], y b dy[k];if (x 0 x m y 0 y n grid[x][y] 1 !vis[x][y]) {q.add(new int[] { x, y });vis[x][y] true;}}}}
}
