十五周算法訓練營——島嶼問題
今天是十五周算法訓練營的第十五周，主要講島嶼問題專題。
島嶼問題
一、題目
給你一個由 '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));
