This article is participating in the nuggets team number online activity, click to see the dachang spring recruiting positions

LeetCode 200. Number of Islands

1. Title Description

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.

Example 1:

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

Example 2:

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

P. :

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300
  • Grid [I][j] = ‘0’ or ‘1’;

Second, train of thought analysis

Go through all the places: starting with the first land you encounter, mark it as visited, and “do so” for the surrounding lands that have not been visited. Finally, that island has been visited, and then the number of islands that can be recorded is increased by 1. The next piece of land to be found is the next island territory, and so on until all the places have been covered.

You can use either DFS or BFS.

Time complexity analysis

Everything is accessed, and it’s only accessed once, so the time is O(m*n).

Spatial complexity Analysis – How to express “access”?

Idea 1: You can use a two-dimensional bool array with space complexity O(m*n). Idea 2: Notice that in traversal, the logic is the same for crossing the boundary, encountering water, and already visiting land — ignore it. Therefore, if you can modify the grid, you can directly set the visited land to “0”. The space complexity is order 1.

How to express “visit around”?

Idea 1: Write directly. For the upper and lower left and right, respectively to judge whether the boundary is crossed, whether it is land and water, etc., similar code to write (copy) 4 copies. [0,1],[0,-1],[1,0],[-1,0],[-1,0] In each round of traversal, the current position plus deviation to get a new position, determine whether the boundary, whether the logic of land and water can be written once.

AC code

Python3 is implemented in DFS

    def numIslands(self, grid: List[List[str]]) - >int:
        rows = len(grid)
        if rows == 0: return 0
        cols = len(grid[0])
        if cols == 0: return 0

        # Traverse a certain land area of the island until all the land of the island becomes water
        def dfs(i,j) :
            grid[i][j] = '0'
            # Visit around
            neighbors = [ [0, -1], [0.1], [1.0], [...1.0]]for x,y in neighbors:
                x += i
                y += j
                if x < 0 or x >= rows or y < 0 or y >= cols orgrid[x][y] ! ='1':
                    continue                
                dfs(x,y)
                
        cnt = 0 Number # island
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == '1':
                    dfs(i,j) 
                    cnt += 1 # Number of islands +1 after traversal
        return cnt
Copy the code

Four,

Often, when you need to visit or walk in one of the directions around, and you have the same idea in each direction, you can actually store the deviations in an array and iterate over them. This way you can write a lot less redundant code. There are many similar situations that require a visit around, such as chess, table walking and so on.

If you feel good, give me a thumbs-up 💐