数据结构与算法

该文章主要是学习数据结构（链表、栈、哈希表、树、图）和算法（排序算法、程序员常用10大算法），针对每个结构都有一个小case测试验证。

数据结构

链表

一种数据结构，包括单向链表、双向链表、单向环形链表

单向链表

/**
 * @desc 单链表demo
 *  1.链表添加
 *      1.1 普通添加
 *      1.2 顺序添加
 *  2.遍历
 *  3.删除
 *  4.修改
 *  5.查找倒数第k个元素
 *  6.链表反转
 *      6.1 数组方式反转
 *      6.2 栈的方式反转
 * @Author xw
 * @Date 2019/8/30
 */
public class SingleLinkedListDemo {
    public static void main(String[] args) throws CloneNotSupportedException {
        HeroNode hero1 = new HeroNode(1,"宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2,"卢俊义", "玉麒麟");
        HeroNode hero3 = new HeroNode(3,"吴用", "智多星");
        HeroNode hero4 = new HeroNode(4,"林冲", "豹子头");
        // 添加操作
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        /*// 1.1 正常添加
        singleLinkedList.add(hero1);
        singleLinkedList.add(hero2);
        singleLinkedList.add(hero3);
        singleLinkedList.add(hero4);*/
        // 1.2 顺序添加
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero3);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero4);
        // 2.遍历
        singleLinkedList.list();
        System.out.println("------------------------------------------");
        // 3.修改
        HeroNode editHero = new HeroNode(1,"宋江", "及时雨2");
        singleLinkedList.update(editHero);
        System.out.println("修改后-----------------------");
        singleLinkedList.list();
        // 4.删除
        System.out.println("删除后-----------------------");
        int no = 3;
        singleLinkedList.del(no);
        singleLinkedList.list();
        // 5.查找倒数第k个元素
        HeroNode head = singleLinkedList.getHead();
        int index = 4; // 倒数第1个
        HeroNode lastIndexNode = singleLinkedList.findLastIndexNode(head, index);
        System.out.println("倒数第"+index+"个元素是：\n"+lastIndexNode);
        // 6.链表反转
        System.out.println("反转后--------------");
//        singleLinkedList.reverseByArray(head);
        singleLinkedList.reverseByStack(head);
        singleLinkedList.list();
    }
}

双向链表

/**
 * @desc 双向链表
 * @Author xw
 * @Date 2019/9/2
 */
