题目介绍 一道面试时频繁被问及的题目，而且还换着花样问。 给定一个整形数组，找到数组中第 K 大的元素。 还是老样子，光看题目没啥意思，还是思考思考这个算法能有什么实际的用处。其实应用就是把这里的整形数组换成是有意义的数据，比如说是一堆学生的成绩，找出排名第 K 的学生，或者是一个医院的体检报告，找出男性身高第 K 高的。 可能固定数组的应用场景固定，但假如说这里是实时的流数据，应用...

场景再现 学习设计模式的一个比较好的方式是在实际场景中来试着应用。首先我们还是来看一个实际的场景，很多公司都有自己的数据中心，我们试着定义一个数据中心的类： class DataCenter { // ... private Object employeeData; private Object companyData; private Object humanResou...

场景再现 和之前一样，在介绍具体的设计模式前，我们还是来看一个案例，这样可以让我们理解这个模式的应用场景以及它所解决的问题。 假设有一家餐厅为顾客提供定制化的菜品，顾客在菜单上面挑选菜品后，可以对菜品提一些个性化的要求，比如多加某种食材或是某种调料，也可以对烹调方式进行要求，根据顾客的要求不同，最后的菜品价格也会有所不同，我们可以得到下面这个结构： abstract class Dis...

堆排序算法介绍 在之前的 文章 中，我们介绍了堆这个数据结构，并且给出了它的各项操作的实现。 堆最主要的特性是可以在 O(1) 的时间里获取一个数据集中的最值。在之前的 文章 中，我们也详细推导了构建一个含有 N 个元素的堆只需要 O(N) 的时间。并且我们其实都知道，从堆中删除一个元素（一般是删除最值）只需要 O(logN)。 知道了这些，我们能否基于堆的这些特性来对一组数据进行排序...

模版所解决的问题 在介绍设计模式之前，我们先来看一个具体的编码问题。餐馆为了保证菜品的出菜速度与质量，都会有流程化管理，对于每道菜来说，都有一系列的操作步骤，比如下面这个类表示的就是中餐的一个大致流程： class ChineseDishes { public void prepareDish() { prepareIngredient(); cut(); f...

Splay 树的基本定义 关于平衡二叉搜索树，我们介绍过 AVL 树。AVL 树通过旋转来保证了相对严格的自平衡，这样操作复杂度是 O(logN)。 今天我们要介绍的 Splay 树也是一个平衡二叉树，但是它并没有像 AVL 树那样去严格地保证树的平衡性，每次当 AVL 树的结构发生变化，就找到相应的节点进行调整。对于 Splay 树来说，不管是什么样的操作，读、写、更新以及删除，Spl...

背景介绍 在介绍这个算法之前，我们先来说说文件压缩与编码到底是怎么一回事。 我们知道计算机是基于二进制的，也就是说任何信息到最后其实都变成了类似 0101101010101... 这样的序列。文件中存储的也是这样的序列。但你会说，不对呀，为什么我打开文件看到的是具体的文字和内容。这就要说到编码了，通过编码，我们使得这样的序列变得有意义了。 比如最常见的 ASCII 编码，就是对一些英文...

适配器模式是什么？ 什么是适配器？什么又是适配器模式？看到 “适配器” 这 3 个字，你可能会觉得很陌生，但这其实在我们生活中随处可见。适配器其实就是转换器，或者说是转换接口，比如说你没办法将 USB-C 的设备插到 USB-B 的接口上，这时你就需要 USB-C 到 USB-B 的转换接口，电源转换器也是同理。 放到面向对象当中，很多时候我们需要去使用一个对象，但是我们现有的接口并不能...

应用场景和解决的问题 单例模式的主要目的是对资源开销，或者说是对对象的创建进行管理。在很多的应用场景中，一个对象是可以被许多应用所共同使用的，我们并不希望对不同的应用重复创建对象。比如说一个数据库的连接管理对象，线程池的管理对象等等。这些对象对任何的应用不会有差别，一个对象完全可以覆盖所有的应用场景，在此场景下，单例模式就能够很好地对对象的构建进行封装和管理。 除了保证全局只有一个对象，...

左倾堆的特性 之前在二项堆的 文章 中提到了普通二叉堆存在的问题，主要就是没法对两个堆进行高效的合并。二项堆可以解决这个问题，除了二项堆以外，今天我们要讲的左倾堆也可以解决这个问题。 在介绍左倾堆之前，有一个概念叫做 零距离（Null Path Length）。对任意一个节点 x，零距离 npl(x) 等于其到最近一个没有两个子节点的节点（不满节点）的长度。 左倾堆是一个特殊的二叉树，...