Notes: Implement DFS 的时候，有几种情况.
（1）在条件满足的base case下return 1，这样层层收集起来，也可以在那里update全局变量，比如self.res += 1.Python前者效率更高一点。
（2）修改的list作为参数传来传去，可能会直接call dfs，这样让最低层的先修改/累加了count list的值，然后上层的直接用count list里面的数累加。这种以修改参数为手段的，只要先call dfs的node,相应的数据在list里面就有了。要同时update两个信息的，一般就用参数传递法，而不是return收集法。
Visited set有两种形式。
格式一：(preferred)
主函数里面Call self.dfs_dist(root,set(),sesult,graph)
def dfs(self,cur,visited,result,graph):
visited.add(cur)
for nei in graph[cur]:
if nei in visited: continue
#modify result
self.dfs(nei,visited,result,graph)
格式二：
主函数里面Call self.dfs_dist(root,{root},sesult,graph)
def dfs(self,cur,visited,result,graph):
for nei in graph[cur]:
if nei in visited: continue
#modify result
visited.add(nei)
self.dfs(nei,visited,result,graph)
visited.add(nei)
Catalog:
LC 351 unlock android pattern
LC 489 Robot Room Cleaner
LC 694 Number of distinct island
LC 711 Number of distinct island II (rotation allowed)
to-do
[Uber] LC 133 Clone Graph
- DFS
- do it without recursion
[Uber]Number of Islands , use BFS or DFS ! Follow up, Number of Islands II, use Union Find.
Onsite面经： 给定一个手机屏幕，屏幕上有0，1，2，..., 9 总共10个数字，这10个数字按照如下排列。
1 2 3
4 5 6
7 8 9
0
当按一个digit后，下一个输入的digit只能是其上下左右四个neighbor之一。 例如 123是valid的输入，但是122和128不是. 问给定n， 有多少个n-digits numbers 符合上述条件？
LC 351 Android Unlock Patterns
给1-9的九宫格，滑动解锁，m-n个元素组成的有效pattern.
Rules for a valid pattern:
Each pattern must connect at least m keys and at most n keys.
All the keys must be distinct.
If the line connecting two consecutive keys in the pattern passes through any other keys, the other keys must have previously selected in the pattern. No jumps through non selected key is allowed.
The order of keys used matters.
Invalid move: 4 - 1 - 3 - 6
Invalid move: 4 - 1 - 3 - 6
Valid move: 6 - 5 - 4 - 1 - 9 - 2
Line 1 - 9 is valid because it passes through key 5, which had been selected in the pattern.
1-8 is valid here.
class Solution(object):
def numberOfPatterns(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
skip = {}
skip[(1,7)] = 4
skip[(1,3)] = 2
skip[(1,9)] = 5
skip[(2,8)] = 5
skip[(3,7)] = 5
skip[(3,9)] = 6
skip[(4,6)] = 5
skip[(7,9)] = 8
def dfs(used, last,remaining):
res = 0
if not remaining:
return 1
for j in range(1, 10):
if j not in used: # if j is not used
# Sort the vertices of the edge to search in skip
edge = (min(last, j), max(last, j))
if edge not in skip or skip[edge] in used:
res += dfs(used + [j], j,remaining-1)
return res
ans = 0
for i in range(m,n+1):
ans += dfs([1], 1,i-1)*4
ans += dfs([2], 2,i-1)*4
ans += dfs([5], 5,i-1)
return ans
LC 489 Robot Room Cleaner
不知道房间的格局，不知道机器人的起始地点，保证机器人能打扫整个房间。机器人move()返回bool表示能否moving up.
容易忽略的点：visited在DFS的参数中传递。
策略：每个方向都去DFS，比如一直往上，走到顶，然后在那个格子四个方向都去尝试move and clean，4次转身后这个点的DFS结束，转身退回上一步，同样的4个方向走到底。
class Solution(object):
def cleanRoom(self, robot):
"""
:type robot: Robot
:rtype: None
"""
self.dfs(robot, 0, 0, 0, 1, set())
def dfs(self, robot, x, y, direction_x, direction_y, visited):
robot.clean()
visited.add((x, y))
for k in range(4):
neighbor_x = x + direction_x
neighbor_y = y + direction_y
if (neighbor_x, neighbor_y) not in visited and robot.move():
self.dfs(robot, neighbor_x, neighbor_y, direction_x, direction_y, visited)
robot.turnLeft()
robot.turnLeft()
robot.move()
robot.turnLeft()
robot.turnLeft()
robot.turnLeft()
direction_x, direction_y = -direction_y, direction_x
LC 694 Number of distinct island
岛屿的形状相同就算是同样的，但不考虑rotation, reflection.
方法一：按“顺序“DFS遍历岛屿的路径，相同形状的岛屿会是一样的。
注意点：1.DFS修改1相当于visited作用 2."b"在路径里很重要
class Solution:
def numDistinctIslands(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
self.steps = ''
distinctIslands = set()
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 1:
# 'o' for origin
self.helper(grid, i, j, 'o')
distinctIslands.add(self.steps)
self.steps = ''
return len(distinctIslands)
def helper(self, grid, i, j, direct):
if 0 <= i < len(grid) and 0 <= j < len(grid[0]) and grid[i][j] == 1:
self.steps += direct
grid[i][j] = 0
self.helper(grid, i+1, j, 'd') # down
self.helper(grid, i-1, j, 'u') # upper
self.helper(grid, i, j+1, 'r') # right
self.helper(grid, i, j-1, 'l') # left
self.steps += 'b' # back
LC 711 Number of distinct island II
L形状和7形状的岛屿视为同样的！
找到旋转后的coordinates --- normalize --- sort后的第一个作为base shape代表这一类的岛屿。
class Solution(object):
def dfs(self, grid, r, c, shape):
grid[r][c] = 0
shape.append((r, c))
m, n = len(grid), len(grid[0])
directions = [(0, -1), (1, 0), (0, 1), (-1, 0)]
for d in directions:
nr, nc = r + d[0], c + d[1]
if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] != 0:
self.dfs(grid, nr, nc, shape)
def rotation_norm(self, shape):
rotated_shapes = [[] for _ in range(8)]
norm_res = []
for x,y in shape:
rotated_shapes[0].append((x, y))
rotated_shapes[1].append((-x, y))
rotated_shapes[2].append((x, -y))
rotated_shapes[3].append((-x, -y)) #origin
rotated_shapes[4].append((y, x))
rotated_shapes[5].append((-y, x))
rotated_shapes[6].append((y, -x))
rotated_shapes[7].append((-y, -x))
for rs in rotated_shapes:
rs.sort()
#describe the shape based on top left point (min x coordinate)
tmp = [(0, 0)]
for i in range(1, len(rs)):
tmp.append((rs[i][0]-rs[0][0], rs[i][1]-rs[0][1]))
norm_res.append(tmp[:])
norm_res.sort() #important!!
return tuple(norm_res[0])#others can be rotated from norm_res[0]
def numDistinctIslands2(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
if not grid and not grid[0]: return 0
m, n = len(grid), len(grid[0])
res = set()
for r in range(m):
for c in range(n):
if grid[r][c] == 1:
shape = []
self.dfs(grid, r, c, shape) #raw coordinates of island
norm = self.rotation_norm(shape)
res.add(norm)
return len(res)
[Uber]LC 200 Number of Islands
|
[Uber]given二位数列，里面一堆各种字母，找到每个字母的cluster个数。每个position的neighborhood有八个，diagonal也算
ex:
a a b c
a b c c
c c c a
return [('a', 2), ('b', 1), ('c', 6)]
solution:（我菜 欢迎探讨 轻喷）
先把每个character作为key，这个character对应的所有位置（二维list）作为value弄了个map
然后对每个key中的所有positions做dfs，used为True的跳过，neighbor不在这些position里的也跳过。做一次count++，当一个key全做完了把(key,count) pair加到result list里面就行。.本文原创自1point3acres论坛
注意：
main函数自己写 还好array给了不用stdin读，要跑，跑了四个例子，都对了，本人没什么创造力，栗子都是他要求的。
follow-up:
1 time complexity -
2 我做了两次循环能不能合并成一次
