所有题解方法请移步 github-Leecode_summary
133. 克隆图
DFS&BFS 有整理过对象赋值、深拷贝、浅拷贝的关系，所以理解题目之后还是不难的，跟着原Graph遍历一遍并存储即可，注意两个Graph不能出现直接赋值的情况。（看完题解DFS，写的很不错~
399.除法求值
构建图+DFS
310.最小高度树
写在前面：我是用bfs获取每个顶点作为根节点时树的深度去做的，在运行55/66个案例时提示超时，好不容易能写出程序，一写就超时，我太难了...，看完题解，嗯？拓扑排序，好像之前写207题遇到过，根本没想到这些套路
类似题型：课程表I
课程表II
⭐ 拓扑排序
拓扑排序算是有向无环图 (directed acyclic graph, DAG) 的一种遍历方法，满足一定的条件：图中任意一对顶点<u, v>∈E(G)，则u在遍历结果中必须出现在v之前，拓扑排序结果可能不唯一。
拓扑排序可以用于检测图中是否有环。
举例来说：如果将一系列需要完成的任务构成一个有向图，运用拓扑排序能得到满足条件的任务执行顺序。
⭐ 通用代码
几点概念：
顶点的度(degree): 图中和该顶点相关联的边数，在有向图中通常分为入度和出度。
入度(in-degree)：图中指向该顶点的边数
出度(out-degree)：图中从该顶点出发的边数
一个简单的DAG
# 伪代码
def topological_sort():
built the graphdict and indegree[]
取得所有indegree = 0 的结点加入队列
遍历队列中所有indegree = 0 结点的graphdict ，将其 indegree-1
if 满足 indegree == 0：添加到遍历队列中
直到队列为空
149. 直线上最多的点数
最开始我是用斜率相等做的，但很多情况都没有考虑：
① 重复点的处理
② 如果直接算斜率相等，float类型因为不精确所以报错（正好之前python取整中有提到decimal，可以考虑一下这个）
③ 怎么唯一表示斜率呢？？题解告诉我了...化简dy/dx
今日份的Tips： 求两个数的最大公约数
def gcd(a,b):
if b!=0:
return gcd(b,a%b)
else:
return a
a = a//gcd(a,b)
b = b//gcd(a,b)
网友评论