public class DoubleLinkedListDemo {
    public static void main(String[] args) {
        HeroNode hero1 = new HeroNode(1,"宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2,"卢俊义", "玉麒麟");
        HeroNode hero3 = new HeroNode(3,"吴用", "智多星");
        HeroNode hero4 = new HeroNode(4,"林冲", "豹子头");
        // 添加操作
        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
        // 1.1 正常添加
        doubleLinkedList.add(hero1);
        doubleLinkedList.add(hero2);
        doubleLinkedList.add(hero3);
        doubleLinkedList.add(hero4);
        doubleLinkedList.list();
        // 3.修改
        HeroNode editHero = new HeroNode(1,"宋江", "及时雨2");
        doubleLinkedList.update(editHero);
        System.out.println("修改后-----------------------");
        doubleLinkedList.list();
        // 4.删除
        System.out.println("删除后-----------------------");
        int no = 3;
        doubleLinkedList.del(no);
        doubleLinkedList.list();
    }
}

单向环形链表（约瑟夫问题）

/**
 * @desc 单向环形列表
 * 1.约瑟夫问题：
 *  设编号为1，2，...n的n个人围坐一圈，约定编号为k(1<=k<=n)的人
 *  从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，
 *  依次类推，直到所有人出列为止，由此产生一个环形队列
 * 2.假设问题：
 *  n = 5 有5个人
 *  k = 1 从第一个人开始
 *  m = 2 每次数2下
 * 3.思路分析：
 * （1）定义一个辅助变量helper，指向最后一个节点
 * （2）当小孩报数时，first、helper同时移动 m-1 次（每次是从自己开始数）
 * （3）这时，可以将first指向的小孩节点出圈
 *      first = first.next
 *      helper.next = first
 *      原来的first节点没有任何引用，就会被回收
 * @Author xw
 * @Date 2019/9/2
 */
public class CircleSingleLinkedListDemo {
    public static void main(String[] args) {
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        circleSingleLinkedList.addBoy(5);
        circleSingleLinkedList.showBoy();
        circleSingleLinkedList.countBoy(1, 2, 5);
    }
}

栈

数组模拟栈

/**
 * @desc 数据模拟栈
 * 1.使用数组模拟栈 arr = new Array[maxSize]
 * 2.定义一个top表示顶
 * 3.入栈 arr[++top] = data
 * 4.出栈 return arr[--top]
 * @Author xw
 * @Date 2019/9/2
 */
public class ArrayStackDemo {
    public static void main(String[] args) {
        ArrayStack arrayStack = new ArrayStack(3);
        arrayStack.push(1);
        arrayStack.push(2);
        arrayStack.push(3);
        System.out.println(arrayStack.pop());
        System.out.println(arrayStack.pop());
        System.out.println(arrayStack.pop());
    }
}

实现统合计数器

/**
 * @desc 波兰计算器
 *  suffixExpression=(30+4)*5-6 => 30 4 + 5 * 6 - => 164
 * 1.将suffixExpression放入ArrayList中 [30, 4, +, 5, *, 6, -]
 * 2.将ArrayList传递给一个方法，遍历ArrayList配合栈完成计算
 *
 * 中缀转后缀表达式
 * 1.初始化两个栈：运算符栈s1和存储结果栈s2
 * 2.从左至右扫描中缀表达式
 * 3.遇到数字时，将其压入s2
 * 4.遇到运算符时，比较其与s1栈顶运算符的优先级；
 * （1）如果s1为空，或栈顶运算符为左括号“（”，则直接将些运算符入栈s1；
 * （2）否则，若优先级比栈顶优先级高，也将运算符压入s1
 * （3）否则，将s1栈顶的运算符弹出并压入s2中，再次转到（4.1）与s1中新的栈顶运算符相比较
 * 5.遇到括号时：
 * （1）如果是“（”，则直接压入s1
 * （2）如果是“）”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到“（”为止，此时将这一对括号丢弃
 * 6.重复步骤2-5，一直到表达式的最右边
 * 7.将s1中剩余的运算符依次弹出并压入s2
 * 8.依次弹出s2中的元素并输出，结果的逆序即为表达式对应的后缀表达式
 *
 * @Author xw
 * @Date 2019/9/3
 */
public class PolandNotation {
    public static void main(String[] args) {
        // 中缀转后缀表达式
        /*String expression = "(30+4)*5-6"; // 30 4 + 5 * 6 - => 164
        expression = "4*5-8+60+8/2"; // 4 5 * 8 - 60 + 8 2 / + => 76
        List<String> list = infixToSuffixExpression(expression);
        System.out.println("后缀表达式：" + list);
        int res = calculate(list);
        System.out.println("res=" + res);*/
        // 长+2x（宽+高）>100cm => (%s+%s*(%s+%s))>%s
        int length = 100;
        int width = 10;
        int height = 10;
        String expression = String.format("(%s+2*(%s+%s))>%s", length, width, height, 100);
        System.out.println(String.format("%s=>%s", expression, calculate2(infixToSuffixExpression(expression)).intValue()));
        // 长>100CM 或者 宽>100cm
        length = 120;
        width = 77;
        expression = String.format("%s>%s|%s>%s", length, 100, width, 100);
        System.out.println(String.format("%s=>%s",expression, calculate2(infixToSuffixExpression(expression)).intValue()));
        // 重量>100kg
        double weight = 100.75;
        expression = String.format("%s>%s", weight, 100.75);
        System.out.println(String.format("%s=>%s", expression, calculate2(infixToSuffixExpression(expression)).intValue()));
        /*System.out.println(1|0|0|0); // 1
        System.out.println(1|0); // 1
        System.out.println(0|0); // 0
        System.out.println(1&1&0); // 1
        System.out.println(1&0); // 0
        System.out.println(0&0); // 0*/
    }

递归

打印、阶乘问题

/**
 * @desc 打印问题
 * （1）打印
 * （2）阶乘
 * @Author xw
 * @Date 2019/9/3
 */
public class RecursionPrintDemo {
    public static void main(String[] args) {
        // 打印问题
        test1(4); // 2 3 4
        System.out.println("-----------");
        test2(4); // 2
        // 阶乘 4x3x2x1
        System.out.println(factorial(4));
    }
    // 阶乘
    public static int factorial(int n) {
        if (n == 1) {
            return 1;
        } else {
            return n * factorial(n - 1);
        }
    }
    // 输出什么？
    public static void test1(int n) {
        if (n > 2) {
            test1(n -1);
        }
        System.out.println("n=" + n);
    }
    // 输出什么？
    public static void test2(int n) {
        if (n > 2) {
            test2(n -1);
        } else {
            System.out.println("n=" + n);
        }
    }
}

迷宫

/**
 * @desc 迷宫问题
 * 1.初始化一个8行7列的矩阵 map[8][7]
 * 2.假设：
 * （1）三种类型：0-还没有走,1-档板,2-可以走（已走）,3-走不通
 * （2）策略：下-》右-》下-》左
 * （3）初始值：周围都是1
 * 3.过程分析：
 * （1）已经找到（确定找到的条件：第7行6列即为找到 =》 [6,5]=2）
 * （2）还没有找到按策略去找
 *
 * @Author xw
 * @Date 2019/9/3
 */
public class MingGong {
    public static void main(String[] args) {
        // 1.初始化一个8行7列的矩阵arr[8][7]
        int[][] map = new int[8][7];
        // 2.初始值：周围都是1
        // 第1行和第8行设置档板
        for (int j = 0; j < 7; j++) {
            map[0][j] = 1;
            map[7][j] = 1;
        }
        // 第1列和第7列设置档板
        for (int i = 0; i < 8; i++) {
            map[i][0] = 1;
            map[i][6] = 1;
        }
        // 输出矩阵
        print(map);
        System.out.println("-------------------------");
        // 设置档板 [3,1]=1,[3,2]=1
        map[3][1] = 1;
        map[3][2] = 1;
        print(map);
        // 策略：下-》右-》上-》左
        setWay(map, 1, 1); // 从[1,1]这个位置开始
        System.out.println("策略:下-》右-》上-》左 =>");
        print(map);
    }
}

八皇后

/**
 * @desc 8皇后问题
 * 1.是什么？
 *  8x8的矩阵，任意两个位置不能处于同一行、同一列或同一斜线，能找出多少种解法，这就是8皇后问题
 * 2.思路分析
 * （1）第一个皇后放第一行第一列[0,0]
 * （2）第二个皇后放第二行第一列[1,0]...直到判断ok，
 *      如果不ok，继续放在第二列、第三列、依次把所有列放完，找到一个合适位置
 * （3）继续第三个皇后，还是第一列、第二列...直到第8个皇后也放在一个不冲突的位置，
 *      算是找到一个正确解
 * （4）当得到一个正确解时，在栈回退到上一个栈时，就会开始回溯，即将第一个皇后，放在第一列的所有正确解，全部得到
 * （5）然后回头继续第一个皇后放第二列，后面继续循环执行1-4步骤
 * 3.说明
 *  理论上创建一个二维数组来表示一个棋盘，但实际上可以通过算法，
 *  用一个一维数组即可解决 arr[8] = {0, 4, 7, 5, 2, 6, 1, 3}
 *  // arr[0] = 0 表示第1个皇后（第一行）放在第1列，即[0,0]
 *  // arr[1] = 4 表示第2个皇后（第二行）放在第5列，即[1,4]
  * 下标表示第几行 即第几个皇后
 *  arr[i] = val，val表示第i+1个皇后放在第i+1行的第val+1列
 * @Author xw
 * @Date 2019/9/4
 */
public class Queen8 {
    private int max;
    private int[] arr;
    private int count;
    public Queen8(int max) {
        this.max = max;
        this.arr = new int[max];
    }
    public static void main(String[] args) {
        for (int i = 0; i < 8; i++) {
            System.out.print(String.format("R%s\t", i+1));
        }
        System.out.println();
        Queen8 queen8 = new Queen8(8);
        queen8.check(0);
        System.out.println(String.format("共有%s种解法", queen8.count));
    }
}

排序算法

冒泡排序

/**
 * @desc 冒泡排序
 *  案例：arr[] = {3, 9, -1, 10, 20}
 * 思路分析：
 * 1.两层for循环遍历待排序的数组，i的index=[0,arr.length-1],j的index=[0,arr.length-1-i]
 *  （1）length-1：每一轮循环是两个数比较，所以-1
 *  （2）length-1-i：-1跟同上；每一轮结束会有一个最小值到数组最末端，所以每次-i
 * 2.如果 arr[j] > arr[j+1] 交换两个值的位置（arr[j] = arr[j+1]），需要用temp临时变量保存arr[j]的值
 * @Author xw
 * @Date 2019/9/4
 */
public class BubbleSort {
    public static void main(String[] args) {
        int arr[] = {3, 9, -1, 10, 20};
        int temp;
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j+1]) {
                    // 直接交换是不行的，值会覆盖
                    /*arr[j] = arr[j+1];
                    arr[j+1] = arr[j];*/
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
            System.out.println("第"+(i+1)+"轮过后，arr=" + Arrays.toString(arr));
        }
    }
}

选择排序

/**
 * @desc 选择排序
 * arr[] = {101, 34, 119, 1}
 * （1）第一次从arr[0]~arr[n]中选取最小值，与arr[0]交换
 * （2）第二次从arr[1]~arr[n]中选取最小值，与arr[1]交换
 *  ...
 * （3）第i次从arr[i-1]~arr[n-1]中选取最小值，与arr[i-1]交换
 * （4）第n-1次从arr[n-2]~arr[n-1]中选取最小值，与arr[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列
 *
 * @Author xw
 * @Date 2019/9/4
 */
public class SelectSort {
    public static void main(String[] args) {
        int arr[] = {101, 34, 119, 1};
        for (int i = 0; i < arr.length - 1; i++) { // arr.length - 1 只要n-1次就能排好顺序
            int minIndex = i;
            int min = arr[i];
            for (int j = i+1; j < arr.length; j++) { // i+1，每结束一轮，最小下标往后移
                if (min > arr[j]) { // 不是最小值
                    min = arr[j];
                    minIndex = j;
                }
            }
            // 找到最小值，与arr[0]交换，并放在第一个位置，即arr[0]
            if (minIndex != i) { // 最小下标发生改变，才调整位置
                arr[minIndex] = arr[i]; // [101, 34, 119, 1] => [34, 101, 119, 1]
                arr[i] = min;
            }
            System.out.println("第"+(i+1)+"轮过后，arr=" + Arrays.toString(arr));
        }
    }
}

插入排序

/**
 * @desc 插入排序
 * 思路分析：
 *  （1）把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表只包含一个元素，无序表中含有n-1个元素
 *  （2）排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序的排序码进行比较，将它插入到有序表中的适当位置，
 *      使之成为新的有序节点
 * 实例：
 *  {101, 34, 119, 1}
 * @Author xw
 * @Date 2019/9/4
 */
public class InsertSort {
    public static void main(String[] args) {
        int arr[] = {34, 101, 119, 1};
        /*int[] arr = new int[160000];
        for (int i = 0; i < 160000; i++) {
            arr[i] = new Random().nextInt(8000000);
        }*/
        System.out.println(LocalDateTime.now());
        insert_sort2(arr);
        System.out.println(LocalDateTime.now());
    }
}

