Leetcode – and lookup set (JS)

695. The largest area of the island

Give you a binary matrix grid of size M x N.

An island is a combination of adjacent 1’s (land) that must be adjacent in all four directions, horizontal or vertical. You can assume that all four edges of the grid are surrounded by zeros (for water).

The area of an island is the number of cells on the island with a value of 1.

Calculate and return the largest island area in the grid. If there are no islands, the return area is 0.

Input: ,0,1,0,0,0,0,1,0,0,0,0,0 grid = [[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]. ,1,0,0,1,1,0,0,1,0,1,0,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,1,1,0,0,0,0 [0]] output: 6 explain: the answer should not be 11, because island only contains 1 on the horizontal or vertical direction of the four.Copy the code

/ * * *@param {number[][]} grid
 * @return {number}* /
var maxAreaOfIsland = function (grid) {
  let row = grid.length; let col = grid[0].length;
  let res = 0;
  const dfs = (i, j) = > {
    // index out of bounds returns 0
    if (i < 0 || i >= row || j < 0 || j >= col) return 0;
    // Returns 0 if the value is 0
    if (grid[i][j] === 0) return 0;
    // Set the value to 0 after the access to prevent repeated access
    grid[i][j] = 0;
    // Calculate the size of the island recursively
    return 1 + dfs(i, j - 1) + dfs(i - 1, j) + dfs(i, j + 1) + dfs(i + 1, j);
  };
  // Iterate over a two-dimensional array
  for (let i = 0; i < row; i++) {
    for (let j = 0; j < col; j++) {
      if (grid[i][j] === 1) {
        res = Math.max(res, dfs(i, j));
      } else {
        continue; }}}return res;
};

Copy the code

200. Number of islands

Given a two-dimensional grid of ‘1’ (land) and ‘0’ (water), count the number of islands in the grid.

Islands are always surrounded by water, and each island can only be formed by connecting adjacent lands horizontally and/or vertically.

Furthermore, you can assume that all four sides of the grid are surrounded by water.

Input: the grid = [[" 1 ", "1", "1", "1", "0"], [" 1 ", "1", "0", "1", "0"], [" 1 ", "1", "0" and "0" and "0"], [" 0 "and" 0 ", "0" and "0", "0"]] output: 1Copy the code

/ * * *@param {character[][]} grid
 * @return {number}* /
var numIslands = function (grid) {
  let row = grid.length; let col = grid[0].length;
  let res = 0;
  const dfs = (i, j) = > {
    // index out of bounds returns 0
    if (i < 0 || i >= row || j < 0 || j >= col) return '0';
    // Returns 0 if the value is 0
    if (grid[i][j] === '0') return '0';
    // Set the value to 0 after the access to prevent repeated access
    grid[i][j] = '0';
    dfs(i, j - 1);
    dfs(i - 1, j);
    dfs(i, j + 1);
    dfs(i + 1, j);
  };
  for (let i = 0; i < row; i++) {
    for (let j = 0; j < col; j++) {
      if (grid[i][j] === '1') { dfs(i, j); res++; }}}return res;
};

Copy the code