Maze
这一系列题目的要求是小球滚动直到遇到障碍才停止,最后找到出口,求出valid,shorest,shortest的变种;所以用BFS可以比较简洁的解决这一系列的问题。
1 | queue = [start] |
I
`490. The Maze
基本款,套用模版就好了
O(mn),O(mn)
1 | class Solution(object): |
II - 求最短路径
`505. The Maze II
可以考虑Dijkstra’s algorithm,在Python使用heapq最小堆,因为每一次都要记录当前路径,所以需要记录local_count
1 | count,i,j = heapq.heappop(pq) |
时间:O(mn*log(mn)) – 用heapq方法每次heapify的时候是Log级别的复杂度
空间:O(mn)
1 | import heapq |
III - 遇到洞
`499. The Maze III
同样道理,只需要添加条件在while循环里,然后在dir里面加入dir的字符,heap的时候
1 | if [row,col] == destination: |
时间:O(mn*log(mn)) – 用heapq方法每次heapify的时候是Log级别的复杂度
空间:O(mn)
1 | class Solution(object): |
Matrix
01 Matrix
`542. 01 Matrix
Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.
The distance between two adjacent cells is 1
用类似的思维,在Queue中只加入0的点,然后预设其他的点到0的距离为无穷大,这样的话,遍历的时候四个方向每次加1;遇到重复的时候取最小值就好
T O(mn)
S O(mn)
1 | def updateMatrix(self, rooms): |
286. Walls and Gates
几乎一摸一样的题,除了题目中的1改为inf
1 | # init |