# **Leetcode筆記(Number of Islands)**
:::info
:information_source: 題目 : Number of Islands, 類型 : graph , 等級 : medium
日期 : 2023/04/15，2023/05/16，2023/07/13，2023/09/16，2023/11/20，2023/11/25，2024/02/13，2024/10/24，2025/02/17
:::
### 嘗試
2023/05/16
時間複雜度是 O(m * n)，其中 m 是矩陣的行數，n 是矩陣的列數。因為我們需要遍歷整個矩陣
空間複雜度是 O(m * n)
```python
dfs (stack)
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
m, n = len(grid), len(grid[0])
dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
record = []
visited = set()
def dfs(r, c):
while record:
row, col = record.pop()
visited.add((row, col))
for dr, dc in dirs:
nr, nc = row + dr, col + dc
if (0 <= nr < m and 0 <= nc < n and grid[nr][nc] == "1" and (nr, nc) not in visited):
record.append((nr, nc))
visited.add((nr, nc))
res = 0
# 因為不連續 所以另外要用一個迴圈
for r in range(m):
for c in range(n):
# 這樣被第一個node連著都在visited
if grid[r][c] == "1" and (r, c) not in visited:
# 初始化
record.append([r, c])
dfs(r, c)
res += 1
return res
```
2023/05/16
```python
bfs (queue)
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
# bfs (queue)
m, n = len(grid), len(grid[0])
dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
q = deque()
visited = set()
def bfs(r, c):
while q:
row, col = q.popleft()
visited.add((row, col))
for dr, dc in dirs:
nr, nc = row + dr, col + dc
if (0 <= nr < m and 0 <= nc < n and grid[nr][nc] == "1" and (nr, nc) not in visited):
q.append((nr, nc))
visited.add((nr, nc))
res = 0
for r in range(m):
for c in range(n):
if grid[r][c] == "1" and (r, c) not in visited:
# 初始化
q.append([r, c])
bfs(r, c)
res += 1
return res
```
2023/07/13
```python
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
m, n = len(grid), len(grid[0])
visited = set()
dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
count = 0
def dfs(r, c):
if r < 0 or c < 0 or r >= m or c >=n or (r, c) in visited or grid[r][c] == "0":
return
visited.add((r, c))
for dr, dc in dirs:
nr, nc = r + dr, c + dc
dfs(nr, nc)
return
for r in range(m):
for c in range(n):
if grid[r][c] == "1" and (r, c) not in visited:
dfs(r, c)
count += 1
return count
```
2023/09/16
不能直接船grid[nr][nc]，如果nr nc這時候本身就超過範圍，那就會錯誤
要先檢查範圍再取grid的值
```python
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
m, n = len(grid), len(grid[0])
count = 0
visited = set()
def bfs(r, c):
if r < 0 or c < 0 or r >= m or c >= n or grid[r][c] == "0" or (r, c) in visited:
return False
visited.add((r, c))
for dr, dc in dirs:
nr, nc = r + dr, c + dc
bfs(nr, nc)
return True
for r in range(m):
for c in range(n):
if bfs(r, c):
count += 1
return count
```
2023/11/20
```python
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
visited = set()
dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
res = 0
R, C = len(grid), len(grid[0])
def bfs(r, c):
if r < 0 or r >= R or c < 0 or c >= C or grid[r][c] == "0" or (r, c) in visited:
return False
visited.add((r,c))
for dr, dc in dirs:
nr, nc = r + dr, c + dc
bfs(nr, nc)
return True
for r in range(R):
for c in range(C):
if bfs(r, c):
res += 1
return res
```
2023/11/25
```python
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
n, m = len(grid), len(grid[0])
res = 0
visited = set()
dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
def bfs(r, c, grid):
if r < 0 or c < 0 or r >= n or c >= m or (r, c) in visited or grid[r][c] == "0":
return False
visited.add((r, c))
for dr, dc in dirs:
nr, nc = r + dr, c + dc
bfs(nr, nc, grid)
return True
for r in range(n):
for c in range(m):
if bfs(r, c, grid):
res += 1
return res
```
2024/02/13
```python
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
visited = set()
res = 0
dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
n, m = len(grid), len(grid[0])
def bfs(r, c):
if r < 0 or c < 0 or r >= n or c >= m or (r, c) in visited or grid[r][c] == "0":
return
visited.add((r, c))
for dr, dc in dirs:
nr, nc = r + dr, c + dc
bfs(nr, nc)
return True
for r in range(n):
for c in range(m):
if bfs(r, c):
res += 1
return res
```
2024/10/24
```python
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
self.res = 0
self.n, self.m = len(grid), len(grid[0])
self.dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
self.visited = set()
for r in range(self.n):
for c in range(self.m):
if self.dfs(grid, r, c):
self.res += 1
return self.res
def dfs(self, grid, r, c):
if r < 0 or r >= self.n or c < 0 or c >= self.m or (r, c) in self.visited or grid[r][c] == "0":
return
self.visited.add((r, c))
for dr, dc in self.dirs:
nr, nc = r + dr, c + dc
self.dfs(grid, nr, nc)
return True
```
2024/10/24
面試Google前準備，dfs / bfs 加油!!
```python
# bfs
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
self.n, self.m = len(grid), len(grid[0])
self.dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
visited = set()
res = 0
for r in range(self.n):
for c in range(self.m):
if grid[r][c] == "1" and (r, c) not in visited:
self.bfs(grid, r, c, visited)
res += 1
return res
def bfs(self, grid, r, c, visited):
q = deque()
q.append((r, c))
visited.add((r, c))
while q:
r, c = q.popleft()
for dr, dc in self.dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < self.n and 0 <= nc < self.m and (nr, nc) not in visited and grid[nr][nc] == "1":
visited.add((nr, nc))
q.append((nr, nc))
return
```
```python
# dfs
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
res = 0
self.n, self.m = len(grid), len(grid[0])
self.dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
visited = set()
for r in range(self.n):
for c in range(self.m):
if self.dfs(grid, r, c, visited):
res += 1
return res
def dfs(self, grid, r, c, visited):
if r < 0 or r >= self.n or c < 0 or c >= self.m or (r, c) in visited or grid[r][c] == "0":
return False
visited.add((r, c))
for dr, dc in self.dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < self.n and 0 <= nc < self.m and (nr, nc) not in visited and grid[nr][nc] == "1":
self.dfs(grid, nr, nc, visited)
return True
```
2025/02/17
```python
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
self.grid = grid
self.n, self.m = len(grid), len(grid[0])
res = 0
self.visited = set()
self.dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
for r in range(self.n):
for c in range(self.m):
if (r, c) not in self.visited and self.grid[r][c] == "1":
self.bfs(r, c)
res += 1
return res
def bfs(self, r, c):
if r < 0 or c < 0 or r >= self.n or c >= self.m or (r, c) in self.visited or self.grid[r][c] == "0":
return
self.visited.add((r, c))
for dr, dc in self.dirs:
nr, nc = r + dr, c + dc
self.bfs(nr, nc)
```
---
### **優化**
時間複雜度O(n)，空間複雜度O(n)
```python
# dfs
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
ROW, COL = len(grid), len(grid[0])
visit = set()
def dfs(r, c):
if (r < 0 or c < 0 or r == ROW or c == COL or
grid[r][c] == "0" or (r, c) in visit):
return
visit.add((r, c))
dfs(r + 1, c)
dfs(r - 1, c)
dfs(r, c + 1)
dfs(r, c - 1)
res = 0
for r in range(ROW):
for c in range(COL):
# 防止已經被連起來的島嶼又被dfs一次
if grid[r][c] == "1" and (r, c) not in visit:
dfs(r, c) # 都return(都撞到0了)才會通過此
res += 1
return res
```
```python
# bfs_1
from collections import deque
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
ROW, COL = len(grid), len(grid[0])
visit = set()
# iterative
def bfs(r, c):
# 初始化
queue = deque([(r, c)])
visit.add((r, c))
while queue:
r, c = queue.popleft()
directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
for dr, dc in directions:
nr, nc = r + dr, c + dc # 取代四點去循環
if (nr < 0 or nc < 0 or nr == ROW or nc == COL or
grid[nr][nc] == "0" or (nr, nc) in visit):
continue # 跳下一個循環
# 合格的話
queue.append((nr, nc))
visit.add((nr, nc))
res = 0
for r in range(ROW):
for c in range(COL):
if grid[r][c] == "1" and (r, c) not in visit:
bfs(r, c) # q為空才會通過此
res += 1
return res
```
```python
# bfs_2
from collections import deque
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
ROW, COL = len(grid), len(grid[0])
visit = set()
# iterative
def bfs(r, c):
# 初始化
queue = deque([(r, c)])
#visit.add((row, col))
while queue:
r, c = queue.popleft()
if (r, c) not in visit:
visit.add((r, c))
if r - 1 >= 0 and grid[r - 1][c] == '1':
queue.append((r - 1, c))
if r + 1 < ROW and grid[r + 1][c] == '1':
queue.append((r + 1, c))
if c - 1 >= 0 and grid[r][c - 1] == '1':
queue.append((r, c - 1))
if c + 1 < COL and grid[r][c + 1] == '1':
queue.append((r, c + 1))
res = 0
for r in range(ROW):
for c in range(COL):
if grid[r][c] == "1" and (r, c) not in visit:
bfs(r, c) # q為空才會通過此
res += 1
return res
```
---
**:warning: 錯誤語法**
:::warning
q為append
:::
**:thumbsup:學習**
:::success
:::
**思路**
**講解連結**
https://www.youtube.com/watch?v=pV2kpPD66nE
Provided by. NeetCode
https://blog.csdn.net/qq_37821701/article/details/108414557
https://blog.csdn.net/fuxuemingzhu/article/details/81126995
###### tags: `graph` `medium` `leetcode`
Sign in with Wallet
Connect another wallet