一个纯正程序员的啰嗦
上半部分请参见 《排序算法一览（上）：交换类、选择类和插入类排序》。
归并类排序
归并排序（Merge Sort）
归并排序是一种分治法，它反复将两个已经排序的序列合并成一个序列（平均时间复杂度 O(nlogn)，最好时间复杂度 O(n)）：
public class Sort {
public s
[……]阅读全文
[……]阅读全文
Trie 树，又叫做前缀树或者是字典树，是一种有序的树。从空字符串的根开始，往下遍历到某个节点，确定了对应的字符串，也就是说，任意一个节点的所有子孙都具备相同的前缀。每一棵 Trie 树都可以被看做是一个简单版的确定有限状态的自动机（DFA，deterministic finite automaton），也就是说，对于一个任意给定的属于该自动机的状态 (①) 和一个属于该自动机字母表的字符 (②)，都可以根据给定的转移函数 (③) 转到下一个状态去。其中：
[……]阅读全文
一篇文章存成一个巨大的文件，总共大约有一亿个单词，要找出里面重复次数最多的。怎么做？
Hadoop 是一把威力巨大的榔头，在使用过 Hadoop 之后，看着任何东西都想把它给 map reduce 了。有一个关于 Jeff Dean 的小笑话，说在睡不着觉的时候，一般人是数羊，Jeff Dean 是 map reduce 他的羊群。所以，我的办法是，把这个文件拆分成若干个小文件，在 map 过程用 hash 算法保证相同的单词落入一个文件（这点很重要），计算单词出现次数，在 reduce 过程取得重复次数最多的单词来。
但是，真有必要这样啰嗦吗？
只有一亿个单词，简单估算一下，一个字母占据两个字节，假设单词平均长度 5，即便
[……]阅读全文
最近在看一本书，叫做 《思考的乐趣》，第 26 节 “我最爱的证明”，里面介绍了这样一则有趣的问题（文章链接在此）：
设想一个平面上布满间距为 1 的横纵直线，形成由一个个 1×1 正方形组成的网格。任意给一个面积小于 1 个单位的图形，证明这个图形总能放在网格中而不包含任何一个格点。
初看这个论断，觉得似乎是正确的，但又不知从何下手。文中指出证明的思路很巧妙，让人感到数学的美妙。我的感触是，文中的证明大大地换了个角度，很有峰回路转的感觉。正在读这篇文章的你，不妨先思考一下，别急着往下看答案。
如果陷入了拼命去构造各种各样的图形类别，去思考不同类别图形的情况下，怎么去摆放这样的图形，使得图形不覆
[……]阅读全文
这道题是说，100 层楼，两个一模一样的鸡蛋，某层之上扔鸡蛋就会碎。问要测试多少次才能找出这层楼来。我曾经在去年初的这篇文章里面讨论过这个问题的解法，因为只想记录一下思路和讨论过程，写得很简略。现在，我想重新整理一下这个问题，再稍稍扩展和挖掘一下。希望可以用尽可能清晰易懂的描述，把这个问题的前后说清楚。
现在只有两个鸡蛋，而算法必须在各种合法输入下都是可行的，就是说要能找出这一层来，你得假设你的运气最差，这就意味着，我求解的是在每种扔鸡蛋的策略下都有一个需要扔的次数的最大值，而现在需要求解的是这些最大值中的最小值的问题。如果我只有一枚鸡蛋，这就意味着，我只能从第一层开始老老实实地一层一层往上试
[……]阅读全文
古希腊数学家欧几里德就已证明素数有无穷多个，并提出一些素数可写成 “2P-1”（其中指数 P 也是素数）的形式，其中 17 世纪法国数学家、法兰西科学院奠基人马林·梅森（Martin Mersenne）是其中成果较为卓著的一位，因此数学界将 “2P-1” 型的素数称为 “梅森素数”。
1772 年，欧拉在双目失明的情况下，靠心算证明了 231-1（即 2147483647）是第 8 个梅森素数，这个记录一百多年内都没有人打破。下面是欧拉证明素数有无穷多个的过程，但是梅森素数是否有无穷多个还没有人能证明。
假使素数 p1，p2，p3……pn 只有那么多个，现在有新数 p=p1*p2*p3*……pn + 1，可见 p 无法被 p1
[……]阅读全文
这篇文章是对这个帖子的汇总，帖子里的答复都很有意思，真希望 ITEye 多一些这样的帖子，少一些浮躁和毫无意义的争论。
我把帖子汇总贴在下面：
Write a function that takes as input list of words and prints out groups of words with exactly the same letters, one group per line.
For example,
Given the list:
hat, top, potter, pot, pier, ripe
It would print:
hat
top, pot
pot
[……]阅读全文
题目：一只青蛙一次可以跳 1 级台阶，也可以跳 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
这道题还被 ITEye 放在了博文视点杯有奖答题活动里面。
我提供三种解法。
1、递归求解：
青蛙每跳一次前，有这样三种情况：
于是递归方法求解：
/** * 递归方法 */public static int calc(int n) { [……]阅读全文
有道经典的算法题，两个一模一样的鸡蛋，某层之上扔鸡蛋就会碎。假如运气最差的话，问要测试多少次才能找出这层楼来。
如果只有一个鸡蛋，我就只能一层一层试验。两个的话关键就是找着第一个鸡蛋试验的位置，第二个鸡蛋还是只能一层一层试验。
这道问题其实可以扩展到任意个鸡蛋，但现在还是只看 2 个鸡蛋的情况。
2 个鸡蛋只有 n 层的最优解求出来假使为 k，那么，n+1 层的时候，把第一个鸡蛋在第 k 层释放，只有两种情况（n+1 只是分解成两个<=n 的子问题，这两个都是已经有解了的）：
（1）破碎，于是只有之后就只能遍历从地面到第 k-1 层，一层层遍历，不能偷懒，最坏的情况在此要尝试 k 次；
（2）没碎，那问题
[……]阅读全文