箱猫日和

最近重新看哈希表的东西，发现自己大致能看懂了。以下是自己从书中了解的几个重点。 二次探测是一个根据哈希函数散列到同一个位置即碰撞时重新查找的方式，具体来说，假如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,…