LeetCode题解200.number-of-islands

题目地址

https://leetcode.com/problems/number-of-islands/description/

题目描述

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input:
11110
11010
11000
00000

Output: 1
Example 2:

Input:
11000
11000
00100
00011

Output: 3

思路

如图，我们其实就是要求红色区域的个数，换句话说就是求连续区域的个数。

符合直觉的做法是用DFS来解：

• 我们需要建立一个 visited 数组用来记录某个位置是否被访问过。
• 对于一个为 1 且未被访问过的位置，我们递归进入其上下左右位置上为 1 的数，将其 visited 变成 true。
• 重复上述过程
• 找完相邻区域后，我们将结果 res 自增1，然后我们在继续找下一个为 1 且未被访问过的位置，直至遍历完.

但是这道题目只是让我们求连通区域的个数，因此我们其实不需要额外的空间去存储visited信息。
注意到上面的过程，我们对于数字为0的其实不会进行操作的，也就是对我们“没用”。 因此对于已经访问的元素，
我们可以将其置为0即可。

关键点解析

• 二维数组DFS解题模板
• 将已经访问的元素置为0，省去visited的空间开销

代码

• 语言支持：JS, python3

Javascript Code:

/*
 * @lc app=leetcode id=200 lang=javascript
 *
 * [200] Number of Islands
 */
function helper(grid, i, j, rows, cols) {
  if (i < 0 || j < 0 || i > rows - 1 || j > cols - 1 || grid[i][j] === "0")
    return;

  grid[i][j] = "0";

  helper(grid, i + 1, j, rows, cols);
  helper(grid, i, j + 1, rows, cols);
  helper(grid, i - 1, j, rows, cols);
  helper(grid, i, j - 1, rows, cols);
}
/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function(grid) {
  let res = 0;
  const rows = grid.length;
  if (rows === 0) return 0;
  const cols = grid[0].length;
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (grid[i][j] === "1") {
        helper(grid, i, j, rows, cols);
        res++;
      }
    }
  }
  return res;
};

python code:

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid: return 0
        
        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    self.dfs(grid, i, j)
                    count += 1
                    
        return count
    
    def dfs(self, grid, i, j):
        if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] != '1':
            return 
        grid[i][j] = '0'
        self.dfs(grid, i + 1, j)
        self.dfs(grid, i - 1, j)
        self.dfs(grid, i, j + 1)
        self.dfs(grid, i, j - 1)

LeetCode题解1020.number-of-enclaves

题目地址 https://leetcode-cn.com/problems/number-of-enclaves/ 题目描述 给出一个二维数组 A，每个单元格为 0（代表海）或 1（代表陆地）。 移动是指在陆地上从一个地方走到另一个地方（朝四个方向之一）或离开网格的边界。 返回网格中无法在任意次数的移动中离开网格边界的陆地单元格的数量。   示例 1： 输入…

LeetCode题解1297.maximum-number-of-occurrences-of-a-substring

题目地址（1297. 子串的最大出现次数） https://leetcode-cn.com/problems/maximum-number-of-occurrences-of-a-substring 题目描述 给你一个字符串 s ，请你返回满足以下条件且出现次数最大的 任意 子串的出现次数： 子串中不同字母的数目必须小于等于 maxLetters 。 子串的…

LeetCode题解191.number-of-1-bits

题目地址 https://leetcode.com/problems/number-of-1-bits/description/ 题目描述 Write a function that takes an unsigned integer and return the number of '1' bits it has (also known as the Ha…

LeetCode题解136.single-number

题目地址 https://leetcode.com/problems/single-number/description/ 题目描述 Given a non-empty array of integers, every element appears twice except for one. Find that single one. Note: Your…

LeetCode题解1218.longest-arithmetic-subsequence-of-given-difference

题目地址 https://leetcode-cn.com/problems/longest-arithmetic-subsequence-of-given-difference/ 题目描述 给你一个整数数组 arr 和一个整数 difference，请你找出 arr 中所有相邻元素之间的差等于给定 difference 的等差子序列，并返回其中最长的等差子序…