下午花了点时间，把排列和组合算法搞出来了。网上一堆资料看了不靠谱，要么是不明所以的变量名，要么直接帖代码。 排列 实现要点：交换和顺序处理。考虑对[1, 2, 3, 4]排列。实际是排列 [1], [2, 3, 4] [2], [1, 3, 4] [3], [2, 1, 4] [4], [2, 3, 1] 排列[1], [2, 3, 4]时，实际是排列 [1, 2], [3, 4] [1, 3], [2, 4] [1, 4], [3, 2] 从上面的分解可以看出，代码中实际要做的是交换当前的数字和右边数字中的某一个，具体来说，第一步是分别交换第一个和第一个，第一个和第二个，第一个和第三个，第一个和第四个。第二步是交换第二个和第二个，第二个和第三个，第二个和第四个。依次类推。递归的停止条件是右边的数组仅有一个元素，比如[1, 2, 3], [4]。具体代码如下，注意参数比较多的permutation方法。 start和end分别是第二个数组的起始位置和结束位置，当两者相等时，右边的数组只有一个元素，这时就可以直接输出排列的数组。 一般情况下，交换当前元素和右边数字中的一个，递归排列，在结束时交换回来（这步是必须的）。

最近重新看哈希表的东西，发现自己大致能看懂了。以下是自己从书中了解的几个重点。 二次探测是一个根据哈希函数散列到同一个位置即碰撞时重新查找的方式，具体来说，假如i是哈希函数得到的位置，如果i有值了，那么尝试查找i + 1×1，i + 2×2，i + 3×3…i + NxN。 其次和二次探测相关的是在哈希表的大小为一个质数，并且使用量在一半以下时出现碰撞或者聚类的机率很小。 下面写一下实现哈希表二次探测个人认为主要的两个点，剩下的就是一些具体实现的细节问题了。 查找下一个质数 在容量超过一半时重新散列。需要找到比当前表大小大一些的质数。个人实现如下（Java）： public static int findNextPrime(int current) { int nextPrime = current; if(nextPrime % 2 == 0) nextPrime++; while(!isPrime(nextPrime)) { nextPrime += 2; } return nextPrime; } private static boolean isPrime(int number) { for (int i = 3; i <= Math.sqrt(number); i +=…

阶乘和斐波那契数列相信各位都很熟悉，典型的教材式递归例子，因为简单退化为循环也没啥难度。不过依赖于递归的问题并不都是那么简单的，比如最少硬币问题，需要称为动态规划（DP）的方式来实现。 所谓动态规划个人理解就是缓存一下递归的结果。比如斐波那契数列，简单的实现方式是： public int fib(int n) { if(n == 0 || n == 1) return 1; return fib(n – 2) + fib(n – 1); } 假如计算fib(5)，事实上计算了一次fib(4)，两次fib(3)，三次fib(2)，四次fib(1)，两次fib(0)，换句话说，重复计算了(1 – 1) + (2 – 1) + (3 – 1) + (4 – 1) + (2 – 1)有7次之多。理想情况下每个fib(n)只要计算一次。改进方法很简单，增加cache，其实就是简单的映射数组： public int fib(int n) { if(fib_cache[n] > 0) return fib_cache[n]; //…

成果在这里，前天完成的，花了大约半天的时间。参考资料主要是维基百科和一篇博客。 在分析自己代码前，先写一点自己对于Dijkstra算法的理解。 u s v

时隔好几年，才发现算法的趣味性，比如堆排序。堆排序同时也是大学时自己未完成的数据结构作业之一，就像《高等数学》一样之后都是抄抄了事…… 个人理解，堆排序是一个有名的排序算法，比较适合优先级队列。虽然时间复杂度是O(nlogn)，论排序算法中比较快的还是快速排序。堆排序的特点是使用完全或近似完全二叉树来模拟一种父节点肯定比子节点大（最大堆）或者小（最小堆）的结果，并通过多次“删除”根节点并恢复结构来达到“模拟”排序的目的。实践中需要关注的是三点:

插入排序 插入排序最直观的解释是不断拿扑克牌时排序的动作。一开始你只有一张8，第二张是5，你把5放在8的左边。第三张是9，你放在8的右边。第四张是2，你放在最左边。拿这四张牌的过程可以认为是排序4个数字的过程。步骤可以归纳为： 拿起一张牌 -> 取下一个数 比较现有牌，具体来说是从右往左找到第一个不小于当前牌的位置 -> 将所有大于当前数的数字向右移动一位 放入牌 -> 放置数字 形象上来讲，放置数字的过程是多个数字右移的过程，所以不需要swap。Java代码如下： public void sort(int[] xs) { int len = xs.length; if (len <= 1) return; for (int i = 1; i < len; i++) { int x = xs[i]; int j = i; while (j > 0 && xs[j – 1] > x) {…

最近重新学习算法，先从几个排序算法开始。快速排序是比较有名的一个排序算法，基本原理我明白，但是之前只会筛选构造新序列分区的方式，现在要学的是原地分区的方式。 成果代码如下，使用Java编写（C/C++的数组和指针操作忘得差不多了）。 private void swap(int[] array, int i, int j) { if (i == j) return; System.out.println(String.format(“%d <-> %d”, i, j)); int a = array[i]; array[i] = array[j]; array[j] = a; } private int partition(int[] ns, int begin, int end) { int pivotIndex = (begin + end) / 2; int pivot = ns[pivotIndex]; swap(ns, pivotIndex,…