希尔排序（plus版插入排序）

/**
 * @desc 希尔排序
 *  它是一种更高效的插入排序，也称为缩小增量排序。
 *  产生原因：
 *      由于插入排序存在问题，当需要插入数最小时，后移的次数明显增多，对效率有影响
 *  基本思想：
 *      把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
 *      随着增量减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止
 *
 *  案例：
 *      {8, 9, 1, 7, 2, 3, 5, 4, 6, 0}
 * @Author xw
 * @Date 2019/9/5
 */
public class ShellSort {
    public static void main(String[] args) {
        /*int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        shellSort2(arr);
        System.out.println("第1轮过后，arr=" + Arrays.toString(arr));*/
        int[] arr = new int[8000000];
        for (int i = 0; i < 8000000; i++) {
            arr[i] = new Random().nextInt(8000000);
        }
        System.out.println(LocalDateTime.now());
        shellSort2(arr);
        System.out.println(LocalDateTime.now());
        //System.out.println("arr=" + Arrays.toString(arr));
    }
}

快速排序（plus版冒泡排序）

/**
 * @desc 快速排序
 * 思想：
 * （1）将一个数组分割成左右两部分
 * （2）分操作
 *      A.左边进行递归冒泡排序，直到有序
 *      B.右边进行递归冒泡排序，直到有序
 * （3）合操作（左边 + 右边）
 * （4）依次执行1-3步骤，直到有序
 *
 * 案例：
 *  {-9,78,0,23,-567,70}
 * @Author xw
 * @Date 2019/9/6
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {-9, 78, 0, 23, -567, 70};
        /*int[] arr = new int[8000000];
        for (int i = 0; i < 8000000; i++) {
            arr[i] = new Random().nextInt(8000000);
        }*/
        System.out.println(LocalDateTime.now());
        quickSort(arr, 0, arr.length - 1);
        System.out.println(LocalDateTime.now());
        //System.out.println("arr=" + Arrays.toString(arr));
    }
}

归并排序

/**
 * @desc 归并排序
 *  利用分治策略，分而治之，即先分再合
 * （1）分
 *      A.找到中间下标mid
 *      B.向左递归
 *      C.向右递归
 * （2）治
 *      A.将左右两边（有序）的数据按照规则填充到temp数组，直到左右两边的有序序列有一边处理完毕为止
 *      B.把剩余数据的一边的数据依次全部填充到temp
 *      C.将temp数组的元素拷贝到arr（注意，并不是每次都拷贝所有！！！）
 *
 * 案例：
 *      {8, 4, 5, 7, 1, 3, 6, 2}
 * @Author xw
 * @Date 2019/9/6
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {8, 4, 5, 7, 1, 3, 6, 2};
        /*int[] arr = new int[8000000];
        for (int i = 0; i < 8000000; i++) {
            arr[i] = new Random().nextInt(8000000);
        }*/
        int[] temp = new int[arr.length]; // 归并排序需要额外的一个数组
        System.out.println(LocalDateTime.now());
        mergeSort(arr, 0, arr.length - 1, temp);
        System.out.println(LocalDateTime.now());
        System.out.println("arr=" + Arrays.toString(arr));
        /*int[] arr = new int[8000000];
        for (int i = 0; i < 8000000; i++) {
            arr[i] = new Random().nextInt(8000000);
        }
        System.out.println(LocalDateTime.now());
        int[] temp = new int[arr.length]; // 归并排序需要额外的一个数组
        mergeSort(arr, 0, arr.length - 1, temp);
        System.out.println(LocalDateTime.now());*/
    }
}

基数排序（桶排序）

/**
 * @desc 基数排序
 * 特别说明：
 *      该demo不支持负数排序，如想实现负数排序，请参考https://code.i-harness.com/zh-CN/q/e98fa9
 * 排序思想：
 * （1）将所有比较数值统一为同样的数位长度，数位较短的数前面补0。
 * （2）然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序
 *      完成后，数列就变成一个有序序列了。
 *
 * 案例：
 *  {53, 3, 542, 748, 14, 214}
 * @Author xw
 * @Date 2019/9/6
 */
public class RadixSort {
    public static void main(String[] args) {
        int[] arr = {53, 3, 542, 748, 14, 214};
        /*int[] arr = new int[8000000];
        for (int i = 0; i < 8000000; i++) {
            arr[i] = new Random().nextInt(8000000);
        }*/
        System.out.println(LocalDateTime.now());
        radixSort(arr);
        System.out.println(LocalDateTime.now());
        System.out.println("arr=" + Arrays.toString(arr));
    }
}

小结

（1）速度方面：桶排序、快速排序、希尔排序、插入排序、选择排序、冒泡排序
（2）归并排序需要一个arr[length]的额外数组
（3）基数排序需要一个arr[10][length]的二维数组

查找算法

二分查找

/**
 * @desc 二分查找
 * 案例：
 *  {1, 8, 10, 89, 1000, 1234}
 * 一、思路分析（返回第一个）：
 *  1.首先确定该数组的中间下标
 *      mid = (left + right) / 2
 *  2.然后让需要查找的数findVal与arr[mid]比较
 *  2.1 findVal > arr[mid]，说明要查找的数在右边，需要向右递归
 *  2.2 findVal < arr[mid]，说明要查找的数在左边，需要向左递归
 *  2.3 findVal == arr[mid]，说明已经找到了，返回
 *
 *  问题：结束递归的条件是什么?
 *  1) 找到就结束递归
 *  2) 递归完整个数组，仍然没找到findVal，也需要结束递归，当left>right就需要退出
 *
 * 二、思路分析（返回所有符合条件的下标）：
 *  1.在找到mid索引值时，不要立马返回
 *  2.向mid索引值的左边扫描，将所有满足条件元素的下标，加入到集合
 *  3.向mid索引值的右边扫描，将所有满足条件元素的下标，加入到集合
 * @Author xw
 * @Date 2019/9/11
 */
public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {1, 8, 10, 89, 1000, 1234};
        // （1）使用二分查找，返回第一个符合条件的下标
        int findVal = 89;
        int index = binarySearch(arr, 0, arr.length, findVal);
        if (index == -1) {
            System.out.println("没有找到");
        } else {
            System.out.println("找到了，下标为：" + index);
        }
        // （2）使用二分查找，返回所有符合条件的下标数组
        int[] arr2 = {1000, 8, 1000, 89, 1000, 1000, 1000, 1234};
        findVal = 1000;
        List<Integer> resIndexList = binarySearch2(arr2, 0, arr2.length, findVal);
        System.out.println("arr2=" + resIndexList);
    }
}

插值查找

/**
 * @desc 插值查找算法
 *  由于二分查找针对大数据量首、末两端的查找位移次数太多，影响性能，所以出现了动态中间下标，即插值查找算法。
 * 思路分析：
 *  int mid = left + (right - left)*(findVal - arr[left])/(arr[right] - arr[left])
 *  如：arr = {1,2,3...100}
 *  （1）查找1
 *      mid = 0 + (99 - 0)*(1 - 1)/(100 - 1) => 0 + 99 * 0/99 = 0
 *  （2）查找100
 *      mid = 0 + (99 - 0)*(100 - 1)/(100 - 1) => 0 + 99 * 99/99 = 99
 *
 *  案例：
 *      {1,2,3...100}
 * @Author xw
 * @Date 2019/9/11
 */
public class InsertValueSearch {
    public static void main(String[] args) {
        Integer[] arr = Stream.iterate(1, x -> x+1).limit(100).collect(Collectors.toList()).toArray(new Integer[100]);
        int index = insertValueSearch(arr, 0, arr.length - 1, 100); // arr.length - 1
        System.out.println(index);
    }
}

斐波那契算法（黄金分割算法）

