经典算法与数据结构

1

你被欺骗了很久：前缀和真前缀

刘毅 2017年07月24日发布
1 收藏

相信很多读者都看过网上博客对KMP算法的讲解，其中必提及的一个名词就是：前缀。那么请问你心中理解的前缀的定义是什么呢？

4

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

刘毅 2017年05月19日发布
5 收藏

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

2

KMP算法（2）：其细微之处

刘毅 2017年05月14日发布
3 收藏

上述代码的起始下标都是从0开始的，但每个人对数组起始位置的编码习惯不同，大致分为两类：0和1。对于上面的代码，起始位置如果改为1的话又是怎样呢？

19

二叉树操作（面试必备）

刘毅 2017年03月27日发布
33 收藏

本篇针对面试中常见的二叉树操作作个总结：（1）前序遍历，中序遍历，后序遍历；（2）层次遍历；（3）求树的节点数；（4）求树的叶子数；（5）求树的深度；（6）求二叉树第k层的节点个数; （7）判断...

1

线索二叉树

刘毅 2017年03月26日发布
3 收藏

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

2

二叉树基础

刘毅 2017年03月20日发布
12 收藏

本文主要讲解以下二叉树的4个部分：（1）构造二叉树；（2）前，中，后序遍历（递归与非递归）和层次遍历；（3）求节点数；（4）求叶子数。在此先约定下二叉树的节点结构和类的结构：

5

01背包问题

刘毅 2017年03月17日发布
5 收藏

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

7

二分查找（面试必备）

刘毅 2017年03月15日发布
12 收藏

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

8

扩展KMP算法

刘毅 2017年03月12日发布
7 收藏

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

18

KMP算法（1）：如何理解KMP

刘毅 2017年03月05日发布
22 收藏

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

27

Manacher算法

刘毅 2017年02月25日发布
16 收藏

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

0

表达式求值

刘毅 2017年02月24日发布
1 收藏

所谓表达式求值，就是写一个微型计算器。例如输入：（1+9）* 2 / 2 - 1，输出9。对于这样的问题，我们一般利用栈，模拟数学运算来完成。为了简化问题，在继续下面的分析之前，先在此作个约定：本文只讨论+-*/()基...

9

单链表操作（面试必看）

刘毅 2017年02月23日发布
19 收藏

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

0

算法复杂度分析概要

刘毅 2017年02月13日发布
收藏

$O$，读作“大O”，非正式来说，$O(g(n))$是增长次数小于等于$g(n)$及其常数倍（$n$趋向于无穷大）的函数集合。定义如果函数$f(n)$包含在$O(g(n))$中，记作$f(n)∈O(g(n))$（平时使用为了方便书写，我们通常使用$...

8

BFPRT 算法（TOP-K 问题）

刘毅 2017年02月11日发布
4 收藏

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