前言 这篇文章的所有内容均出自 CSAPP 的第二章，主要讲解数据的存储和表示，算是对这部分内容的总结回顾。我们知道，计算机中的数据说到底都是 0，1 这样的二进制流，而这样的二进制流是如何表示我们熟悉的事物的呢？比如程序中的整形、浮点数以及字符串，还有二进制是如何支持变量计算的呢？这篇文章通通会给出答案。 关于这部分内容，很多书籍都会给出一句话，如果你接触过计算机，相信你或多或少也听过...

时间复杂度之外的复杂度 算法绕不开的一个概念就是时间复杂度，我们衡量一个算法的好坏基本上也就看这个指标。解同一个问题，$ O(N) $ 的做法就是会比 $ O(N^2) $ 要高效，要更节省时间。但是这里我们其实省略了一个前提条件，这些算法都是在内存中运行的。你可能会觉得奇怪，算法不在内存中运行还在其他地方运行吗？ 内存属于计算机的内部存储资源，除此之外，计算机还会和外界存储设备打交道，...

应用场景 之前看各种示例代码，iterator 是一个出现频率很高的东西，大多数时候都是在我们需要遍历一个线性的数据结构的时候会出现。当时我很不理解为什么会有这个东西，直接对数据结构使用 for 或 while 循环不是更直接也更省事吗？这个东西到底是解决什么问题呢？ 带着这些问题，我们来看一个案例，假设有一家餐厅 A 的菜单，实现如下： class RestaurantAMenu {...

红黑树原理介绍 红黑树这个名字，想必很多人都不陌生，但是真正了解的人少之又少，主要可能是因为红黑树里面的逻辑并不像动态规划、搜索这么实用。我们经常调侃，说如果红黑树被选为一个公司的面试题，那么这个公司大概率不想招人。但不管怎样，我们都无法否定红黑树的价值，你虽然不了解它，但肯定直接或间接地使用到它，比如说 Java（Java 1.8 往后） 中的 Hash 就是利用红黑树来存储发生 Has...

题目介绍 给定一个二维平面，上面有若干个点，算出距离最近的两个点的距离，可以有重合（相同）的点，这样的话两个点的距离为 0。 首先，我们先不着急着解题，先把需要定义的定义清楚，这样才有解题方向。 因为是二维平面，所以对于任意一个点 $ p_1 $，可以表示成 $ p_1 = (x_1,y_1) $，这样的话我们就可以借助 欧几里得距离 公式来计算两点间的距离。比如 $ p_1 = ...

回溯算法 如果你经常刷算法题，相信对回溯算法（Backtracking）不会陌生。回溯算法可以看成是深度优先搜索算法的特殊形式，它的目的是在所有可能性中找出最优解。通常来说会使用递归来实现， void backtracking(int params) { // pre-processing... backtracking(/* ... */); // post-proces...

回顾：工厂模式 在前面的 文章 中我们提到了 工厂方法模式，子类通过实现父类提供的抽象方法来达到对象构建的差异化，外界只需要选择合适的工厂类就可以创建出对应的对象。这样的模式下，具体的工厂类和产品类均依赖于抽象，从而实现了关系逻辑的解耦。 这里也把工厂方法模式的类关系图放在下面方便回顾以及开展我们今天的话题： 从上面的关系图可以看出，这里的工厂与产品之间的关系是一对一，也就是一个工...

场景再现 今天要讲的这个设计模式应该算是非常常用的，用好了可以大大提高代码的可维护性。我们还是从一个最为原始的场景出发，来一步步优化。 假设有一个工厂，这个工厂生产各种各样的产品，每个产品都是通过类似的一套流程进行生产，基于此，我们就有下面这个方法： class client { Product produceProduct() { Product product = ne...

基本思想 前面一篇 文章 我们介绍了归并排序，这篇文章继续介绍另一个比较型排序 - 快速排序。根据算法名称就可以知道，这个排序主打高效，快速排序被包括进 20 世纪最伟大的十大算法，也被改写衍生为其他的算法，比如我们之前提到的 快速选择，这个算法的地位和影响力相信不用我多说了。可有意思的是，从时间复杂度来看，它的最差时间复杂度是 $O(N^2)$，相比于我们前面说的归并排序，以及 堆排序，...

基本概要 要想弄理解归并排序，首先我们要知道分治的思想。严格说来，分治并不能算是一个算法，它是凌驾于算法之上的一种思想，很多具体的算法都是基于这个思想而产生的，比如今天的主角归并排序，还有后面要将的快速排序，以及之前我们介绍的 快速选择。 分治大体说来就两部分，分 和 治。我们首先将一个大的问题拆分成小问题，再对小问题进行解决，等到每个小问题都解决完毕后，大问题也就解决完毕了。那么分治这...