| 2020-02-28 背包问题 回顾 再来回顾一下背包问题，背包问题是一个典型的组合问题，目标是让我们在容量为 W 的背包中尽可能装价值越高的物品，其中每件物品都对应自己的重量 wi 和价值 vi 。前面我们通过暴力求解的方式将所有可能的组合一一列举出来，然后找到价值最高的组合。但是这样做的效率非常低，时间复杂度是指数级 Θ(2n) ，因此不能成为一种可以接受的算法。 背包 如用动态规划来解决背包问题，事情就会变得简单得多。这里我们用两种方式来实现：自底向上（bottom-up）和自顶向下（top-do ...
| 2020-02-25 关于钱的两个经典问题 动态规划 在介绍动态规划（dynamic programming）前，咱们首先来清楚一个概念，重叠子问题（overlapping subproblem）。前面我们学到的分治法是将一个大问题分成若干个子问题，然后逐一解决子问题，然后合并子问题的解，从而得到原问题的解。这里的子问题之间都是相互独立的，不存在任何交集，就像归并排序一样，子序列 a 和子序列 b 的合并不会跟子序列 c 和子序列 d 的合并有任何重叠，反过来也一样。而动态规划就是专门为了解决这类子问题存在重叠的问题（ ...
| 2020-02-22 哈希 介绍 这一节我们会介绍一种新的概念：哈希（hashing）。一提到它，你可能就想到了在比特币交易中的区块链技术，不管你是挖矿还是单纯的交易，都离不开哈希算法。事实上，哈希算法还广泛地运用在银行、通讯、商业等领域，目的只有一个，那就是加密，并且加密后几乎不能被破解。 比特币 除了加密，哈希还被运用在快速查找的领域，因为它的高效性，一些主流的编程语言都采用了这种方式来做数据之间的映射。比如 Python 中的字典类型dict，以及 Java 中的HashMap。它们都能够在很 ...
| 2020-02-20 字符串匹配（TST） 回顾 这一节我们再来讨论一下字符串匹配问题。在前面的学习中我们已经知道了字符串匹配就是在文本字符串中找到模式字符串，以及它第一次出现的位置。如使用暴力求解的方法，我们将文本字符串和模式字符串对齐，然后从左往右依次比对，如果全部比对成功就返回模式字符串出现的位置；如果失败就向右移动一个单位，然后再进行比较，如果超出文本字符串的右边界就返回匹配失败。这种方式在最坏的情况下复杂度为 Θ(mn)，其中 m 和 n 分别代表模式字符串和文本字符串的长度，而在一般情况下则是线性的复杂度 ...
| 2020-02-19 计数排序 时空权衡 在前面的章节里，我们知道归并排序是一种高效的排序算法，在任何情况下时间复杂度都为 Θ(nlog n)。但是，它需要用额外的内存空间来暂时储存归并过程中的元素，因此我们可以说归并排序是以牺牲一部分内存空间来换取时间上的高效性。相反，如果存储空间有限，我们就必须以牺牲时间为代价来保证空间不被过度使用。像这样在设计一个算法的过程中同时考虑时间复杂度和空间复杂度，并且在这两者中找到一个平衡点的过程我们把它称作时空权衡（time and space trade-off）。 ...
| 2020-02-14 红黑树 介绍 上一节的内容中，我们讨论了 AVL 这种自平衡的树，不知道各位小伙伴有没有真正理解这种神奇的操作呢？哈哈，在这一节中，你将会遇到更神奇，同时也更复杂的算法来帮助我们平衡二叉树。下面就让我们的红黑树浓重登场吧！ 红黑树 红黑树（red-black tree）也是自平衡的二叉树，在介绍它是如何做到自平衡之前，我们首先来了解一下它的性质。 性质 1：所有节点必须为红色或黑色 性质 2：根节点为黑色 性质 3：所有叶子节点（NIL）为黑色 性质 4：如果节点为红色，那么其 ...
| 2020-02-10 AVL树 介绍 在二叉搜索树那一节里，我们在最后分析复杂度的时候提到了如果二叉树严重不平衡，那么它的时间复杂度会退化到线性的复杂度，例如从有序数组[1, 2, 3, 4, 5]中构建出的二叉树，就会成为一个线性表，如下图所示。 二叉树 因此，我们需要有一棵能够自动平衡的二叉树，使得每次插入、删除和查找的复杂度都接近 Θ(nlog n) 的复杂度。AVL 树就是最早被提出的自平衡二叉搜索树，它的名字来自于两名俄国的科学家 G. M. Adelson-Velsky 和 E. M. La ...
| 2020-02-06 堆与堆排序 优先队列 乘坐过飞机时你一定清楚这样一个场景，在候机厅排队登机的过程中，拥有头等舱的乘客总是能够有“特权”，不用排队就能直接登机。 登机 我们看到，坐头等舱的乘客的优先级比坐普通经济舱的乘客要高。如果用计算机里的队列来描述的话，头等舱的乘客在出队时总是先于经济舱的乘客。于是，我们可以定义出一种新的抽象数据类型，优先队列（priority queue），即所有元素都按照优先级的大小出队。举个例子，假设一个数组为 [34, 12, 56, 98, 49]，优先级的顺序为 [4 ...
| 2020-02-04 霍纳法则 多项式计算 在计算机科学里，有时会遇到很多关于计算多项式的问题，例如 2x4 - 3x3 + 5x2 + x - 7。我们首先能够想到的方法就是求出每一项的值，然后把它们全部加起来。如果多项式的阶数不高，这种方法完全可行，甚至更容易理解，可是如果把这个问题推广到 n 阶，即计算 anxn + an-1xn-1 + ··· + a2x2 + a1x + a0 的值，并且当 n 很大时，这种算法就显得力不从心了。 这里以 x = 4 为例来计算多项式 2x4 - 3x3 + 5x ...
| 2020-02-02 预排序 变治 变治（transform and conquer）也是一类解决问题的方法。前面的减治和分治都是针对问题本身进行求解，并没有对问题的实例做任何的变换。变治法就是将实例从一种形式转换为另外一种形式的方法。这样听起来还是太抽象了，咱们还是拿一个具体的例子吧。 不知道大家有没有玩过一个叫做熄灯（英文叫 lights out）的游戏。规则很简单，以下面的图片（来源：维基百科）为例，面板上分布着 5 × 5 的格子，每个格子的灯都是亮着的，且灯只有亮着和熄灭两种状态，每按一次格子， ...
