Lunski's Clutter

This is a place to put my clutters, no matter you like it or not, welcome here.

0%

200. Number of Islands

Posted on In
Symbols count in article: 3.5k Reading time ≈ 3 mins.

Given an m x n 2D binary grid grid which represents a map of ‘1’s (land) and ‘0’s (water), return 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:

1
2
3
4
5
6
7
Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

Example 2:

1
2
3
4
5
6
7
Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

找島嶼數，遞迴移除，再看移幾次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
The idea is simple if we find a 1 we remove all it's neibors recursively.
[["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]]

[[0, '1', '0', '0', '0'], 
['1', '1', '0', '0', '0'], 
['0', '0', '1', '0', '0'], 
['0', '0', '0', '1', '1']]

[[0, '1', '0', '0', '0'], 
[0, '1', '0', '0', '0'], 
['0', '0', '1', '0', '0'], 
['0', '0', '0', '1', '1']]

[[0, '1', '0', '0', '0'], 
[0, 0, '0', '0', '0'], 
['0', '0', '1', '0', '0'],
 ['0', '0', '0', '1', '1']]

[[0, 0, '0', '0', '0'], 
[0, 0, '0', '0', '0'], 
['0', '0', '1', '0', '0'], 
['0', '0', '0', '1', '1']]
done

[[0, 0, '0', '0', '0'],
 [0, 0, '0', '0', '0'], 
['0', '0', 0, '0', '0'],
 ['0', '0', '0', '1', '1']]
done

[[0, 0, '0', '0', '0'],
 [0, 0, '0', '0', '0'], 
['0', '0', 0, '0', '0'], 
['0', '0', '0', 0, '1']]

[[0, 0, '0', '0', '0'], 
[0, 0, '0', '0', '0'], 
['0', '0', 0, '0', '0'], 
['0', '0', '0', 0, 0]]
done

# T:O(nˆ2), S:O(n)
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        count = 0
        for r,row in enumerate(grid):
            for c,col in enumerate(row):
                if grid[r][c] == '1':
                    self.removeNeighbors(r,c,grid)
                    print("done")
                    count += 1
        return count      
    
    def removeNeighbors(self, r ,c, grid):
        grid[r][c] = 0 
        
        print(grid)   
        if r+1 < len(grid) and grid[r+1][c] == '1':
            self.removeNeighbors(r+1,c,grid)
        if c+1 < len(grid[0]) and grid[r][c+1] == '1':
            self.removeNeighbors(r,c+1,grid)    
        if r-1 >= 0 and grid[r-1][c] == '1':
            self.removeNeighbors(r-1,c,grid)
        if c-1 >= 0 and grid[r][c-1] == '1':
            self.removeNeighbors(r,c-1,grid)

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)

Welcome to my other publishing channels