[数据结构]图

练习:Number of Islands(岛屿的个数)

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
class Solution(object):
def numIslands(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
if not grid or not grid[0]: return 0
M, N = len(grid), len(grid[0])
que = collections.deque()
res = 0
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
for i in range(M):
for j in range(N):
if grid[i][j] == '1':
res += 1
grid[i][j] = '0'
que.append((i, j))
while que:
x, y = que.pop()
for d in directions:
nx, ny = x + d[0], y + d[1]
if 0 <= nx < M and 0 <= ny < N and grid[nx][ny] == '1':
grid[nx][ny] = '0'
que.append((nx, ny))
return res

Valid Sudoku(有效的数独)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
def isValidSudoku(self, board):
"""
:type board: List[List[str]]
:rtype: bool
"""
# 注意:这里不能用[[False]*9]*9来初始化,牵涉到深浅拷贝的问题
row = [[False for i in range(9)] for j in range(9)]
col = [[False for i in range(9)] for j in range(9)]
block = [[False for i in range(9)] for j in range(9)]
for i in range(9):
for j in range(9):
if board[i][j] != '.':
num = int(board[i][j]) - 1
k = i/3*3 + j/3
if row[i][num] or col[j][num] or block[k][num]:
return False
row[i][num] = col[j][num] = block[k][num] = True
return True

相关链接

编程计划的第6个任务
第六次任务 打卡表格