二叉查找树

2020-05-05
阅读 6 分钟
1.9k
二叉查找树(Binary Search Tree,简称 BST),也称二叉搜索树、有序二叉树、排序二叉树,是指一棵空树或者具有下列性质的二叉树:

跳跃表

2020-05-05
阅读 10 分钟
4.2k
跳跃表(英文名:Skip List),于 1990 年 William Pugh 发明,是一个可以在有序元素中实现快速查询的数据结构,其插入,查找,删除操作的平均效率都为 $O(logn)$。

单源最短路径(3):SPFA 算法

2019-12-28
阅读 4 分钟
3.8k
SPFA(Shortest Path Faster Algorithm)算法,是西南交通大学段凡丁于 1994 年发表的,其在 Bellman-ford 算法的基础上加上一个队列优化,减少了冗余的松弛操作,是一种高效的最短路算法。

单源最短路径(2):Bellman_Ford 算法

2019-12-27
阅读 4 分钟
3k
Dijkstra 算法是处理单源最短路径的有效算法,但它对存在负权回路的图就会失效。这时候,就需要使用其他的算法来应对这个问题,Bellman-Ford(中文名:贝尔曼-福特)算法就是其中一个。

向量积与线段相交问题

2019-12-22
阅读 4 分钟
2.8k
向量积,也称(向量)叉积,(向量)叉乘,外积,是一种在向量空间中对向量进行的二元运算。常见于物理学力学、电磁学、光学和计算机图形学等理工学科中,是一种很重要的概念。

凸包问题

2019-12-22
阅读 3 分钟
4.5k
原文链接:[链接] 首先介绍下什么是凸包?如下图: 在一个二维坐标系中,有若干点杂乱排列着,将最外层的点连接起来构成的凸多边型,它能包含给定的所有的点,这个多边形就是凸包。 寻找凸包的算法有很多种,Graham Scan 算法是一种十分简单高效的二维凸包算法,能够在 $O(nlogn)$ 的时间内找到凸包。 Graham Scan 算法...

单源最短路径(1):Dijkstra 算法

2017-05-19
阅读 5 分钟
32.3k
Dijkstra 算法(中文名:迪杰斯特拉算法)是由荷兰计算机科学家 Edsger Wybe Dijkstra 提出。该算法常用于路由算法或者作为其他图算法的一个子模块。举例来说,如果图中的顶点表示城市,而边上的权重表示城市间开车行经的距离,该算法可以用来找到两个城市之间的最短路径。

二叉树操作(面试必备)

2017-03-27
阅读 18 分钟
24.2k
原文:[链接] 本篇针对面试中常见的二叉树操作作个总结: 前序遍历,中序遍历,后序遍历; 层次遍历; 求树的结点数; 求树的叶子数; 求树的深度; 求二叉树第k层的结点个数; 判断两棵二叉树是否结构相同; 求二叉树的镜像; 求两个结点的最低公共祖先结点; 求任意两结点距离; 找出二叉树中某个结点的所有祖先结点;...

线索二叉树

2017-03-26
阅读 7 分钟
9.2k
线索二叉树的定义为:一个二叉树通过如下的方法“穿起来”:所有应该为空的右孩子指针指向该结点在中序序列中的后继,所有应该为空的左孩子指针指向该结点的中序序列的前驱。

01背包问题

2017-03-17
阅读 3 分钟
14.2k
有$N$件物品和一个容量为$V$的背包。第$i$件物品的体积是$C_i$,其价值是$W_i$。求解,在不超过背包容量情况下,将哪些物品装入背包可使价值总和最大。

二分查找(面试必备)

2017-03-15
阅读 3 分钟
44.3k
在计算机科学中,二分搜索(binary search),也称折半搜索(half-interval search)、对数搜索(logarithmic search),是一种在有序数组中查找某一特定元素的搜索算法。

扩展 KMP 算法

2017-03-12
阅读 3 分钟
23.1k
问题定义:给定两个字符串S和T(长度分别为n和m),下标从0开始,定义extend[i]等于S[i]...S[n-1]与T的最长相同前缀的长度,求出所有的extend[i]。举个例子,看下表:

KMP 算法

2017-03-05
阅读 7 分钟
65.5k
Knuth-Morris-Pratt 算法(简称 KMP)是解决这一问题的常用算法之一,这个算法是由高德纳(Donald Ervin Knuth)和沃恩·普拉特在 1974 年构思,同年詹姆斯·H·莫里斯也独立地设计出该算法,最终三人于 1977 年联合发表。

Manacher 算法

2017-02-25
阅读 4 分钟
79k
原文:[链接]给定一个字符串,求出其最长回文子串。例如:s="abcd",最长回文长度为 1;s="ababa",最长回文长度为 5;s="abccb",最长回文长度为 4,即 bccb。以上问题的传统思路大概是,遍历每一个字符,以该字符为中心向两边查找。其时间复杂度为 $O(n^2)$,效率很差。1975 年,一个叫 Manacher 的人发明了一个算法,...

单链表操作(面试必看)

2017-02-23
阅读 8 分钟
17.4k
单链表经常为公司面试所提及,先不贬其过于简单,因为单链表确实是数据结构中最简单的一部分,但往往最简单的,人们越无法把握其细节。本文一共总结了单链表常被提及的各种操作,如下:

理解和计算算法复杂度

2017-02-13
阅读 4 分钟
5k
算法复杂度的表示通常用三种渐进符号:$O, Ω, Θ$。我们平时常见的都是第一个,后面两个多见于教科书。下面先介绍下这三种符号的含义和性质。

BFPRT 算法(TOP-K 问题)

2017-02-11
阅读 5 分钟
25.9k
在一堆数中求其前 k 大或前 k 小的问题,简称 TOP-K 问题。而目前解决 TOP-K 问题最有效的算法即是 BFPRT 算法,又称为中位数的中位数算法,该算法由 Blum、Floyd、Pratt、Rivest、Tarjan 提出,最坏时间复杂度为 $O(n)$。