algorithm

1. 问题 之前遇到过这么一个问题{:target="_blank"} ，说有一只青蛙，它想跳到 n 层的楼梯上面去，由于自身原因，它每次只能选择跳 1 层或者 2 层。 问，青蛙有多少种跳法？ 第一眼看到这个问题的时候有点蒙，不知道从何下手。不妨先从可见的楼梯层数 n 入手，设求青蛙跳法的方法是 f(n)。 那么当 n=1 时 f(n)=1, n=2 时 f(n)=2, n=3 时 f(n)=3, n=4 时 f(n)=5 … 很明显，f(n) 是一个斐波那锲数列的方法，当前数等于前两个数之和，所以有 f(n)=f(n-1)+f(n-2)。 其实从另一个角度想也可以想明白，假设我是那只青蛙，站在 n 层的楼梯脚下，我有 f(n) 种跳法，现在我能选择的是跳 1 层还是跳 2 层。当我选择跳 1 层时，我接下来的跳法还有 f(n-1) 种；当我选择跳 2 层时，我接下来的跳法还有 f(n-2) 种。所以我在还没有选择之前的跳法应该等于我这两种跳法之和，所以有 f(n)=f(n-1)+f(n-2)。 2. 解答 2.1 递归 上面的思路有了，我们很容易就可以用代码实现了。 public int climbStairs(int n) { if (n <= 0) return 0; if (n == 1) return 1; if (n == 2) return 2; // f(n)=f(n-1)+f(n-2) return climbStairs(n - 1) + climbStairs(n - 2); } 上面的代码虽然可以解决问题，但是会出现很大一部分的重复运算。 如下图所示，当 n=6 时，我们计算了 2 次 f(4), 3 次 f(3)。 2....

一、缓存 缓存（Cache） 一词来源于 1967 年的一篇电子工程期刊论文。其作者将法语词 “cache” 赋予 “safekeeping storage” 的涵义，用于计算机工程领域。 最早是因为 CPU 与内存之间运算和读写速度不一致，在 CPU 添加一块空间用于提前将内存中数据加载进来，提高 整体的速度，这块空间被称为 缓存（Cache）。如今缓存的概念已被扩充，在内存和硬盘之间也有 Cache（磁盘缓存），乃至在硬盘与网络之间也有某种意义上的 Cache ──称为 Internet 临时文件夹或网络内容缓存等。凡是位于速度相差较大的两种硬件之间，用于协调两者数据传输速度差异的结构，均可称之为 Cache。 但是缓存的空间是宝贵的，所以我们不会将所有的数据都缓存起来，必须依赖一定的规则淘汰掉一部分数据。这个规则就是我们讨论的缓存淘汰算法。 二、缓存淘汰 2.1 FIFO（先入先出） FIFO (First In FIrst Out) 是最简单的算法，原理跟名字一样，“如果一个数据最先进入缓存中，则应该最早淘汰掉”。把缓存中的数据看成一个队列，最先加入的数据位于队列的头部，最后加入位于队列的尾部。当缓存空间不足需要执行缓存淘汰操作时，从队列的头部开始淘汰。 如下所示，假设我们的缓存可以缓存 3 对数据，1 加入时处于队列的头部，2 和 3 加入时缓存空间充足。当 4 加入时，执行缓存淘汰，由于 1 处于队列的头部，所以被淘汰。同理 5 加入时，2 被淘汰。 Java 中有单独的队列 Queue ，可以使用 LinkedList。 1 2 3 4 5 3=c 4=e 5=f 2=b 2=b 3=c 4=e 1=a 1=a 1=a 2=b 3=c 2....

快速排序是目前所有排序中性能较好的一种算法，最好情况和平均情况下时间复杂度均为O(nlogn)，最坏的情况下时间复杂度为O(n^2)。快速排序采用递归，用空间换取时间。由于使用了递归，因此需要额外的存储空间。 package sunbufu.sort; import java.util.Arrays; public class MyQuickSort { public static void main(String[] args) { int[] array = { 2, 5, 1, 4, 3, 9, 5, 1, 12 }; System.out.println(Arrays.toString(array)); System.out.println("--------------------------"); quickSort(array, 0, array.length - 1); System.out.println("--------------------------"); System.out.println(Arrays.toString(array)); } private static void quickSort(int[] array, int low, int high) { int l = low; int h = high; int key = array[low];// 默认选择第0个为基数 while (l != h) {// l跟h相等则结束 while (l < h && array[h] >= key)// h从右向左移动,直到找到一个比基数小的值 h--; if (l < h) swap(array, l, h); while (l < h && array[l] <= key)// l从左向右移动,直到找到一个比基数大的值 l++; if (l < h) swap(array, l, h); } // 然后把数组从基数所在的位置分成两部分,分别递归 if (l > low) quickSort(array, low, l - 1); if (h < high) quickSort(array, h + 1, high); } private static void swap(int[] array, int a, int b) { int temp = array[a]; array[a] = array[b]; array[b] = temp; System....

1.定义概述 Floyd-Warshall算法（Floyd-Warshall algorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。 2.实例演示 /** * 弗洛伊德算法求最短路径 * @author sunbufu * */ public class ShortestPathFloyd { /**无穷大*/ final static int INF = Integer.MAX_VALUE; public static void main(String[] args) { int[] points = { 1, 2, 3, 4, 5, 6 }; int[][] weights = { // 1 2 3 4 5 6 {0, 7, 9, INF, INF, 14 },//1 {7, 0, 10, 15, INF, INF },//2 {9, 10, 0, 11, INF, 2 },//3 {INF, 15, 11, 0, 6, INF },//4 {INF, INF, INF, 6, 0, 9 },//5 {14, INF, 2, INF, 9, 0 } //6 }; int[][] previousPoint = { // 1 2 3 4 5 6 {1, 2, 3, 4, 5, 6 },//1 {1, 2, 3, 4, 5, 6 },//2 {1, 2, 3, 4, 5, 6 },//3 {1, 2, 3, 4, 5, 6 },//4 {1, 2, 3, 4, 5, 6 },//5 {1, 2, 3, 4, 5, 6 } //6 }; floyd(points, weights, previousPoint); } private static void floyd(int[] points, int[][] weights, int[][] previousPoint) { int pointsNumber = points....

1.定义概览 Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。 2.实例演示 设结点1为起点，依次求到其它结点的最短路径。 /** * 迪杰斯特拉算法求最短路径 * @author sunbufu * */ public class ShortestPathDijkstra { /**无穷大*/ final static int INF = Integer.MAX_VALUE; public static void main(String[] args) { int[] points = { 1, 2, 3, 4, 5, 6 }; int[][] weights = { // 1 2 3 4 5 6 {0, 7, 9, INF, INF, 14 },//1 {7, 0, 10, 15, INF, INF },//2 {9, 10, 0, 11, INF, 2 },//3 {INF, 15, 11, 0, 6, INF },//4 {INF, INF, INF, 6, 0, 9 },//5 {14, INF, 2, INF, 9, 0 } //6 }; dijkstra(points, weights); } public static void dijkstra(int[] points, int[][] weights) { int pointsNumber = points....