/**
 * @desc 斐波那契查找算法
 * 思路分析：
 * 1.原理与二分查找、插值查找类似，也是通过改变mid值（该值在黄金分割点附近）位置，算法：mid = low + f[k-1] - 1
 *  f代码斐波那契数列
 *  （1）斐波那契数列特点：f[k] = f[k-1] + f[k-2] => (f[k] - 1) = (f[k-1]-1) + (f[k-2]-1) + 1
 *      假设顺序表长度为：length = (f[k] - 1) ，刚好可以分成 f[k-1]-1和f[k-2]-1两部分
 *      即中间位置 mid = low + (f[k-1] - 1)
 *
 * 案例：
 *  {1, 1, 2, 3, 5, 8, 13, 21, 34, 55}
 * @Author xw
 * @Date 2019/9/11
 */
public class FibSearch {
    static int maxSize = 12;
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 18, 56, 87, 100};
        int index = fibSearch(arr, 100);
        if (index == -1) {
            System.out.println("没有找到");
        } else {
            System.out.println("找到了，下标为：" + index);
        }
    }
}

哈希表

简单的员工添加、查询

/**
 * @desc 哈希表案例
 *  有一个公司，当有新员式来报道时，要求该员工的信息加入
 *  （id，性别，年龄，名字、住址），当输入该员工的id时，要求查询该员工的所有信息
 *  要求：
 *  不使用数据库，速度越快越好=> 哈希表（散列）
 *  添加时，保证按照id从低至高的顺序插入？
 *  （1）使用链表来实现哈希表，该链表不带表头，即：链表的第一个结点放存放雇员
 *  （2）思路分析并画出示意图
 *  （3）代码实现【增删改查（显示所有员工，按id查询）】
 * @Author xw
 * @Date 2019/9/12
 */
public class HashTabDemo {
    public static void main(String[] args) {
        HashTab hashTab = new HashTab();
        String key;
        Scanner scanner = new Scanner(System.in);
        while (true) {
            System.out.println("add: 添加雇员");
            System.out.println("list: 显示雇员");
            System.out.println("find: 查找");
            System.out.println("exit: 退出系统");
            key = scanner.next();
            switch (key) {
                case "add":
                    System.out.println("请输入id");
                    int id = scanner.nextInt();
                    System.out.println("请输入名字");
                    String name = scanner.next();
                    Emp emp = new Emp(id, name);
                    hashTab.add(emp);
                    break;
                case "list":
                    hashTab.list();
                    break;
                case "find":
                    System.out.println("请输入id");
                    id = scanner.nextInt();
                    hashTab.findEmpById(id);
                    break;
                case "exit":
                    scanner.close();
                    System.exit(0);
                    break;
                default:
                    break;
            }
        }
    }
}

树

树结构基础部分

二叉树

/**
 * @desc 二叉树遍历
 *  案例：1-宋江、2-吴用、3-卢俊义、4-林冲
 * @Author xw
 * @Date 2019/9/12
 */
public class BinaryTreeDemo {
    public static void main(String[] args) {
        // 1.前、中、后序遍历
        test_simple_order();
        // 2.查找指定节点（前、中、后序查找）
        //test_sample_order_search();
        // 3.删除节点（后序遍历为例）
        //test_del_node();
    }
}

顺序二叉树

/**
 * @desc 顺序二叉树（只考虑完全二叉树）
 * 思路分析：
 *  n: 表示二叉树中的第几个元素（按0开始编号）
 *  （1）第n个元素的左子节点为2*n + 1
 *  （2）第n个元素的右子节点为2*n + 2、
 *  （3）第n个元素的父节点为arr[(n-1)/2]
 * 案例：
 *  给个数组：{1, 2, 3, 4, 5, 6, 7}，要求以前序遍历的方式遍历，结果为：1,2,4,5,3,6,7
 * @Author xw
 * @Date 2019/9/12
 */
public class ArrayBinaryTreeDemo {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7};
        ArrayBinaryTree arrayBinaryTree = new ArrayBinaryTree(arr);
        arrayBinaryTree.preOrder(); // 前序：1,2,4,5,3,6,7
        System.out.println();
        arrayBinaryTree.infixOrder(); // 中序：4,2,5,1,6,3,7
        System.out.println();
        arrayBinaryTree.postOrder(); // 后序：4,5,2,6,7,3,1
    }
}

线索化二叉树

/**
 * @desc 线索化二叉树
 *  案例：
 *      {1, 3, 6, 8, 10, 14}
 *  中序遍历方式：
 *      {8, 3, 10, 1, 14, 6}
 * @Author xw
 * @Date 2019/9/16
 */
public class ThreadedBinaryTreeDemo {
    public static void main(String[] args) {
        HeroNode root = new HeroNode(1, "宋江");
        HeroNode node2 = new HeroNode(3, "吴用");
        HeroNode node3 = new HeroNode(6, "卢俊义");
        HeroNode node4 = new HeroNode(8, "林冲");
        HeroNode node5 = new HeroNode(10, "关胜");
        HeroNode node6 = new HeroNode(14, "张包");
        root.setLeft(node2);
        root.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setLeft(node6);
        ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
        threadedBinaryTree.setRoot(root);
        threadedBinaryTree.threadedNodes();
        // 测试：以10号结点测试
        HeroNode leftNode = node5.getLeft();
        HeroNode rightNode = node5.getRight();
        System.out.println("10号结点的前驱节点：" + leftNode); // 3
        System.out.println("10号结点的后继节点：" + rightNode); // 1
    }
}

实际应用

堆排序

/**
 * @desc 堆排序
 * 排序思想：
 *  1.将待排序序列构造成一个大顶堆
 *  2.此时，整个队列最大的就是堆顶
 *  3.将其与末尾元素进行交换，此时末尾就为最大值
 *  4.然后将剩余n-1个元素重新构成一个堆，这样会得到n个元素的次小值，
 *      如此反复执行，便能得到一个有序序列
 *  可以看到在构建大顶堆的过程中，元素的个数逐渐减少，最后得到一个有序序列
 *
 *  案例：
 *    {4, 6, 8, 5, 9}
 * @Author xw
 * @Date 2019/9/16
 */
public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {4, 6, 8, 5, 9};
        /*int[] arr = new int[8000000];
        for (int i = 0; i < 8000000; i++) {
            arr[i] = new Random().nextInt(8000000);
        }*/
        System.out.println(LocalDateTime.now());
        heapSort(arr);
        System.out.println(LocalDateTime.now());
        //System.out.println("arr=" + Arrays.toString(arr));
    }
}

赫夫曼编码（数据压缩）

/**
 * @desc 数据压缩
 * 原理分析：
 * （1）生成赫夫曼树
 *      i like like like java do you like a java
 * （2）生成赫夫曼树对应的编码
 *      =01,a=100 d=11000 u=11101 e=1110 v=11011 i=101 y=11010 j=0010 k=1111 l=000 o=0011
 * （3）使用赫夫曼编码来生成赫夫曼编码数据，即按照上面的赫夫曼编码，将"i like like ..."
 *      字符串生成对应的编码数据，形式如下：
 *
 * @Author xw
 * @Date 2019/9/16
 */
public class HuffmanZip {
    static Map<Byte, String> huffmanCodes = new HashMap<>(); // 赫夫曼编码集合
    static StringBuilder stringBuilder = new StringBuilder();
    public static void main(String[] args) {
        // （1）生成赫夫曼树
        String content = "i like like like java do you like a java";
        // （3）使用赫夫曼编码来生成赫夫曼编码数据，即按照上面的赫夫曼编码，将"i like like ..."
        //      字符串生成对应的编码数据，形式如下：
        byte[] huffmanCodesBytes = huffmanZip(content.getBytes());
        System.out.println("压缩后的结果：" + new String(huffmanCodesBytes) + " 长度=" + huffmanCodesBytes.length);
        // 解码
        byte[] sourceBytes = decode(huffmanCodes, huffmanCodesBytes);
        System.out.println("原字符串：" + new String(sourceBytes));
        String srcFile = "D:\\2019\\doc\\img\\huffman.png";
        String dstFile = "D:\\2019\\doc\\img\\huffman.zip";
        zipFile(srcFile, dstFile);
        System.out.println("ok");
    }
}

