今天是十五周算法训练营的第十五周,主要讲岛屿问题专题。周算
给你一个由 '1'(陆地)和 '0'(水)组成的练营的二维网格,请你计算网格中岛屿的岛屿数量。
岛屿总是问题被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的周算陆地连接形成。
此外,法训你可以假设该网格的练营四条边均被水包围。
示例 1:
输入:grid = [ ["1",岛屿"1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] 输出:1
// 找到岛屿+1// 将岛屿淹没function numIslands(grid) { // 通过dfs将岛屿淹没 const dfs = (grid,问题 i, j) => { const m = grid.length; const n = grid[0].length; if (i < 0 || i >= m || j < 0 || j >= n) { // 超出索引边界 return; } // 如果已经被淹了,直接返回 if (grid[i][j] === '0') { return; } // 将当前变成海水 grid[i][j] = '0'; // 淹没四周 dfs(grid, i - 1, j); dfs(grid, i + 1, j); dfs(grid, i, j - 1); dfs(grid, i, j + 1); }; const m = grid.length; const n = grid[0].length; let result = 0; for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { if (grid[i][j] === '1') { // 每发现一个岛屿,岛屿数量加1 result++; // 然后使用dfs将岛屿淹没 dfs(grid, i, j); } } } return result;}const grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]];console.log(numIslands(grid));
给你一个大小为 m x n 的二进制矩阵 grid 。
岛屿 是由一些相邻的 1 (代表土地) 构成的组合,这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0(代表水)包围着。
岛屿的面积是岛上值为 1 的单元格的数目。
计算并返回 grid 中最大的岛屿面积。如果没有岛屿,则返回面积为 0 。
示例 1:
输入:grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]] 输出:6 解释:答案不应该是 11 ,因为岛屿只能包含水平或垂直这四个方向上的 1 。
function maxAreaIsland(grid) { // 通过dfs淹没岛屿 const dfs = (grid, i, j) => { const m = grid.length; const n = grid[0].length; // 超出边界直接跳过 if (i < 0 || i >= m || j < 0 || j >= n) { return 0; } if (grid[i][j] === 0) { return 0; } // 淹没当前位置 grid[i][j] = 0; // 淹没上下左右 return 1 + dfs(grid, i - 1, j) + dfs(grid, i + 1, j) + dfs(grid, i, j - 1) + dfs(grid, i, j + 1); } const m = grid.length; const n = grid[0].length; let maxArea = 0; for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { if (grid[i][j] === 1) { maxArea = Math.max(dfs(grid, i, j), maxArea); } } } return maxArea;}const grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]];console.log(maxAreaIsland(grid));
给你一个大小为 m x n 的二进制矩阵 grid ,其中 0 表示一个海洋单元格、1 表示一个陆地单元格。
一次 移动 是指从一个陆地单元格走到另一个相邻(上、下、左、右)的陆地单元格或跨过 grid 的边界。
返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。
示例 1:
输入:grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]] 输出:3 解释:有三个 1 被 0 包围。一个 1 没有被包围,因为它在边界上。
// 该题目其实就是求不邻接边界的土地的面积// 其实就是将邻接边界的岛屿淹没,然后遍历一遍获取剩下岛屿的面积function numsEnclaves(grid) { // 通过dfs将岛屿淹没 const dfs = (grid, i, j) => { const m = grid.length; const n = grid[0].length; // 超过边界,则跳过 if (i < 0 || i >= m ||j < 0 || j >= n) { return; } // 如果已经是海洋,则跳过 if (grid[i][j] === 0) { return; } // 将当前淹没 grid[i][j] = 0; // 将上下左右淹没 dfs(grid, i - 1, j); dfs(grid, i + 1, j); dfs(grid, i, j - 1); dfs(grid, i, j + 1); }; let result = 0; const m = grid.length; const n = grid[0].length; // 将上下边界淹没 for (let j = 0; j < n; j++) { dfs(grid, 0, j); dfs(grid, m - 1, j); } // 将左右边界淹没 for (let i = 0; i < m; i++) { dfs(grid, i, 0); dfs(grid, i, n - 1); } for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { if (grid[i][j] === 1) { result++; } } } return result;}const grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]];console.log(numsEnclaves(grid));
二维矩阵 grid 由 0 (土地)和 1 (水)组成。岛是由最大的4个方向连通的 0 组成的群,封闭岛是一个 完全 由1包围(左、上、右、下)的岛。
请返回 封闭岛屿 的数目。
示例 1:
输入:grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]] 输出:2 解释: 灰色区域的岛屿是封闭岛屿,因为这座岛屿完全被水域包围(即被 1 区域包围)。
// 先将靠边的岛屿淹没掉// 然后找岛屿,找到岛屿加1,并淹没function closeIsland(grid) { // 通过dfs将岛屿淹没 const dfs = (grid, i, j) => { const m = grid.length; const n = grid[0].length; if (i < 0 || i >= m || j < 0 || j >= n) { return; } if (grid[i][j] === 1) { return; } // 将当前位置淹没 grid[i][j] = 1; // 将上下左右位置淹没 dfs(grid, i - 1, j); dfs(grid, i + 1, j); dfs(grid, i, j - 1); dfs(grid, i, j + 1); }; const m = grid.length; const n = grid[0].length; // 将上下边界处的岛屿淹没 for (let j = 0; j < n; j++) { dfs(grid, 0, j); dfs(grid, m - 1, j); } // 将左右边界的岛屿淹没 for (let i = 0; i < m; i++) { dfs(grid, i, 0); dfs(grid, i, n - 1); } let result = 0; for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { if (grid[i][j] === 0) { // 遇到岛屿,岛屿加1 result++; // 淹没岛屿 dfs(grid, i, j); } } } return result;}const grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]];console.log(closeIsland(grid));
给你两个 m x n 的二进制矩阵 grid1 和 grid2 ,它们只包含 0 (表示水域)和 1 (表示陆地)。一个 岛屿 是由 四个方向 (水平或者竖直)上相邻的 1 组成的区域。任何矩阵以外的区域都视为水域。
如果 grid2 的一个岛屿,被 grid1 的一个岛屿 完全 包含,也就是说 grid2 中该岛屿的每一个格子都被 grid1 中同一个岛屿完全包含,那么我们称 grid2 中的这个岛屿为 子岛屿 。
请你返回 grid2 中 子岛屿 的 数目 。
示例 1:
输入:grid1 = [[1,1,1,0,0],[0,1,1,1,1],[0,0,0,0,0],[1,0,0,0,0],[1,1,0,1,1]], grid2 = [[1,1,1,0,0],[0,0,1,1,1],[0,1,0,0,0],[1,0,1,1,0],[0,1,0,1,0]] 输出:3 解释:如上图所示,左边为 grid1 ,右边为 grid2 。 grid2 中标红的 1 区域是子岛屿,总共有 3 个子岛屿。
// 首先将在grid1中是海水部分的在grid2中的岛屿淹没掉,剩下的就是grid2中的子岛屿function countSubIslands(grid1, grid2) { const dfs = (grid, i, j) => { const m = grid.length; const n = grid[0].length; if (i < 0 || i >= m || j < 0 || j >= n) { return; } if (grid[i][j] === 0) { return; } grid[i][j] = 0; dfs(grid, i - 1, j); dfs(grid, i + 1, j); dfs(grid, i, j - 1); dfs(grid, i, j + 1); }; // 将grid2中grid1中是海水的岛屿淹没 const m = grid1.length; const n = grid1[0].length; let result = 0; for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { if (grid1[i][j] === 0) { // 淹没grid2中的岛屿 dfs(grid2, i, j); } } } for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { if (grid2[i][j] === 1) { result++; dfs(grid2, i, j); } } } return result;}const grid1 = [[1,0,1,0,1,1,1,0,1,1,0,1,1,1,1],[1,1,1,1,1,0,1,1,1,1,0,0,0,1,1],[1,1,1,1,1,0,1,1,1,1,1,1,1,1,0],[1,1,1,1,0,1,0,0,1,1,1,1,0,0,1],[0,0,1,1,1,1,1,0,1,0,1,1,1,0,0],[0,1,1,1,1,1,1,1,1,0,1,1,1,1,1],[0,0,1,1,1,1,1,1,1,1,1,1,1,1,0],[0,1,1,1,1,1,1,1,0,1,1,1,1,1,1],[1,1,1,1,1,1,1,1,1,1,1,1,1,1,0],[1,1,1,1,0,1,0,0,1,1,1,0,0,1,1],[1,0,1,1,1,1,1,0,0,1,1,1,1,0,1],[0,1,0,0,0,1,1,1,1,1,1,1,0,0,1]], grid2 = [[1,0,1,0,0,0,1,0,0,0,0,0,1,0,1],[1,1,0,1,0,1,1,1,1,1,0,1,0,1,1],[1,1,1,0,1,1,1,1,1,1,0,1,0,1,1],[1,0,0,1,0,1,1,1,0,0,1,0,1,0,1],[0,1,1,1,1,1,1,0,1,1,1,1,1,0,0],[0,1,1,1,1,1,1,1,1,1,0,1,1,1,0],[1,1,1,1,1,1,1,1,1,0,0,1,0,1,1],[1,0,1,0,0,1,1,1,0,1,0,1,1,1,1],[0,1,0,1,1,1,0,1,1,1,1,0,0,0,1],[1,1,1,0,1,0,0,0,1,1,0,0,1,1,1],[1,0,0,1,1,1,0,0,0,0,1,0,1,0,0],[0,0,1,1,1,1,1,0,1,0,1,1,1,0,0]];console.log(countSubIslands(grid1, grid2));
责任编辑:姜华 来源: 前端点线面 岛屿问题算法(责任编辑:知识)
武汉第四座铁路客运大站武汉东站开通运营 总建筑面积16.3万平方米
中国海油有限海南分公司一季度天然气增幅54% 有效保障粤港琼天然气需求
全力以赴实现度电必争 四川省港投集团发电企业多措并举战高温、保供电
商络电子海南公司拟向亿维特增资2000万元 部分计入亿维特注册资本