拓扑排序

对一个有向无环图G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边<u,v> ∈ E(G),则u在线性序列中出现在v之前。通常,这样的线性序列称为满足拓扑次序(Topological Order)的序列,简称拓扑序列。

阅读全文 »

从暴力枚举到双指针算法

双指针算法:双指针是算法编程中一种非常重要的算法思想。所谓双指针算法,就是指的是在遍历的过程中,不是普通的使用单个指针进行循环访问,而是使用两个相同方向或者相反方向的指针进行扫描,从而达到相应的目的。通常使用双指针算法解决的第一大类问题是:对O(n2)O(n^2)的枚举进行优化到O(n)O(n)

阅读全文 »

掐死“细节是魔鬼”的二分

二分查找是解决很多查找类题目的常用方法,它可以达到O(log n)的时间复杂度。对于浮点数的二分比较简单,但涉及到整数的二分,边界情况的考虑就显得非常重要,思路很简单,细节是魔鬼。这里总结了两套模板对解题有很大的帮助

阅读全文 »

高精度算法分析

高精度运算:是指参与运算的数(加数,减数,因子……)范围大大超出了标准数据类型(整型,实型)能表示的范围的运算。例如,求两个20000位的数的和。这时,就要用到高精度算法了

阅读全文 »