LC吐血整理之Graph篇

Posted on | In
人生苦短 我学python

所有题解方法请移步 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
一个简单的DAG ⭐ 伪代码 

1
2
3
4
5
6
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： 求两个数的最大公约数 

1
2
3
4
5
def gcd(a,b):
    if b!=0:
        return gcd(b,a%b)
    else:
        return a