十五周算法訓(xùn)練營(yíng)——島嶼問(wèn)題
今天是十五周算法訓(xùn)練營(yíng)的第十五周，主要講島嶼問(wèn)題專(zhuān)題。
島嶼問(wèn)題
一、題目
給你一個(gè)由 '1'（陸地）和 '0'（水）組成的的二維網(wǎng)格，請(qǐng)你計(jì)算網(wǎng)格中島嶼的數(shù)量。
島嶼總是被水包圍，并且每座島嶼只能由水平方向和/或豎直方向上相鄰的陸地連接形成。
此外，你可以假設(shè)該網(wǎng)格的四條邊均被水包圍。
示例 1：
輸入：grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] 輸出：1
二、題解
// 找到島嶼+1
// 將島嶼淹沒(méi)
function numIslands(grid) {
// 通過(guò)dfs將島嶼淹沒(méi)
const dfs = (grid, i, j) => {
const m = grid.length;
const n = grid[0].length;
if (i < 0 || i >= m || j < 0 || j >= n) {
// 超出索引邊界
return;
}
// 如果已經(jīng)被淹了，直接返回
if (grid[i][j] === '0') {
return;
}
// 將當(dāng)前變成海水
grid[i][j] = '0';
// 淹沒(méi)四周
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') {
// 每發(fā)現(xiàn)一個(gè)島嶼，島嶼數(shù)量加1
result++;
// 然后使用dfs將島嶼淹沒(méi)
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));島嶼的最大面積
一、題目
給你一個(gè)大小為 m x n 的二進(jìn)制矩陣 grid 。
島嶼 是由一些相鄰的 1 (代表土地) 構(gòu)成的組合，這里的「相鄰」要求兩個(gè) 1 必須在 水平或者豎直的四個(gè)方向上 相鄰。你可以假設(shè) grid 的四個(gè)邊緣都被 0（代表水）包圍著。
島嶼的面積是島上值為 1 的單元格的數(shù)目。
計(jì)算并返回 grid 中最大的島嶼面積。如果沒(méi)有島嶼，則返回面積為 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 解釋?zhuān)捍鸢覆粦?yīng)該是 11 ，因?yàn)閸u嶼只能包含水平或垂直這四個(gè)方向上的 1 。
二、題解
function maxAreaIsland(grid) {
// 通過(guò)dfs淹沒(méi)島嶼
const dfs = (grid, i, j) => {
const m = grid.length;
const n = grid[0].length;
// 超出邊界直接跳過(guò)
if (i < 0 || i >= m || j < 0 || j >= n) {
return 0;
}
if (grid[i][j] === 0) {
return 0;
}
// 淹沒(méi)當(dāng)前位置
grid[i][j] = 0;
// 淹沒(méi)上下左右
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));飛地的數(shù)量
一、題目
給你一個(gè)大小為 m x n 的二進(jìn)制矩陣 grid ，其中 0 表示一個(gè)海洋單元格、1 表示一個(gè)陸地單元格。
一次 移動(dòng) 是指從一個(gè)陸地單元格走到另一個(gè)相鄰（上、下、左、右）的陸地單元格或跨過(guò) grid 的邊界。
返回網(wǎng)格中 無(wú)法 在任意次數(shù)的移動(dòng)中離開(kāi)網(wǎng)格邊界的陸地單元格的數(shù)量。
示例 1：
輸入：grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]] 輸出：3 解釋?zhuān)河腥齻€(gè) 1 被 0 包圍。一個(gè) 1 沒(méi)有被包圍，因?yàn)樗谶吔缟稀?/p>
二、題解
// 該題目其實(shí)就是求不鄰接邊界的土地的面積
// 其實(shí)就是將鄰接邊界的島嶼淹沒(méi)，然后遍歷一遍獲取剩下島嶼的面積
function numsEnclaves(grid) {
// 通過(guò)dfs將島嶼淹沒(méi)
const dfs = (grid, i, j) => {
const m = grid.length;
const n = grid[0].length;
// 超過(guò)邊界，則跳過(guò)
if (i < 0 || i >= m ||j < 0 || j >= n) {
return;
}
// 如果已經(jīng)是海洋，則跳過(guò)
if (grid[i][j] === 0) {
return;
}
// 將當(dāng)前淹沒(méi)
grid[i][j] = 0;
// 將上下左右淹沒(méi)
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;
// 將上下邊界淹沒(méi)
for (let j = 0; j < n; j++) {
dfs(grid, 0, j);
dfs(grid, m - 1, j);
}
// 將左右邊界淹沒(méi)
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));統(tǒng)計(jì)封閉島嶼的數(shù)量
一、題目
二維矩陣 grid 由 0 （土地）和 1 （水）組成。島是由最大的4個(gè)方向連通的 0 組成的群，封閉島是一個(gè) 完全 由1包圍（左、上、右、下）的島。
請(qǐng)返回 封閉島嶼 的數(shù)目。
示例 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 解釋?zhuān)?灰色區(qū)域的島嶼是封閉島嶼，因?yàn)檫@座島嶼完全被水域包圍（即被 1 區(qū)域包圍）。
二、題解
// 先將靠邊的島嶼淹沒(méi)掉
// 然后找島嶼，找到島嶼加1，并淹沒(méi)
function closeIsland(grid) {
// 通過(guò)dfs將島嶼淹沒(méi)
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;
}
// 將當(dāng)前位置淹沒(méi)
grid[i][j] = 1;
// 將上下左右位置淹沒(méi)
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;
// 將上下邊界處的島嶼淹沒(méi)
for (let j = 0; j < n; j++) {
dfs(grid, 0, j);
dfs(grid, m - 1, j);
}
// 將左右邊界的島嶼淹沒(méi)
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++;
// 淹沒(méi)島嶼
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));統(tǒng)計(jì)子島嶼
一、題目
給你兩個(gè) m x n 的二進(jìn)制矩陣 grid1 和 grid2 ，它們只包含 0 （表示水域）和 1 （表示陸地）。一個(gè) 島嶼 是由 四個(gè)方向 （水平或者豎直）上相鄰的 1 組成的區(qū)域。任何矩陣以外的區(qū)域都視為水域。
如果 grid2 的一個(gè)島嶼，被 grid1 的一個(gè)島嶼 完全 包含，也就是說(shuō) grid2 中該島嶼的每一個(gè)格子都被 grid1 中同一個(gè)島嶼完全包含，那么我們稱(chēng) grid2 中的這個(gè)島嶼為 子島嶼 。
請(qǐng)你返回 grid2 中 子島嶼 的 數(shù)目 。
示例 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 解釋?zhuān)喝缟蠄D所示，左邊為 grid1 ，右邊為 grid2 。 grid2 中標(biāo)紅的 1 區(qū)域是子島嶼，總共有 3 個(gè)子島嶼。
二、題解
// 首先將在grid1中是海水部分的在grid2中的島嶼淹沒(méi)掉，剩下的就是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中g(shù)rid1中是海水的島嶼淹沒(méi)
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) {
// 淹沒(méi)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));
