背景 假如我们要传输一段文本，比如“hello”，怎么办？最容易想到的方法是，直接依次传输每个字符的Unicode，每个字符都用8个比特或以上来传输。这样就需要58=40个比特来传输。但是如果我们要传输一段很长的文本怎么办呢？产生的数据量是非常大的，为了节省成本，我们必须要把数据压缩，并且能保证对方接收到压缩的数据可以百分百解读出来原始的信息。 事实上，一段文本中每个字符出现的频率是不同的，比如英文中字母e出现的频率通常是最高的，而z的出现频率要远远低于e。因此可以想到，让出现频率高的字符占用较少的比特。 还是以上面的“hello”为例，因为l出现了2次，而h、e、o只出现了1次，所以l就用1...

假设你有n个任务要做，其中某些任务需要在另外一些任务之前完成，你该如何规划你的任务，使得按照你的规划依次做下去就能完成你的所有任务？ 定义 拓扑排序（Topologicalsorting,toposort）：给定一个有向无环图，将所有节点排成一个线性序列，在这个序列中只有从前面的节点指向后面的节点的边。 条件 有向图中没有环。如果有环的话就无法进行拓扑排序。因为如果尝试将所有节点排成一个线性序列的话，就必然会出现这种情况： 必然有从后面的节点指向前面的节点的有向边，不符合拓扑排序的定义，所以无法对有环的有向图进行拓扑排序。 假如你手边有两个任务A和B，要完成任务A你得先完成任务B，要完成任务...

定义 如果在一个图中，删除某个节点连同与之关联的边，会导致整个图的连通分支数增加，那么这个节点叫做割点（ArticulationPoint,CutVertex） 如下图： 整个图的连通分支数为1，但是删除节点3后，整个图就“分裂”成了2个连通分支： 因此，节点3是整个图的割点。 方法 一个很容易想到的方法是，依次删除图中的每一个节点，看剩下部分的连通分支数增没增加。但是那样显然太浪费时间了！有没有一种办法，能够快速的找出整个图的割点呢？ Tarjan算法的核心思想：深度优先遍历(DFS)这张图，得到的DFS树（由遍历路径和节点构成的树）中，当某个节点u满足以下条件之一时，它就是割点： u...

在有向图的拓扑排序——BFS这篇文章中，介绍了有向图的拓扑排序的定义以及使用广度优先搜索（BFS）对有向图进行拓扑排序的方法，这里再介绍另一种方法：深度优先搜索（DFS）。 算法 考虑下面这张图： 首先，我们需要维护一个栈，用来存放DFS到的节点。另外规定每个节点有两个状态：已访问（这里用蓝绿色表示）、未访问（这里用黑色表示）。 任选一个节点开始DFS，比如这里就从0开始吧。 首先将节点0的状态设为已访问，然后节点0的邻居（节点0的出边指向的节点）共有1个：节点2，它是未访问状态，于是顺下去访问节点2。 节点2的状态也设为已访问。节点2有3个邻居：3、4、5，都是未访问状态，不妨从3开始...

阅读本文前，请确保您已经了解了二叉搜索树的相关内容（如定义、增删查改的方法以及效率等）。否则，建议您先学习二叉搜索树。本文假定您对二叉搜索树有了足够的了解。 效率？ 众所周知，在平衡条件下，对二叉搜索树中的元素进行增删查改，时间效率为\(O(log(n))\)。 然而，理想很丰满，现实很骨感，实际上，二叉搜索树并不总是能够保持平衡状态。 最极端的情况就是，除了叶节点之外，每个节点只有一个子节点，如图所示： 这种情况下二叉搜索树已经退化成一个链表，时间复杂度达到了\(O(n)\)，二叉搜索树在时间效率上的优势并没有发挥出来。 要想解决这个问题，我们就要在每次动态操作（插入、删除）之后，采取某种...

相信不少人在学数据结构的时候都被KMP算法搞的迷迷糊糊的，原理看的似懂非懂，代码写不出来，或者写出来了也不知道为什么就可以这么写。本文力求尽可能通俗详细的讲解KMP算法，让你不再受到KMP算法的困扰。 暴力匹配的痛点 所谓暴力匹配，就是从文本串的首端开始依次检查子串是否与模式串匹配，如果不匹配就将模式串往后移一个位置，从头开始匹配，直到在某处成功匹配或匹配到末尾也没能成功匹配。如下图： 设文本串为T，模式串为P，i为文本串中的下标，j为模式串中的下标，文本串的长度为m，模式串的长度为n，则代码如下： intbruteForce(std::stringt,std::stringp){ inti...

定义 Dijkstra（读音：/'daɪkstrə/）算法，是用来求解一个边带权图中从某个顶点出发到达其余各个顶点的最短距离的算法。（为表达简便，下文中“起点（源点）到某个顶点的距离”简称为“某个顶点的距离”） 限制条件：各个边的权不能为负。 原理 假设s，v1，v2，...，vn（以下简称P1）为从源点s到vn的最短路，则s，v1，v2，...，vi-1（以下简称P2）也为从源点s到vi-1的最短路。 这点可以用反证法证明，假如P2不是从源点s到vi-1的最短路，那必然存在某两个m、n（1<=m<n<=i-1），使得在vm和vn之间，存在着某条更短的路径。由于P1只不过是在...

定义 BM算法是由Boyer和Moore两人提出的一种高效的字符串匹配算法，被认为是一种亚线性算法（即平均的时间复杂度低于线性级别），其时间效率在一般情况下甚至比KMP还要快35倍。 原理 BM算法跟其他的字符串匹配算法相比，其中一个不同之处是在比对字符的时候，扫描的顺序不是从左往右，而是从右往左的。 暴力匹配 所谓暴力匹配，就是从右向左比对字符，当遇到不匹配的字符时，就将模式串往右移动一个字符，循环执行，直到所有字符都能匹配上（成功），或模式串的右边界超过了文本串的右边界（失败）。如图： 代码实现： intbrute(std::stringt,std::stringp){ constintm...