二叉排序树

/**
 * @desc 二叉排序树
 * 思路分析：
 *  1.排序树添加：
 *      （1）if（待插入节点值 > 当前节点值） -> 往右子树递归找（当右子树为空，找到了）
 *      （2）if（待插入节点值 < 当前节点值） -> 往左子树递归找（当左子树为空，找到了）
 *  2.排序树删除：（三种情况）
 *  情况一：删除叶子节点（比如：2,5,9,12）
 *      （1）先找到要删除的节点targetNode
 *      （2）找到targetNode的父节点
 *      （3）确定targetNode是parent的左子节点还是右子节点
 *      （4）根据前面的情况来删除：
 *              左子结点 -> parent.left = null
 *              右子结点 -> parent.right = null
 *  情况二：删除只有一颗子树的节点（比如：1）
 *      （1）先找到要删除的节点targetNode
 *      （2）找到targetNode的父节点
 *      （3）确定targetNode的子节点是左节点还右节点
 *      （4）确定targetNode是parent的左子节点还是右子节点
 *      （5）如果targetNode有左子节点
 *          5.1 如果targetNode是parent的左子节点 -> parent.left = targetNode.left
 *          5.2 如果targetNode是parent的右子节点 -> parent.right = targetNode.left
 *      （6）如果targetNode有右子节点
 *          6.1 如果targetNode是parent的左子节点 -> parent.left = targetNode.right
 *          6.2 如果targetNode是parent的右子节点 -> parent.right = targetNode.right
 *  情况三：删除有两颗子树的节点（比如：7, 3, 10）
 *      （1）先找到要删除的节点targetNode
 *      （2）找到targetNode的父节点
 *      （3）从targetNode的右子树找到最小的结点
 *      （4）用一个临时变量，将最小结点值保存temp=12
 *      （5）删除该最小节点
 *      （6）targetNode=temp
 *
 * 案例：
 * {7,3,10,12,5,1,9}
 * @Author xw
 * @Date 2019/9/16
 */
public class BinarySortTreeDemo {
    public static void main(String[] args) {
        Integer[] arr = {7, 3, 10, 12, 5, 1, 9, 2};
        BinarySortTree binarySortTree = new BinarySortTree();
        for (int i = 0; i < arr.length; i++) {
            binarySortTree.add(new Node(arr[i]));
        }
        System.out.println("----中序遍历----");
        binarySortTree.infixOrder();
        // 节点删除
        int value = 1; // 2,5,9,12 | 7, 3, 10
        binarySortTree.delNode(value);
        System.out.println("----中序遍历----");
        binarySortTree.infixOrder();
    }
}

平衡树（AVL树）

/**
 * @desc 平衡二叉树（AVL树）
 *  由于二叉排序树可能会出现问题，如{1,2,3,4,5,6}，就变成单链表了，引出解决方案：平衡二叉树
 * （1）左旋转
 *      条件：当右子树高度-左子树高度>1
 *      步骤：
 *          1）将A节点的右节点的左节点，指向A节点
 *          2）将A节点的右节点，指向A节点的右节点的左节点
 *      思路分析：
 *          1）创建一个新节点newNode，并设置值为当前节点的值：newNode.value = value
 *          2）把新节点的左子树设置为当前节点的左子树：newNode.left = left
 *          3）把当前节点的值替换为右子节点的值
 *          4）把当前节点的右子树设置成右子树的右子树
 *          5）把当前节点的左子树设置成新的节点
 *      案例：
 *          {4,3,6,5,7,8}
 * （2）右旋转（与左旋转原理一样）
 * （3）双旋转
 *      思路分析：
 *          1）当符合右旋转的条件时，
 *          1.1）如果它的左子树的右子树高度大于它的左子树的高度
 *          1.2）先对当前这个节点的左节点进行左旋转
 *          1.3）再对当前结点进行右旋转的操作即可
 *          2）当符合左旋转的条件时（与符合右旋转的条件同理）
 * @Author xw
 * @Date 2019/9/17
 */
public class AVLTreeDemo {
    public static void main(String[] args) {
        // 左旋转
//        int[] arr = {4, 3, 6, 5, 7, 8};
        // 右旋转
//        int[] arr = {10, 12, 8, 9, 7, 6};
        // 双旋转
        int[] arr = {10, 11, 7, 6, 8, 9};
//        int[] arr = {2, 1, 6, 5, 7, 3};
        AVLTree avlTree = new AVLTree();
        Arrays.stream(arr).forEach(m -> avlTree.add(new Node(m)));
        System.out.println("---中序遍历---");
        avlTree.infixOrder();
        System.out.println("---平衡处理---");
        System.out.println("树的高度：" + avlTree.getRoot().height());
        System.out.println("左子树的高度：" + avlTree.getRoot().leftHeight());
        System.out.println("右子树的高度：" + avlTree.getRoot().rightHeight());
    }
}

多路查找树

描述：包括二叉树与B树、2-3树、B树、B+树和B*树
代码：暂无

图

创建图

/**
 * @desc 图
 * 基本概念：顶点、边、路径、无向图、有向图、带权图
 * 案例：(实现如下的效果)
 *      A   B   C   D   E
 *  A   0   1   1   0   0
 *  B   1   0   1   1   1
 *  C   1   1   0   0   0
 *  D   0   1   0   0   0
 *  E   0   1   0   0   0
 *
 *  （1）用图的方式实现上述效果图
 *      思路分析：
 *          1）5个顶点：A\B\C\D\E
 *          2）1-表示连通，0-表示不连通
 *  （2）用深度优先方式遍历
 *      思路分析：
 *          1）访问初始结点，并标记结点v为已访问
 *          2）查找结点v的第一个邻接结点
 *          3）若w存在，则继续执行步骤4，如果w不存在，则回到步骤1，将从v的下一个结点继续
 *          4）若w未被访问，对w进行深度优先遍历递归（即把w当作别一个v，然后进行步骤123）
 *          5）查找结点v的w邻接结点的下一个结点，转到步骤3
 *  （3）用广度优先方式遍历
 *      思路分析：
 *          1）访问初始结点v并标记结点v已访问
 *          2）结点v入队列
 *          3）当队列非空时，继续执行，否则算法结束
 *          4）出队列，取得队头结点u
 *          5）查找结点u的第一个邻接结点w
 *          6）若结点u的邻接结点w不存在，则转到步骤3；否则执行以下三个步骤：
 *              6.1 若结点w尚未被访问，则访问结点w并标记为已访问
 *              6.2 结点w入队列
 *              6.3 查找结点u的继w邻接结点后的下一个邻接结点w，转到步骤6
 *
 * @Author xw
 * @Date 2019/9/26
 */
