LRU算法的实现（Python版）
上文Go现LRU算法，给出了Go语言的实现。本文使用Python给出实现，体会两种语言的差别和美丽。
Python3标准库中functools.lru_cache已经实现了LRU算法，但Python2中并没有。对于兼容两个版本的开发，需要使用Python实现兼容functools.lru_cache接口的LRU算法。从源码看，functools.lru_ca...
MySQL的存储引擎
MySQL在实际运行过程中根据不同的表类型有不同的存储引擎。在实际业务中，不同的场景需求要求表的设计和特性不同（比如高写入低读取）也会使用不同的储存引擎。本文总结MySQL的存储引擎及其对比和应用差别。
登录MySQL输入show engines。会列出如下表（只显示部分字段）：
12345678910111213+--------------------+...
基于hash的有序字典的两种实现
字典的实现有多种方法，性能较高的有树类的实现和基于hash的实现。前者查找的时间复杂度为O(lgN)，后者查找的时间复杂度为O(1)。当然，这两个时间级别是在数量级别上的对比，并不是实际单个键值查询时的性能对比。因为基于hash的字典本身的查询性能取决于hash函数的性能、质量。如果hash函数设计得非常慢，单个键值的查询基于hash实现的字典不一定比树类实...
Go实现信号量Semaphore
信号量(Semaphore)是进程间通信的方式之一，通过P操作，信号量减1；V操作信号量加1。如果信号量为零，阻塞操作的进程。关于这部分不展开讨论了。
在并发编程上，很多语言都支持信号量。例如Java的java.util.concurrent.Semaphore，Python的threading.Semaphore，但Go就没有信号量，在标准库中有一类似的对...
基于Go的slice实现的栈式操作
实现栈结构的常规思路是采用链式结构，用过指针和栈有关的属性值实现、控制栈的接口和规范。另外一种思路是采用数据组，把栈操作的数据保存在数组中。但采用数据的一个特点是，数组的大小是确定的，当需要改变数据的存储容量时需要重新分配内存和拷贝数据。
基于go内置的数据结构slice，可以实现灵活的栈结构。类实地，实现队列、堆、优先队列都可以使用Slice结构存储元素。...
散列函数与字典
散列又称为哈希（hash）它本身就是一个整数值，在不同的数制系统下有不同的表示，例如在16进制下的表示。但散列的整数值具有特殊的意义，它对应于一段字符串。一段字符串在给定的散列函数下生成确定的散列值，我们可以用以下的方式表示：
1address = Hash(string)
我们认为address和string有对应关系，根据address我们可以快速确认s...
栈的链式结构实现（Go语言版）
继上文基于的slice实现的栈式操作后，本文给出栈的链式存储结构的实现方式。
首先我们要定义结点，处于通用性考虑，我们希望每个结点能存储不同的数据类型，于是我们使用interface{}，它相当于一个包装，兼容不同的数据类型，解包的时候（拆解出具体的类型）使用如下的方式(interface{}).(*Node)。
结点...
Go实现Huffman Tree
关于哈夫曼树的知识见旧文哈夫曼树和哈夫曼编码的原理和实现。本文讲解Huffman Tree和Huffman Code的Go语言实现。对比旧文中Python的实现，可以体会到Go语言具有Python一样的简洁和效率。Go语言内置了map数据结构，我们不自己实现。
接下来的实现，使用了Go语言的map、slice、struct，尽量使用Go语言标准库自带的元素，...
优先队列的五种实现
本文讲述优先度列的五种实现方式，分别如下
无序数组
有序数组
链表
堆
二叉搜索树
然后分析一个问题。
优先队列是一种队列，它满足优先级别最高的先出队列。它的一个重要的应用时海量数据的排序，当我们需要找出10亿数据中的Top10项，不实际的解决方案是对所有数据排序，取Top10项。使用优先队列可以在很小的辅助空间内找出Top10项。具体思路如下：（1）建...
二叉搜索树的原理、实现和应用
二叉搜索树（binary search tree）是一种特殊的二叉树，满足如下性质：（1）每个结点的关键码大于其左子树结点的关键码（如果有的情况）（2）每个结点的管家码小于其右子树结点的关键码（如果有的情况）（3）根据（1）和（2）BST不允许有重复的键值
由于是树形结构，在理性的情况下，搜索BST的时间复杂度为O(lgN)。如果我们从竖直向下的方法投影BS...
二叉树的遍历和二叉树迭代器
二叉树的遍历方法有五种：（1）前序遍历（2）中序遍历（3）后序遍历（4）深度优先遍历（5）广度优先遍历（层次遍历）单这些遍历算法并不具有通用性。需要使用更通用的方法访问结点对象，于是我们在遍历二叉树上添加迭代功能。
为了方便遍历二叉树的所有结点，我们想为二叉树添加迭代功能，以实现通用的迭代工具。
二叉树的遍历算法我们定义二叉树的结点：
123456class...
数字在排序数组中出现的次数（算法38）
问题：统计一个数字在排序数组中出现的次数，输出统计后的次数。
原理：
一个直观的解法就是扫描序列统计出指定数字的个数，但这个思路并没有用上序列是排序的情况。如果序列是排序的，我们先找出该数字在序列中的区间，那么区间的长度就是数字出现的次数。那么如何找出给定数字在序列中的区间呢？有两种思路：
（1）使用双指针，序列前后同时扫描（2）使用二分查找，分表找到数字的...
实现Singleton模式（算法2.1）
问题：Java中，在不使用synchronized和lock的情况下如何实现线程安全的单例模式？
原理：
本文给出三种思路，它们本质上都是借助ClassLoader线程安全的特点。原理部分在实现下详细讨论。
解答：
思路一：
使用静态内部类。
1234567891011public class Singleton { private stat...
哈夫曼树和哈夫曼编码的原理和实现
哈夫曼(Huffman)树是最优二叉树，基于哈夫曼树数据结构的编码方案称为哈夫曼编码，是一种常见的压缩编码。在这个数据指数递增的时代，高效的数据编码方案的意义不言而喻。构建哈夫曼树的过程和其他树类数据结构不过，它是自底向上。正是这个构建过程，使得编程实现该数据结构变得新奇。哈夫曼编码是不等长编码，稍后的实现中我们可以理解不等长编码的缘由。本文先简述哈夫曼树、...
圆圈中最后剩下的数字（算法45）
问题：0,1,2,…，n-1这n个数字排成一个圆圈，从数字0开始每次从这个圆圈里删除第m个数字。编程求解圆圈里最后剩下的数字。
该问题就是约瑟夫（Josephuse）环问题。
原理：
解决该问题又两种思路：（1）通过模拟环的删除过程找到最后一个剩余的数字（2）使用动态规划方法
思路一的难点是编程实现这个模拟过程，但直观。第二种思路使用动态规划，需要我们找到删...
栈的压入、弹出序列（算法22）
问题：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。
假设：压入栈的所有数字均不相等。
例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
其实模拟这个压入、弹出的过程即可，如果第一个序列表示栈...
连续子数组的最大和（算法31）
问题：输入一个数组，数组中一个或多个联系的数组成子数组，求所有子数组的和的最大值。
原理：
解决该问题有两个思路：（1）扫描累加（2）动态规划
思路一
以[1, -2, 3, 10, -4, 7, 2, -5]为例。初始化和r为0，扫描数组，加上1后r为1，加上-2后r为-1，加上3后，r为2，r比3本身还要小，因此可以抛弃3先前的和。r的累加从3开始。继续...
