通过LeetCode 210课程表 II学习图
程序员文章站
2022-03-27 21:05:20
通过LeetCode 210课程表 II学习图用python实现图python的图可以通过dict很简单的实现, 例如下面这张图可以这样表示:Map = {}Map['s'] = ['a', 'd']Map['a'] = ['s', 'c', 'b']Map['b'] = ['a', 't']···这样可以很轻易的知道每个元素相连的元素代码实现class Solution: def findOrder(self, numCourses: int, prerequisites...
通过LeetCode 210课程表 II学习图
用python实现图
python的图可以通过dict很简单的实现, 例如下面这张图
可以这样表示:
Map = {}
Map['s'] = ['a', 'd']
Map['a'] = ['s', 'c', 'b']
Map['b'] = ['a', 't']
···
这样可以很轻易的知道每个元素相连的元素
代码实现
class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
#制图
l = {}
for i in prerequisites:
if i[0] in l:
l[i[0]].append(i[1])
else:
l[i[0]] = [i[1]]
#判断是否有重复
T= True
def check(ed, n):
global T
if n in l:
for i in l[n]:
if i in ed:
T=False
return
else:
check(ed+[n], i)
for i in range(numCourses):
check([], i)
if not T:
return []
#得到一个排序
already = {}
rl = []
def get_next_lesson(n):
if n in already:
return
if n in l:
for i in l[n]:
get_next_lesson(i)
rl.append(n)
already[n] = 1
for i in range(numCourses):
get_next_lesson(i)
return rl
运用图的时候要注意:
1.查找过的元素不需要使用第二次
2.使用前先确定这个元素是否存在
这其实概括了dict的作用:查找重复, 缓存, 映射
其实我感觉check和get_next_lesson可以合在一起,而且纯深度优先算法感觉也不太好
本文地址:https://blog.csdn.net/albert_fifth/article/details/110491395
下一篇: 传感器在未来的五大发展