public class Graph {
    private List<String> vertexList; // 顶点
    private int[][] edges; // 存储图对应的邻结矩阵
    private int numOfEdges; // 表示边的数目
    private boolean[] isVisited; // 边是否被访问过
    public static void main(String[] args) {
        // 创建图
        Graph graph = new Graph(5);
        // （1）添加顶点
        graph.insertVertex("A");
        graph.insertVertex("B");
        graph.insertVertex("C");
        graph.insertVertex("D");
        graph.insertVertex("E");
        // （2）添加边
        // A-B,A-C,B-C,B-D,B-E
        graph.insertEdge(0,1, 1);
        graph.insertEdge(0,2, 1);
        graph.insertEdge(1,0, 1);
        graph.insertEdge(1,2, 1);
        graph.insertEdge(1,3, 1);
        graph.insertEdge(1,4, 1);
        // show一把
        graph.showGraph();
        // 深度优先思路分析：
        // 1）访问初始结点，并标记结点v为已访问
        // 2）查找结点v的第一个邻接结点
        // 3）若w存在，则继续执行步骤4，如果w不存在，则回到步骤1，将从v的下一个结点继续
        // 4）若w未被访问，对w进行深度优先遍历递归（即把w当作别一个v，然后进行步骤123）
        // 5）查找结点v的w邻接结点的下一个结点，转到步骤3
        System.out.println("=========== 深度优先  ==========");
        graph.dfs();
        System.out.println();
        // 广度优先思路分析：思路分析：
        // 1）访问初始结点v并标记结点v已访问
        // 2）结点v入队列
        // 3）当队列非空时，继续执行，否则算法结束
        // 4）出队列，取得队头结点u
        // 5）查找结点u的第一个邻接结点w
        // 6）若结点u的邻接结点w不存在，则转到步骤3；否则执行以下三个步骤：
        //  6.1 若结点w尚未被访问，则访问结点w并标记为已访问
        //  6.2 结点w入队列
        //  6.3 查找结点u的继w邻接结点后的下一个邻接结点w，转到步骤6
        System.out.println("=========== 广度优先  ==========");
        graph.bfs();
    }
}

深度优先算法

/**
 *
 * @param isVisited 访问标识
 * @param i 从第0个元素开始
 */
public void dfs(boolean[] isVisited, int i) {
    // 1）访问初始结点，并标记结点v为已访问
    System.out.print(getValueByIndex(i) + "->");
    isVisited[i] = true;
    // 2）查找结点v的第一个邻接结点
    int w = getFirstNeighbor(i);
    // 3）若w存在，则继续执行步骤4，如果w不存在，则回到步骤1，将从v的下一个结点继续
    while (w != -1) {
        if (!isVisited[w]) {
            dfs(isVisited, w);
        }
        // 如果w已经被访问过
        w = getNextNeighbor(i, w);
    }
    // 4）若w未被访问，对w进行深度优先遍历递归（即把w当作别一个v，然后进行步骤123）
}

广度优先算法

// 广度优先
public void bfs(boolean[] isVisited, int i) {
    // 1）访问初始结点v并标记结点v已访问
    System.out.print(getValueByIndex(i) + "->");
    isVisited[i] = true;
    // 2）结点v入队列
    LinkedList queue = new LinkedList();
    queue.addLast(i);
    // 3）当队列非空时，继续执行，否则算法结束
    Integer u;
    Integer w;
    while (!queue.isEmpty()) {
        // 4）出队列，取得队头结点u
        u = (Integer) queue.removeFirst();
        // 5）查找结点u的第一个邻接结点w
        w = getFirstNeighbor(u);
        while (w != -1) {
            // 6.1 若结点w尚未被访问，则访问结点w并标记为已访问
            if (!isVisited[w]) {
                System.out.print(getValueByIndex(w) + "->");
                isVisited[w] = true;
                // 6.2 结点w入队列
                queue.addLast(w);
            }
            // 6.3 查找结点u的继w邻接结点后的下一个邻接结点w，转到步骤6
            w = getNextNeighbor(u, w);
        }
    }
}

算法

程序员常用10大算法

二分查找算法（非递归）

/**
 * @desc 二分查询（非递归方式）
 * 案例：
 * {1,3,8,10,11,67,100}，编程实现二分查找，要求使用非递归方式完成。
 * @Author xw
 * @Date 2019/9/27
 */
public class BinarySearchNonRecursive {
    public static void main(String[] args) {
        int[] arr = {1, 3, 8, 10, 11, 67, 100};
        int index = binarySearch(arr, 1);
        if (index != -1) {
            System.out.println("找到了，下标为：" + index);
        } else {
            System.out.println("没有找到--");
        }
    }
    private static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] > target) {
                right = mid - 1; // 向左找
            } else {
                left = mid + 1; // 向右找
            }
        }
        return -1;
    }
}

分治算法

/**
 * @desc 分治算法案例：汉诺塔
 * （1）基本概念
 * 分治算法是一种很重要的算法，字面上的解释是“分而治之”，就是把一个复杂的问题
 * 分解成两个或更多的相同或相似的子问题...直到最后子问题可以简单的直接求解，原
 * 问题的解即子问题的解的合并，这个技巧就是很多高效算法的基础，如排序算法（快速排序，归并排序），傅里叶变换（快速傅里叶变换）...
 * （2）基本步骤
 * 1）分解：将原问题分解为若干个规模较小的问题，相互独立，与原问题形式相同的子问题
 * 2）解决：若子问题规模较小则直接解决，否则递归地解各个子问题
 * 3）合并：将各个子问题的解合并为原问题的解
 * （3）分治算法设计模式
 * if |P|<=n0
 * then return (ADHOC(P))
 * // 将P分解为较小的问题P1,P2...PK
 * for i <- 1 to k
 * do yi <- Divide-and-Conquer(Pi) 递归解决Pi
 * T <- MERGE(y1,y2...yk) 合并子问题
 * return (T)
 * <p>
 * |P|：表示问题P的规模
 * n0：表示阈值，表示当问题P的规模不超过n0时，问题已容易直接解出，不必再继续分解。
 * ADHOC(P)：是该分治法中的基本子算法，用于直接解小规模的问题P。因此，当P的规模不超过n0时直接用算法ADHOC(P)求解
 * 算法MERGE(y1,y2...yk)：是该分治算法中的合并子算法，用于将P的子问题P1,P2...PK的相应的解y1,y2,..yk合并为P的解。
 * <p>
 * 经典案例：汉诺塔
 * 思路分析：
 * （1）如果有一个盘，A->C
 * n0=2
 * if (n<=n0) {
 * // 直接解出来
 * }
 * // 将P分解为较小的问题P1,P2...PK
 * while(n>n0) {
 * 分(n);
 * n--;
 * }
 * // T <- MERGE(y1,y2...yk) 合并子问题
 * @Author xw
 * @Date 2019/9/27
 */
public class HanoiTower {
    public static void main(String[] args) {
        hanoiTower(3, 'A', 'B', 'C');
    }
    private static void hanoiTower(int num, char a, char b, char c) {
        if (num == 1) { // 只有一个盘，直接解出
            System.out.println("第1个盘从" + a + "->" + c);
        } else {
            // 如果n>=2的情况
            // 1.先把最上面的所有盘A->B，移动过程会使用C
            hanoiTower(num - 1, a, c, b);
            // 2.把最下边的盘A->C
            System.out.println("第" + num + "个盘从" + a + "->" + c);
            // 3.把B塔所有盘从B->C，移动过程使用到A
            hanoiTower(num - 1, b, a, c);
        }
    }
}

动态规划算法

/**
 * @desc 动态规划算法案例：背包问题
 * 思路分析：
 * （1）假设：
 * 用w[i],v[i]来确定是否需要将该物品放入背包中；
 * 即对于给定的n个物品，设v[i],w[i]分别为第i个物品的价值和重量，C为背包的容量。
 * 再令v[i][j] 表示在前i个物品中能够装入容量j的背包的最大价值。则我们有下面的结果：
 * （2）结论：
 * 1）当v[i][0]=v[0][j]=0; // 表示填入表 第一行和第一列是0
 * 2）当w[i]>j时；v[i][j]=v[i-1][j] // 当准备加入新增的商品的容量大于当前背包的容量时，就直接使用上一个单元格的装入策略
 * 3）当j>=w[i]时；v[i][j]=max{v[i-1][j], v[i]+v[i-1][j-w[i]]}
 * // 当准入的新增的商品的容量小于等于当前背包的容量，装入方式：
 * v[i-1][j]：就是上一个单元格的装入的最大值
 * v[i]：表示当前商品的价值
 * v[i-1][j-w[i]]：装入i-1商品，到剩余空间j-w[i]的最大值
 * 当j>=w[i]时：v[i][j] = max{v[i-1][j], v[i-1][j-w[i]]}
 * <p>
 * 案例：
 * 物品      重量  价格
 * 吉他（G）   1   1500
 * 音响（S）   4   3000
 * 电脑（L）   3   2000
 * @Author xw
 * @Date 2019/9/27
 */
