class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
directions = [(-1, 0), (0, -1), (1, 0), (0, 1)]
m = len(grid)
if m == 0:
return 0
n = len(grid[0])
marked = [[False for _ in range(n)] for _ in range(m)]
count = 0
def dfs(i, j):
marked[i][j] = True
for direction in directions:
new_i = i + direction[0]
new_j = j + direction[1]
if 0 <= new_i and new_i < m and 0 <= new_j and new_j < n and \
not marked[new_i][new_j] and grid[new_i][new_j] == "1":
dfs(new_i, new_j)
for i in range(m):
for j in range(n):
if not marked[i][j] and grid[i][j] == "1":
count += 1
dfs(i, j)
return count
Runtime: 180 ms, faster than 17.23% of Python3 online submissions for Number of Islands.
Memory Usage: 13.8 MB, less than 67.52% of Python3 online submissions for Number of Islands.
python里面，光[0]*3，这是浅拷贝，需要[0 for _ in range(n)]才行。。
广度优先
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
from collections import deque
m = len(grid)
if m == 0:
return 0
n = len(grid[0])
marked = [[False for _ in range(n)] for _ in range(m)]
count = 0
def bfs(i, j):
queue = deque()
queue.append((i, j))
marked[i][j] = True
while queue:
cur_x, cur_y = queue.popleft()
directions = [(-1, 0), (0, -1), (1, 0), (0, 1)]
for direction in directions:
new_i = cur_x + direction[0]
new_j = cur_y + direction[1]
if 0 <= new_i and new_i < m and 0 <= new_j and \
new_j < n and not marked[new_i][new_j] and\
grid[new_i][new_j] == "1":
queue.append((new_i, new_j))
marked[new_i][new_j] = True
for i in range(m):
for j in range(n):
if not marked[i][j] and grid[i][j] == "1":
count += 1
bfs(i, j)
return count
Runtime: 196 ms, faster than 11.96% of Python3 online submissions for Number of Islands.
Memory Usage: 13.6 MB, less than 98.29% of Python3 online submissions for Number of Islands.
dfs之挖人工湖
就是把遇到的岛屿全部填成水，就可以少一个markded列表来记录了
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
m = len(grid)
if m == 0:
return 0
n = len(grid[0])
count = 0
def dfs(i, j):
if i < 0 or j < 0 or i >= m or j >= n or grid[i][j] == "0":
return
grid[i][j] = "0"
dfs(i+1, j)
dfs(i, j+1)
dfs(i-1, j)
dfs(i, j-1)
for i in range(m):
for j in range(n):
if grid[i][j] == "1":
count += 1
dfs(i, j)
return count
Runtime: 152 ms, faster than 47.88% of Python3 online submissions for Number of Islands.
Memory Usage: 13.7 MB, less than 82.05% of Python3 online submissions for Number of Islands.
光头大佬的版本
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
def sink(i, j):
if 0 <= i and i < len(grid) and 0 <= j and j < len(grid[i]) and\
grid[i][j] == "1":
grid[i][j] = "0"
list(map(sink, (i+1, i-1, i, i), (j, j, j+1, j-1)))
return 1
return 0
return sum(sink(i, j) for i in range(len(grid)) for j in range(len(grid[i])))
Runtime: 416 ms, faster than 5.14% of Python3 online submissions for Number of Islands.
Memory Usage: 14.1 MB, less than 26.50% of Python3 online submissions for Number of Islands.
