经典算法与数据结构

0

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

刘毅 2019-12-28 发布
收藏

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

0

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

刘毅 2019-12-27 发布
收藏

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

0

向量积与线段相交问题

刘毅 2019-12-22 发布
收藏

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

0

凸包问题

刘毅 2019-12-22 发布
收藏

在一个二维坐标系中，有若干点杂乱排列着，将最外层的点连接起来构成的凸多边型，它能包含给定的所有的点，这个多边形就是凸包。

4

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

刘毅 2017-05-19 发布
5 收藏

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

19

二叉树操作（面试必备）

刘毅 2017-03-27 发布
33 收藏

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

1

线索二叉树

刘毅 2017-03-26 发布
3 收藏

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

5

01背包问题

刘毅 2017-03-17 发布
5 收藏

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

9

二分查找（面试必备）

刘毅 2017-03-15 发布
12 收藏

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

10

扩展KMP算法

刘毅 2017-03-12 发布
8 收藏

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

24

KMP 算法

刘毅 2017-03-05 发布
24 收藏

给定一个主串（以 S 代替）和模式串（以 P 代替），要求找出 P 在 S 中出现的位置，此即串的模式匹配问题。

33

Manacher 算法

刘毅 2017-02-25 发布
19 收藏

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

9

单链表操作（面试必看）

刘毅 2017-02-23 发布
19 收藏

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

0

理解和计算算法复杂度

刘毅 2017-02-13 发布
收藏

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

8

BFPRT 算法（TOP-K 问题）

刘毅 2017-02-11 发布
4 收藏

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