经典算法与数据结构

1

二叉查找树

• Ethson   5月5日发布
• 收藏

二叉查找树（Binary Search Tree，简称 BST），也称二叉搜索树、有序二叉树、排序二叉树，是指一棵空树或者具有下列性质的二叉树：

1

跳跃表

• Ethson   5月5日发布
• 收藏

跳跃表（英文名：Skip List），于 1990 年 William Pugh 发明，是一个可以在有序元素中实现快速查询的数据结构，其插入，查找，删除操作的平均效率都为 $O(logn)$。

1

单源最短路径（3）：SPFA 算法

• Ethson   2019-12-28 发布
• 收藏

SPFA（Shortest Path Faster Algorithm）算法，是西南交通大学段凡丁于 1994 年发表的，其在 Bellman-ford 算法的基础上加上一个队列优化，减少了冗余的松弛操作，是一种高效的最短路算法。

1

单源最短路径（2）：Bellman_Ford 算法

• Ethson   2019-12-27 发布
• 收藏

Dijkstra 算法是处理单源最短路径的有效算法，但它对存在负权回路的图就会失效。这时候，就需要使用其他的算法来应对这个问题，Bellman-Ford（中文名：贝尔曼-福特）算法就是其中一个。

1

向量积与线段相交问题

• Ethson   2019-12-22 发布
• 收藏

向量积，也称（向量）叉积，（向量）叉乘，外积，是一种在向量空间中对向量进行的二元运算。常见于物理学力学、电磁学、光学和计算机图形学等理工学科中，是一种很重要的概念。

1

凸包问题

• Ethson   2019-12-22 发布
• 收藏

原文链接：[链接] 首先介绍下什么是凸包？如下图： 在一个二维坐标系中，有若干点杂乱排列着，将最外层的点连接起来构成的凸多边型，它能包含给定的所有的点，这个多边形就是凸包。 寻找凸包的算法有很多种，Grah...

7

单源最短路径（1）：Dijkstra 算法

• Ethson   2017-05-19 发布
• 7 收藏

Dijkstra 算法（中文名：迪杰斯特拉算法）是由荷兰计算机科学家 Edsger Wybe Dijkstra 提出。该算法常用于路由算法或者作为其他图算法的一个子模块。举例来说，如果图中的顶点表示城市，而边上的权重表示城市间开...

22

二叉树操作（面试必备）

• Ethson   2017-03-27 发布
• 34 收藏

原文：[链接] 本篇针对面试中常见的二叉树操作作个总结： 前序遍历，中序遍历，后序遍历； 层次遍历； 求树的结点数； 求树的叶子数； 求树的深度； 求二叉树第k层的结点个数； 判断两棵二叉树是否结构相同； 求...

3

线索二叉树

• Ethson   2017-03-26 发布
• 3 收藏

线索二叉树的定义为：一个二叉树通过如下的方法“穿起来”：所有应该为空的右孩子指针指向该结点在中序序列中的后继，所有应该为空的左孩子指针指向该结点的中序序列的前驱。

6

01背包问题

• Ethson   2017-03-17 发布
• 5 收藏

有$N$件物品和一个容量为$V$的背包。第$i$件物品的体积是$C_i$，其价值是$W_i$。求解，在不超过背包容量情况下，将哪些物品装入背包可使价值总和最大。

13

二分查找（面试必备）

• Ethson   2017-03-15 发布
• 12 收藏

在计算机科学中，二分搜索（binary search），也称折半搜索（half-interval search）、对数搜索（logarithmic search），是一种在有序数组中查找某一特定元素的搜索算法。

12

扩展 KMP 算法

• Ethson   2017-03-12 发布
• 8 收藏

问题定义：给定两个字符串S和T（长度分别为n和m），下标从0开始，定义extend[i]等于S[i]...S[n-1]与T的最长相同前缀的长度，求出所有的extend[i]。举个例子，看下表：

29

KMP 算法

• Ethson   2017-03-05 发布
• 25 收藏

Knuth-Morris-Pratt 算法（简称 KMP）是解决这一问题的常用算法之一，这个算法是由高德纳（Donald Ervin Knuth）和沃恩·普拉特在 1974 年构思，同年詹姆斯·H·莫里斯也独立地设计出该算法，最终三人于 1977 年联合...

41

Manacher 算法

• Ethson   2017-02-25 发布
• 23 收藏

原文：[链接]给定一个字符串，求出其最长回文子串。例如：s="abcd"，最长回文长度为 1；s="ababa"，最长回文长度为 5；s="abccb"，最长回文长度为 4，即 bccb。以上问题的传统思路大概是，遍历每一个字符，以该字...

10

单链表操作（面试必看）

• Ethson   2017-02-23 发布
• 20 收藏

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

0

理解和计算算法复杂度

• Ethson   2017-02-13 发布
• 收藏

算法复杂度的表示通常用三种渐进符号：$O, Ω, Θ$。我们平时常见的都是第一个，后面两个多见于教科书。下面先介绍下这三种符号的含义和性质。

10

BFPRT 算法（TOP-K 问题）

• Ethson   2017-02-11 发布
• 5 收藏

在一堆数中求其前 k 大或前 k 小的问题，简称 TOP-K 问题。而目前解决 TOP-K 问题最有效的算法即是 BFPRT 算法，又称为中位数的中位数算法，该算法由 Blum、Floyd、Pratt、Rivest、Tarjan 提出，最坏时间复杂度为...