public class KnapsackProblem {
    public static void main(String[] args) {
        int[] w = {1, 4, 3}; // 物品重量
        int[] val = {1500, 3000, 2000}; // 物品价值
        int m = 4; // 背包的容量
        int n = val.length; // 物品个数
        // 创建二维数据
        int[][] v = new int[n + 1][m + 1];
        // 1）当v[i][0]=v[0][j]=0; // 表示填入表 第一行和第一列是0
        for (int i = 0; i < v.length; i++) {
            v[0][i] = 0; // 第一列为0
        }
        for (int i = 0; i < v.length; i++) {
            v[i][0] = 0; // 第一行为0
        }
        int[][] path = new int[n + 1][m + 1];
        for (int i = 1; i < v.length; i++) {
            for (int j = 1; j < v[0].length; j++) { // 不处理第1列
                // 当w[i]>j时；v[i][j]=v[i-1][j] // 当准备加入新增的商品的容量大于当前背包的容量时，就直接使用上一个单元格的装入策略
                if (w[i - 1] > j) {
                    v[i][j] = v[i - 1][j];
                } else {
                    // 当j>=w[i]时；v[i][j]=max{v[i-1][j], v[i]+v[i-1][j-w[i]]}
                    // v[i-1][j]：就是上一个单元格的装入的最大值
                    // v[i]：表示当前商品的价值
                    // v[i-1][j-w[i]]：装入i-1商品，到剩余空间j-w[i]的最大值
                    // 当准入的新增的商品的容量小于等于当前背包的容量，装入方式：
                    if (v[i - 1][j] < val[i - 1] + v[i - 1][j - w[i - 1]]) { // w[i]->w[i-1]替换?
                        v[i][j] = val[i - 1] + v[i - 1][j - w[i - 1]];
                        // 把当前的情况记录到path
                        path[i][j] = 1;
                    } else {
                        v[i][j] = v[i - 1][j];
                    }
                }
            }
        }
        // 输出一把
        for (int i = 0; i < v.length; i++) {
            for (int j = 0; j < v[i].length; j++) {
                System.out.print(v[i][j] + "\t");
            }
            System.out.println();
        }
        System.out.println("========================");
        /*for (int i = 0; i < path.length; i++) {
            for (int j = 0; j < path[i].length; j++) {
                if (path[i][j] == 1) {
                    System.out.println(String.format("第%d个商品放入背包", i));
                }
            }
        }*/
        // 其实我们只需要最后的放入
        int i = path.length - 1;
        int j = path[0].length - 1;
        while (i > 0 && j > 0) {
            if (path[i][j] == 1) {
                System.out.println(String.format("第%d个商品放入到背包", i));
                j -= w[i - 1];
            }
            i--;
        }
    }
}

KMP算法

/**
 * @desc KMP算法
 * 基本介绍：
 * （1）暴力匹配算法
 *      1）如果当前字符匹配成功（即str1[i]=str2[i]），则i++,j++，继续匹配下一个字符
 *      2）如果失败，令i=i-(j-1)，j=0，相当于每次匹配失败时，i回溯，j被转为0
 *      3）用暴力方法解决的话就会有大量的回溯，每次只移动一位，若是不匹配，移动到下一位接着判断，浪费大量时间。（不可行）
 *      4）暴力匹配实现
 * （2）KMP算法介绍
 *      1）KMP是一个解决模式串在文本串是否出现过，如果出现过，最早出现的位置就经典算法。
 *      2）Knuth-Morris-Pratt字符串查找法，简称KMP。
 *      3）KMP算法就是利用之前判断过信息，通过一个next数组，保存模式串中前后最长公共序列的长度，每次回溯时，通过next数组找到，
 *          前面匹配的位置，省去了大量的计算时间
 *      4）参考资料：https://www.cnblogs.com/ZuoAndFutureGirl/p/9028287.html
 * @Author xw
 * @Date 2019/9/27
 */
public class KMPAlgorithm {
    public static void main(String[] args) {
        // 暴力匹配
        String str1 = "ABCDE";
        String str2 = "CD";
        int index = violenceMatch(str1, str2);
        if (index != -1) {
            System.out.println("找到了，位置：" + index);
        } else {
            System.out.println("没有找到！");
        }
        // KMP算法介绍
        // 字符串模板匹配值
        str1 = "BBC ABCDAD ABCDABCDABDE";
        str2 = "ABCDABD";
        /*int[] next = kmpNext("ABCDABD");
        System.out.println("next=" + Arrays.toString(next));*/
        index = kmpMatch(str1, str2, kmpNext(str2));
        if (index != -1) {
            System.out.println("找到了，位置：" + index);
        } else {
            System.out.println("没有找到！");
        }
    }
}

贪心算法

/**
 * @desc 贪心算法
 * 思路分析
 * （1）使用穷举法，列出每个可能广播台集合，这被称为幂集。
 * （2）假设有n个广播台，则广播台的组合共有2^n-1个，假设每秒可以计算10个子集
 *      广播台数量   子集总数    需要的时间
 *      5               32          3.2秒
 *      10              1024        102.4秒
 *      ...
 *
 *  案例：集合覆盖问题
 *      假设存在下面需要付费的广播台，以及广播信号可以覆盖的地区，如何选择
 *      最少的广播台，让所有的地区都可以接收信息
 *      广播台     覆盖地区
 *      K1          "北京","上海","天津"
 *      K2          "广州","北京","深圳"
 *      K3          "成都","上海","杭州"
 *      K4          "上海","天津"
 *      K5          "杭州","大连"
 * @Author xw
 * @Date 2019/9/27
 */
public class GreedyAlgorithm {
    public static void main(String[] args) {
        Map<String, Set<String>> broadcasts = new HashMap<>(); // 广播电台
        broadcasts.put("K1", Arrays.stream(new String[]{"北京", "上海", "天津"}).collect(Collectors.toSet()));
        broadcasts.put("K2", Arrays.stream(new String[]{"广州", "北京", "深圳"}).collect(Collectors.toSet()));
        broadcasts.put("K3", Arrays.stream(new String[]{"成都", "上海", "杭州"}).collect(Collectors.toSet()));
        broadcasts.put("K4", Arrays.stream(new String[]{"上海", "天津"}).collect(Collectors.toSet()));
        broadcasts.put("K5", Arrays.stream(new String[]{"杭州", "大连"}).collect(Collectors.toSet()));
        // [上海, 天津, 北京, 广州, 深圳, 成都, 杭州, 大连]
        List<String> allAreas = broadcasts.values().stream().flatMap(Collection::stream).distinct().collect(Collectors.toList()); // 表示所有需要覆盖的地区
        System.out.println("allAreas=" + allAreas);
        List<String> selects = new ArrayList<>(); // 选择的地区集合
        // 定义一个临时的集合，在遍历过程中，存放遍历过程中的电台覆盖的地区和当前还没有覆盖的地区的交集
        Set<String> tempSet = new HashSet<>();
        String maxKey; // 最大的电台，保存在一次遍历过程中，能够覆盖最大未覆盖的地区对应的电台key
        while (allAreas.size() != 0) {
            maxKey = null; // 置空
            // 遍历broadcasts，取出对应key
            for (String key : broadcasts.keySet()) {
                tempSet.clear(); // 清空
                Set<String> areas = broadcasts.get(key);
                tempSet.addAll(areas);
                tempSet.retainAll(allAreas); // tempSet = tempSet与allAreas的交集
                if (tempSet.size() > 0 && (maxKey == null
                        || tempSet.size() > broadcasts.get(maxKey).size())) {
                    maxKey = key;
                }
            }
            if (maxKey != null) {
                selects.add(maxKey);
                // 将maxKey指向的广播电台覆盖地区，从allAreas去掉
                System.out.println("maxKey=" + maxKey);
                allAreas.removeAll(broadcasts.get(maxKey));
            }
        }
        System.out.println("得到的选择结果是：" + selects);
    }
}

普利姆算法

/**
 * @desc 普利姆算法
 * 应用案例：修路问题
 * <p>
 * 思路分析
 *  1.从<A>顶点开始处理=><A,G> 2
 *      A,C[7] A-G[2] A-B[5] =>
 *  2.<A,G>开始，将A和G顶点和他们相邻的还没有访问的顶面进行处理=> <A,G,B>
 *      A-C[7] A-B[5] G-B[3] G-F[6]
 *  3.<A,G,B>开始，将A,G,B顶点和他们相邻的还没有访问的顶面进行处理=> <A,G,B>
 *      A-C[7] G-E[4] G-F[6] B-D[9]
 *  ...
 *  4.{A,G,B,E,F,D} -> C // 第6次大循环，对应边<A,C>权值：7 => <A,G,B,E,F,D,C>
 * @Author xw
 * @Date 2019/10/4
 */
public class PrimAlgorithm {
    public static void main(String[] args) {
        char[] data = {'A','B','C','D','E','F','G'};
        int verxs = data.length;
        // 邻接矩阵
        int[][] weight = new int[][] {
                {10000,5,7,10000,10000,10000,2},
                {5,10000,10000,9,10000,10000,3},
                {7,10000,10000,10000,8,10000,10000},
                {10000,9,10000,10000,10000,4,10000},
                {10000,10000,8,10000,10000,5,4},
                {10000,10000,10000,4,5,10000,6},
                {2,3,10000,10000,4,6,10000}
        };
        // 创建MGraph对象
        MGraph graph = new MGraph(verxs);
        // 创建最小树
        MinTree minTree = new MinTree();
        minTree.createGraph(graph, verxs, data, weight);
        // 输出
        minTree.showGraph(graph);
        // 测试普利姆算法
        minTree.prim(graph, 0);
    }
}

克鲁斯卡尔算法

/**
 * @desc 克鲁斯卡尔算法
 * 案例：公交车问题
 * 1. 某城市新增7个站点，A,B,C,D,E,F,G,现在需要修路7个站点连通
 * 2. 各个站点距离用连线表示，比如A-B距离12公里
 * 3. 问：如何修路保证各个站点都能连通，并且总的修建公路总里程最短
 * @Author xw
 * @Date 2019/10/8
 */
public class KruskalCase {
    private static final int INF = Integer.MAX_VALUE;
    private char[] vertexs;
    private int[][] matrix;
    private int edgeNums; // 边的数量
    public KruskalCase(char[] vertexs,int[][] matrix ) {
        this.vertexs = vertexs;
        this.matrix = matrix;
        // 统计边
        for (int i = 0; i < vertexs.length; i++) {
            for (int j = i + 1; j < vertexs.length; j++) { // 每次少一条边，所以是i+1
                if (this.matrix[i][j] != INF) {
                    edgeNums++;
                }
            }
        }
    }
    public static void main(String[] args) {
        char[] vertexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int[][] matrix = {
                     /*A*//*B*//*C*//*D*//*E*//*F*//*G*/
                /*A*/{ 0,   12, INF,  INF, INF, 16,  14 },
                /*B*/{ 12,  0,   10,  INF, INF, 7,   INF},
                /*C*/{ INF, 10,  0,   3,    5,  6,   INF },
                /*D*/{ INF, INF, 3,   0,    4,  INF, INF },
                /*E*/{ INF, INF, 5,   4,    0,  2,   8 },
                /*F*/{ 16,  7,   6,   INF,  2,  0,   9 },
                /*G*/{ 14,  INF, INF, INF,  8,  9,   0 }
        };
        // 创建KruskalCase对象实例
        KruskalCase kruskalCase = new KruskalCase(vertexs, matrix);
        //
        kruskalCase.print();
        kruskalCase.kruskal();
    }
}

迪杰斯特拉算法

/**
 * @desc 迪杰斯特拉算法
 * 案例：最短路径问题
 * 1. 战争时期，胜利乡有7个村庄(A,B,C,D,E,F,G)，现在有6个邮差，从G点出发，需要分别把邮件分别送到A,B,C,D,E,F 六个村庄
 * 2. 各个村庄的距离用边线表示（权），比如A-B距离5公里
 * 3. 问：如何计算最短距离
 *
 * @Author xw
 * @Date 2019/10/8
 */
public class DijkstraAlgorithm {
    public static void main(String[] args) {
        char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int[][] matrix = new int[vertex.length][vertex.length];
        final int N = 65535;
        matrix[0] = new int[]{N,5,7,N,N,N,2};
        matrix[1] = new int[]{5,N,N,9,N,N,3};
        matrix[2] = new int[]{7,N,N,N,8,N,N};
        matrix[3] = new int[]{N,9,N,N,N,4,N};
        matrix[4] = new int[]{N,N,8,N,N,5,4};
        matrix[5] = new int[]{N,N,N,4,5,N,6};
        matrix[6] = new int[]{2,3,N,N,4,6,N};
        // 创建Graph对象
        Graph graph = new Graph(vertex, matrix);
        graph.showGraph();
        // 测试迪杰斯特拉算法
        graph.dsj(6); // G
        graph.showDijkstra();
    }
}

弗洛伊德算法

/**
 * @desc 弗洛伊德算法
 * @Author xw
 * @Date 2019/10/8
 */
public class FloydAlgorithm {
    public static void main(String[] args) {
        char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int[][] matrix = new int[vertex.length][vertex.length];
        final int N = 65535;
        matrix[0] = new int[]{0, 5, 7, N, N, N, 2};
        matrix[1] = new int[]{5, 0, N, 9, N, N, 3};
        matrix[2] = new int[]{7, N, 0, N, 8, N, N};
        matrix[3] = new int[]{N, 9, N, 0, N, 4, N};
        matrix[4] = new int[]{N, N, 8, N, 0, 5, 4};
        matrix[5] = new int[]{N, N, N, 4, 5, 0, 6};
        matrix[6] = new int[]{2, 3, N, N, 4, 6, 0};
        FloydGraph graph = new FloydGraph(vertex.length, matrix, vertex);
        graph.floyd();
        graph.show();
    }
}

马踏棋盘算法

/**
 * @desc 马踏棋盘算法
 * @Author xw
 * @Date 2019/10/8
 */
public class HorseChessboard {
    private static int X; // 棋盘的列数
    private static int Y; // 棋盘的行数
    //创建一个数组，标记棋盘的各个位置是否被访问过
    private static boolean visited[];
    //使用一个属性，标记是否棋盘的所有位置都被访问
    private static boolean finished; // 如果为true,表示成功
    public static void main(String[] args) {
        System.out.println("骑士周游算法，开始运行~~");
        //测试骑士周游算法是否正确
        X = 8;
        Y = 8;
        int row = 1; //马儿初始位置的行，从1开始编号
        int column = 1; //马儿初始位置的列，从1开始编号
        //创建棋盘
        int[][] chessboard = new int[X][Y];
        visited = new boolean[X * Y];//初始值都是false
        //测试一下耗时
        long start = System.currentTimeMillis();
        traversalChessboard(chessboard, row - 1, column - 1, 1);
        long end = System.currentTimeMillis();
        System.out.println("共耗时: " + (end - start) + " 毫秒");
        //输出棋盘的最后情况
        for(int[] rows : chessboard) {
            for(int step: rows) {
                System.out.print(step + "\t");
            }
            System.out.println();
        }
    }
}