Java 数据结构与算法

大 O 表示法：比较的是操作数，指出算法运行时间的增速。

如何选择数组和链表：

增删情况较多的需求下选择链表。
改查情况较多的情况下选择数组。

选择排序

每次循环找当前查询数组中最小或者最大元素的索引
得到索引之后，将索引位置的值与顺序放置位置交换
直至循环结束

🗝特点：找到最小或者最大元素的索引，通过索引进行元素交换。

class Solution {
    public int[] sort( int[] nums) {
        for(int i = 0; i<nums.length - 1 ; i++){
            //记录当前最小值及其Index
            int minNum = nums[i];
            int minIndex = i;
            for(int j = i + 1 ; j < nums.length; j++){
               //minNum 需要更新最小元素
                if(minNum > nums[j]){
                    //找到了更小元素的Index
                    minIndex = j;
                    minNum = nums[j];
                }
            }
            //最小元素放置于当前遍历数组的第一个位置
            //即根据index交换值
            nums[minIndex] = nums[i];
            nums[i] = minNum;
        }
        return nums;
    }
}

递归

🗝递归的两个条件：

基线条件：防止死循环
递归条件：自己调用自己

public int recursion(int n){
	//基线条件
    if (n == 1){
        return n;
    //递归条件
    } else {
        return recursion(n - 1) + n;
    }
}

链表队列

双向链表

单向链表的缺点：

只能一个方向查找
不能实现自我删除，需要辅助节点

双向链表的遍历：可以向前和向后遍历

添加：先找到最后节点，temp.next = newNode; newNode.pre = temp

修改：

删除：实现自我删除： node5.pre.next= node5.next; node5.next.pre = node5.pre

单向环形链表约瑟夫问题

//according the input of the user, calculate the order
/**
 * @param startNo  no. of the first boy
 * @param countNum gap num
 * @param nums     total num of boy
 */
public void countBoys(int startNo, int countNum, int nums) {
    if (first == null || startNo < 1 || startNo > nums) {
        System.out.println("Error Input");
        return;
    }
    //first pointer point to the startNo
    for (int i = 0; i < startNo - 1; i++) {
        first = first.getNext();
    }
    Boy helper = first;
    //helper pointer the last node
    while (true) {
        if (helper.getNext() == first) {
            break;
        }
        helper = helper.getNext();
    }
    //move countNum - 1 exit
    while (true) {
        if (helper == first) {
            break;
        }
        //move first and helper countNo -1
        for (int i = 0; i < countNum - 1; i++) {
            first = first.getNext();
            helper = helper.getNext();
        }
        //first points the node(boy) exiting circle
        System.out.println("The num of boy who left the circle is " + first.getNo());
        first = first.getNext();
        helper.setNext(first);
    }
    System.out.println("The num of last one is " + first.getNo());
}

栈

FIFO

应用场景

//create a array stack
class ArrayStack{
    private int maxSize; //size of stack
    private int[] stack; //stack
    private int top = -1; // top of stack

    public ArrayStack(int maxSize) {
        this.maxSize = maxSize;
        stack = new int[maxSize];
    }

    //stack is full
    public boolean isFull(){
        return top == maxSize-1;
    }
    //stack is empty
    public boolean isEmpty(){
        return top == -1;
    }
    //push
    public void push(int value){
        if(isFull()){
            System.out.println("Stack is Full");
            return;
        }
        top++;
        stack[top] = value;
    }
    //pop
    public int pop(){
        if(isEmpty()){
            throw new RuntimeException("Stack is Empty");
        }
        int value = stack[top];
        top--;
        return value;
    }
    //print stack
    public void list(){
        if (isEmpty()){
            System.out.println("Stack is Empty");
            return;
        }
        for (int i = top; i >= 0 ; i--) {
            System.out.println("Stack num is: " + stack[i]);
        }
    }
}

栈实现综合计算器

编写特点：

写MyStack在继承Java 提供的 Stack
在MyStack 中提供运算符优先级判断，使用数字表示 * ：2，+：1
在MyStack 中提供符号判断的方法
在MyStack 中提供运算方法
使用字符扫描字符串表达式根据扫描到的运算符判断当前是否可以进行运算
主要 char 和 int 转换时 char （‘7’，’0‘）（70）可能是两个字符，需要使用字符串配合符号判断对70进行拼接
扫描越界问题

中缀表达式转后缀表达式

public static List<String> parseSuffixExprList(List<String> ls) {
    Stack<String> s1 = new Stack<>(); //for input operator first
    List<String> s2 = new ArrayList<>();//for input number first

    for (String item : ls) {
        //if item is num
        if(item.matches("//d+")){
            s2.add(item);
        }else if(item.equals("(")){
            s1.push(item);
        }else if(item.equals(")")){
            while (!s1.peek().equals("(")){
                s2.add(s1.pop());
            }
            s1.pop();//pop the (
        }else {
            while (s1.size() != 0 &&
                    !s1.peek().equals("(") &&
                    priority(s1.peek()) >= priority(item)){
                s2.add(s1.pop());
            }
            //s1 == empty or priority(s1.peek()) < priority(item)
            s1.push(item);
        }
    }
    //pop the left item of s1 into s2
    while (s1.size() != 0){
        s2.add(s1.pop());
    }
    return s2;
}


public static int priority(String operator){
    if(operator.equals("*") || operator.equals("/")){
        return 2;
    }else if(operator.equals("+") || operator.equals("-")){
        return 1;
    }else {
        throw new RuntimeException("ERROR OPERATOR");
    }
}

递归

迷宫问题：

编写思路

确定策略：先上？上-》下-》左-》右去尝试
设置递归退出条件，即走到了目的地
先占位置 map/[ i ][ j ] = 2 ，然后走;
在进入迷宫时尝试探索下一步，如果下一步可行返回 true 继续递归
在遇见当前路是墙：1，走过的：2，死路：3 就返回 false

package com.test.recursion;

public class Maze {
    public static void main(String[] args) {
        //create a map
        int[][] map = new int[8][7];
        //1:wall
        for (int i = 0; i < 7; i++) {
            map[0][i] = 1;
            map[7][i] = 1;
            map[i + 1][0] = 1;
            map[i + 1][6] = 1;
        }
        map[3][1] = 1;
        map[3][2] = 1;
        map[1][2] = 1;
        map[2][2] = 1;

        Maze.setWay(map, 1, 1);
        System.out.println("map is:");
        for (int[] ints : map) {
            for (int anInt : ints) {
                System.out.print(anInt + " ");
            }
            System.out.println();
        }

    }

    //using recursion help the ball:2 find a way

    /**
     * 1:wall
     * 2:way
     * 3:the position has been walked, but it is not the right way, next time
     * you don't need to walk.
     * 1. strategy: down->right->up->left, if it is not right, recall
     *
     * @param map: map
     * @param i:   (i,j): start position
     * @param j:   (6,5): terminated position
     * @return find a way return true, else return false
     */
    public static boolean setWay(int[][] map, int i, int j) {
        if (map[6][5] == 2) {
            return true;
        } else {
            //the position hasn't been walked
            //Each recursion, it help to set the position = 2
            if (map[i][j] == 0) {
                map[i][j] = 2;
                //down
                if (setWay(map, i + 1, j)) {
                    return true;
                }
                //right
                else if (setWay(map, i, j + 1)) {
                    return true;
                }
                //up
                else if (setWay(map, i - 1, j)) {
                    return true;
                }
                //left
                else if (setWay(map, i, j - 1)) {
                    return true;
                } else {
                    map[i][j] = 3;
                    return false;
                }
            }else {
                return false;
            }
        }
    }

八皇后问题

编写思路：

拆分问题
1. 设置输出函数输出每次的找的结果
2. 设置check 函数检查防止是否符合要求（对于斜线上的要巧用函数的思维，即斜率为1 or -1）
3. 设置放置函数放置皇后
4. 先占位置 array[n] = i; 再判断 if(isNotConflict(n)
在编写放置皇后函数时
1. 设置递归退出条件
2. 由于每次每列只有一个皇后，即 n th 列数== n th 皇后
3. 在每列放置皇后时，如果当前位置不冲突，就去递归检查下一行 or 下一个皇后
4. 如果当前列中当前的位置不对，则循环 check 下一个位置，如果 check（n+1）没有找到，退出 if 条件，尝试 n 行中的下一个位置

package com.test.recursion;

public class EightQueen {

    //define a max present the number of Queen
    int max = 8;
    //define a array to store the result of position
    int[] array = new int[max];

    //to count the number of solutions
    static int count = 0;
    public static void main(String[] args) {
        EightQueen eightQueen = new EightQueen();
        eightQueen.check(0);
        System.out.println(count);

    }

    //put a Queen in the right position
    //n: meaning the nth Queen and the Queen in the nth line
    private void check(int n){
        //exit recursion
        if(n == max){
            print();
            count++;
            return;
        }

        //put the Queen in right position by order in a line
        for (int i = 0; i < max; i++) {
            //1. put the ith Queen in the first column in a line
            array[n] = i;
            //n: meaning the nth Queen and the Queen in the nth line
            //if not conflicting, check next queen
            //if we find there are not position to put the queen(n+1) in the line
            //it will continue run the queen(n) loop to check the next position in the line
            if(isNotConflict(n)){
                check(n+1);
            }
            //if conflicting or check(n+1) can't not find right position,
            // loop continue to check next position in the line
        }
    }

    //Print the position of Queen
    private void print() {
        for (int i : array) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    //check the position of nth Queen to know whether it is conflicted to the
    //position of the (1st -> n-1th) Queen.

    /**
     * @param n: nth Queen
     * @return
     */
    private boolean isNotConflict(int n) {
        for (int i = 0; i < n; i++) {
            //1. array[i] == array[n]: they are in same column
            //2. They are in same bias line.
            //y2-y1 == x2-x1 =》 k value : 1
            //y2-y1 == -(x2-x1) =》 k value : -1
            //3. They are in same line, the loop have helped us to check
            // They can't be in same line.
            if (array[i] == array[n] ||
                    (n - i) == (array[n] - array[i]) ||
                    (n - i) == -(array[n] - array[i])) {
                return false;
            }
        }
        return true;
    }

}

排序算法

冒泡排序

编写思维：

相邻元素之间发生交换
大循环次数 = 元素的个数 - 1 《== 每次大循环都会确定最大的一个数的位置，知道确定第二位置，就结束了（第一个自动就是最小）
小循环的次数 = 待排元素的个数 - 1 《== 待排元素的个数和大循环的次序有关, 即元素个数 -（ 0, 1, 2, 3, … ）
优化：一次循环中一次交换都没有发生过，即数组已经有序。（每次都是从左至右依次两两比较，即 1< 2 ，2 < 3 ==》1 < 2 < 3）

package com.test.sort;

public class BubbleSort {
    public static void main(String[] args) {
        int arr[] = {3, 9, -1, 10, -2};

        int tmp = 0;
//        //for the first sort 4 times
//        //put the biggest in the last
//        for (int j = 0; j < arr.length - 1; j++) {
//            if(arr[j] > arr[j+1]){
//                tmp = arr[j];
//                arr[j] = arr[j+1];
//                arr[j+1] = tmp;
//            }
//        }
//        for (int i : arr) {
//            System.out.println(i);
//        }
//        //for the second sort 4 times
//        for (int j = 0; j < arr.length - 2; j++) {
//            if(arr[j] > arr[j+1]){
//                tmp = arr[j];
//                arr[j] = arr[j+1];
//                arr[j+1] = tmp;
//            }
//        }
//        for (int i : arr) {
//            System.out.println(i);
//        }
        //We can think just like above
        // flag means that during the sorting, elements whether swap.
        boolean flag = false;
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    flag = true;
                    tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                }
            }
            //In this inner loop, there is not swapping between the elements
            if (!flag){
                break;
            } else {
                flag = false;
            }
        }
        for (int i : arr) {
            System.out.println(i);
        }
    }
}

选择排序

由于只需要交换最小的元素，交换次数的减小使其性能由于冒泡排序

编写思路：

只是找到最小值的时候交换
每次找到当前待排数组中最小的数进行交换
需要发生交换就需要记录当前最小值及其index
大循环次数 = 元素个数 - 1 《= 需要第一个位置和后面的位置进行比较
小循环需要从 i + 1 开始《= 即第一个待排位置的下一位

public static void selectionSort(int[] arr) {
        int minNum;
        int minIndex;
        for (int i = 0; i < arr.length - 1; i++) {
            minNum = arr[i];
            minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (minNum > arr[j]) {
                    minNum = arr[j];
                    minIndex = j;
                }
            }
            //find the new minMun in this sorting
            if(minIndex != i){
                arr[i] = minNum;
                //put the bigger in j position
                arr[minIndex] = arr[i];
            }
        }
        for (int i : arr) {
            System.out.println(i);
        }
    }
}

插入排序

编写思路：

两个list，一个有序一个无序
每次都从大循环中取出一个元素，记录待插入元素（insertValue）及其前一个位置（insertIndex）
插入之前的有序表，从有序表的最后一位开始比较知道找到
第一次，第一个元素就是有序的，后面其他元素是无序的
中间比较时，有序表中较大的数需要移动位置为待插入的数（insertValue）腾出空间，使用 insertIndex 比较并记录位置。

    public static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length ; i++) {
            int insertValue = arr[i];
            int insertIndex = i - 1;
            //the number waiting for inserting to the sorted list need
            //compare to each number in the sorted list from the last position
            //of the sorted list
            while (insertIndex >= 0 && insertValue < arr[insertIndex]){
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex --;
            }
            arr[insertIndex + 1] = insertValue;
        }
        for (int i : arr) {
            System.out.println(i);
        }
    }
}

希尔排序

其目的是为了减少排序中的交换问题

交换式：

    public static void shellSort(int[] arr) {
        int tmp;
        for (int gap = arr.length / 2; gap > 0; gap = gap / 2) {
            for (int i = 0; i < arr.length - gap; i++) {
                for (int j = i + gap; j < arr.length; j = j + gap) {
                    if(arr[i] > arr[j]){
                        tmp = arr[i];
                        arr[i] = arr[j];
                        arr[j] = tmp;
                    }
                }
            }

        }
        for (int i : arr) {
            System.out.println(i);
        }
    }
}

测试之后：时间变慢 14s 左右（8w nums），主要是交换的次数变多了

移动法

快了很多 1s （8w nums）

    public static void shellSort(int[] arr) {
        for (int gap = arr.length / 2; gap > 0; gap = gap / 2) {
            for (int i = gap; i < arr.length; i++) {
                int insertValue = arr[i];
                int insertIndex = i - gap;
                //find a position
                while (insertIndex >= 0 && insertValue < arr[insertIndex]) {
                    arr[insertIndex + gap] = arr[insertIndex];
                    insertIndex = insertIndex - gap;
                }
                //insert the value
                arr[insertIndex + gap] = insertValue;
            }

        }
        for (int i : arr) {
            System.out.println(i);
        }
    }
}

快速排序

每一次遍历，我们在当前处理的数组上维护四个区域，如下图所示。

最左侧是小于等于主元的元素，中间左侧是大于主元的元素，中间右侧是待遍历的元素，最右侧是主元 $x$ 。

每一趟遍历之前，选取最后一个数作为主元x，通过遍历整个序列，把“无限制”区域的数放到区域一或区域二中。下图展示了给定序列的一趟快速排序过程。

编写思路：

确定递归的退出条件
确定排序的4个区域
给每个区域确定index
p, r 位置不变用于后面递归传递数组位置
i：表示比 x 小的数组的最后一个元素的 index
j: 表示unrestricted 区域首元素的index
每次 j 都会增加，当 unrestricted 元素小于 x 时，则与 i+1 的值即比 x 大的数组的第一个元素交换，由于每次 j 都会增加，则 >x 的数组个数和元素并没有受到影响。
完成一次扫描之后就递归操作

   /**
     * The recursive procedure in quick sort.
     *
     * @param arr The array to be sorted.
     * @param p   The start index of the sub-array to be sorted.
     * @param r   The end index of the sub-array to be sorted.
     */
    public static void quickSort(int[] arr, int p, int r) {
        if (p < r) {
            //pivot: pivot position
            int pivot = partition(arr, p, r);
            quickSort(arr, p, pivot - 1);
            quickSort(arr, pivot + 1, r);
        }
    }
    

    /**
     * Partition the array into two parts.
     * get int pivot position
     * <p>
     * After this method, elements greater than pivot are put right, others are put left.
     *
     * @param arr The array to be sorted.
     * @param p   The start index of the sub-array to be sorted.
     * @param r   The end index of the sub-array to be sorted.
     * @return The index of the pivot after partition.
     */
    public static int partition(int[] arr, int p, int r) {
        //x: the main element waiting for cut the array
        int x = arr[r];
        //i: the last index of array which elements are smaller than x
        int i = p - 1;
        int temp;
        //j: the first index of array which elements don't compare with x
        for (int j = p; j < r; j++) {
            if (arr[j] <= x) {
                i++;
                temp = arr[j];
                arr[j] = arr[i];
                arr[i] = temp;
            }
        }
        //put x in the pivot position
        temp = arr[i + 1];
        arr[i + 1] = x;
        arr[r] = temp;
        return i + 1;
    }
}

归并排序

编写思路

差分方法
在分中要设置递归退出条件
并中考虑复制方法

    public static void mergeSort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = (left + right) / 2;
            //left merge sort
            mergeSort(arr, left, mid, temp);
            //right merge sort
            mergeSort(arr, mid + 1, right, temp);
            //merge
            merge(arr, left, mid, right, temp);
        }
    }

    /**
     * @param arr   array waiting for being sorted
     * @param left  the first index of the arr
     * @param mid   the middle index of the arr
     * @param right the last index of the arr
     * @param temp  temp array to store the temp values
     */
    public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left; //first index of part one of the arr
        int j = mid + 1; //first index of part two of the arr
        int t = 0; //current index of temp

        //sorting the arr until the task of copying part one or two of the arr to temp is finished
        while (true) {
            if (i > mid || j > right) {
                break;
            }
            if (arr[i] <= arr[j]) {
                temp[t] = arr[i];
                t++;
                i++;
            } else {
                temp[t] = arr[j];
                t++;
                j++;
            }

        }

        //the left part of the arr directly copy to the temp
        while (i <= mid) {
            temp[t] = arr[i];
            i++;
            t++;
        }

        while (j <= right) {
            temp[t] = arr[j];
            j++;
            t++;
        }

        //copy the values of temp to arr in order
        //note: the arr is the only one from the beginning
        //the first index for each merge is not same
        t = 0;
        while (left <= right) {
            arr[left] = temp[t];
            left++;
            t++;
        }
    }
}

基数排序

编写思路：

确定最大数的位数
需要设置二位数组表示桶
需要设置一维数组记录当前放入桶的数据的个数
每次取出数据到原数组时需要将记录个数的数组清空

public static void radixSort(int[] arr) {

    //1. get the max num in the arr
    int max = arr[0];
    for (int i = 0; i < arr.length; i++) {
        if (max < arr[i]) {
            max = arr[i];
        }
    }
    int maxLength = (max + "").length();

    //set a two dimension array for presenting 10 buckets
    int[][] bucket = new int[10][arr.length];

    //using an array for recording each bucket have stored numbers of num
    int[] bucketElementCounts = new int[10];

    for (int k = 0, n = 1; k < maxLength; k++, n *= 10) {
        //the first round,(ones place)
        for (int i = 0; i < arr.length; i++) {
            int digitOfElement = arr[i] / n % 10;
            //put it in the bucket
            bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[i];
            bucketElementCounts[digitOfElement]++;
        }
        int index = 0;
        for (int i = 0; i < bucketElementCounts.length; i++) {
            if (bucketElementCounts[i] != 0) {
                for (int j = 0; j < bucketElementCounts[i]; j++) {
                    arr[index] = bucket[i][j];
                    index++;
                }
            }
            //when it has been put into the array, the bucketElementCounts should be set 0
            bucketElementCounts[i] = 0;
        }
        System.out.println(Arrays.toString(arr));
    }
}

排序对比

查找算法

二分查找

有序数组中查找

编写思路：

确定递归退出条件（1. 没有找到，由于每次递归 mid 值都已经对比过了，再下次设定向左或向右时，需要 -1 or +1，就会出现 left > right，则退出递归，2. 找到了）

public static int binarySearch(int[] arr, int value, int left, int right) {
    int mid = (left + right) / 2;
    if (left > right) {
        return -1;
    }
    if (arr[mid] > value) {
        return binarySearch(arr, value, left, mid - 1);
    } else if (arr[mid] < value) {
        return binarySearch(arr, value, mid + 1, right);
    } else {
        return mid;
    }
}

对于有多个相同值的数组

    public static ArrayList<Integer> binarySearch2(int[] arr, int value, int left, int right) {
        int mid = (left + right) / 2;
        if (left > right) {
            ArrayList<Integer> resIndexList = new ArrayList<>();
            return resIndexList;
        }
        if (arr[mid] > value) {
            return binarySearch2(arr, value, left, mid - 1);
        } else if (arr[mid] < value) {
            return binarySearch2(arr, value, mid + 1, right);
        } else {
            ArrayList<Integer> resIndexList = new ArrayList<>();
            resIndexList.add(mid);
            //scan left
            for (int tmp = mid - 1; tmp > 0; tmp--) {
                if (arr[tmp] == value) {
                    resIndexList.add(tmp);
                }
            }
            //scan right
            for (int tmp = mid + 1; tmp < arr.length; tmp++) {
                if (arr[tmp] == value) {
                    resIndexList.add(tmp);
                }
            }
            return resIndexList;
        }
    }

}

插值查找

自适应的算法，对于关键字分布均匀的查找表来说很快。

在分布不均匀的情况下不一定好于二分查找

public static int insertValueSearch(int[] arr, int value, int left, int right) {
    int mid = left + (right - left) * (value - arr[left]) / (arr[right] - arr[left]);
    if (left > right || value < arr[0] || value > arr[arr.length - 1]) {
        return -1;
    }
    if (arr[mid] > value) {
        return insertValueSearch(arr, value, left, mid - 1);
    } else if (arr[mid] < value) {
        return insertValueSearch(arr, value, mid + 1, right);
    } else {
        return mid;
    }
}

斐波拉契查找

由于其只涉及加减理论上可能比二分查找要快。

编写思路：

设置斐波那契的 index 数组
如果查找数组不够需要补充满足斐波那契数组的index值
切分查找数组为前 f[n-1]-1 和后 f[n-2]-1 两个部分 f[n]-1 (index) = f[n-1]-1 + f[n-2]-1 + 1 ( 1表示黄金分割位置上的数的个数)
则黄金分割数（mid）= low + f[n-1]-1
如果在左边，则 high = mid - 1；新一次的（index） mid = low + f[n-1-1] - 1，即需要 n–
如果在右边，则 low= mid + 1；新一次的（index） mid = low + f[n-1-2] - 1，即 low 已经从黄金分割数左边开始了，然后加上前面部分的开始，需要 n-=2。
如果 mid > high，则已经找到了填充数了，则返回 high 即可。

public class FibonacciSearch {
    public static int maxSize = 20;

    public static void main(String[] args) {
        int[] arr = {1, 8, 10, 89, 1000, 1234};
        System.out.println(fibSearch(arr, 8));
    }


    //create a Fibonacci array
    public static int[] fib() {
        int[] f = new int[maxSize];
        f[0] = 1;
        f[1] = 1;
        for (int i = 2; i < maxSize; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f;
    }

    /**
     * non-recursion
     *
     * @param arr the arr for finding a target value
     * @param key target value
     * @return index of target value in the arr
     */
    public static int fibSearch(int[] arr, int key) {
        int low = 0;
        int high = arr.length - 1;
        int k = 0;// the index of fibonacci array
        int mid = 0;
        int[] f = fib();
        while (high > f[k] - 1){
            k++;
        }
        //the f[k] may bigger than the length of array
        //copy the array to new array
        int[] tmp = Arrays.copyOf(arr,f[k]);
        //use the last num to fill the tmp
        for (int i = high+1; i < tmp.length; i++) {
            tmp[i] = arr[high];
        }
        while (low <= high){
            //mid is in the golden section
            //f[k-1]-1 is the first part of the temp
            mid = low + f[k-1]-1;
            if(key < tmp[mid]){
                high = mid - 1;
                k--;
            }else if(key > tmp[mid]){
                low = mid + 1;
                //the last numbers of f[k-2] of the temp
                k -= 2;
            }else{
                if(mid <= high){
                    return   mid;
                }else {
                   	//have found the data which are filled in the tmp
                    return high;
                }
            }
        }
        return -1;
    }
}

哈希表

package com.test.hashtable;

import java.util.Scanner;

public class HashTableDemo {
    public static void main(String[] args) {
        HashTable hashTable = new HashTable(7);
        String key = "";
        Scanner scanner = new Scanner(System.in);
        while (true) {
            System.out.println("add: add emp");
            System.out.println("list: list emp");
            System.out.println("find: find emp");
            System.out.println("exit");
            key = scanner.next();
            switch (key) {
                case "add":
                    System.out.println("input id");
                    int id = scanner.nextInt();
                    System.out.println("input name");
                    String name = scanner.next();
                    Emp emp = new Emp(id, name);
                    hashTable.add(emp);
                    break;
                case "list":
                    hashTable.list();
                    break;
                case "find":
                    System.out.println("input id");
                    int findId = scanner.nextInt();
                    hashTable.findEmpId(findId);
                    break;
                case "exit":
                    scanner.close();
                    System.exit(0);
                    break;
                default:
                    break;
            }
        }
    }
}

class HashTable {
    private EmpLinkedList[] empLinkedListArray;
    private int size;

    public HashTable(int size) {
        this.size = size;
        //it just create the empLinkedListArray and the initial value is null
        //we can't input data in null
        empLinkedListArray = new EmpLinkedList[size];
        //initializing the empLinkedListArray
        for (int i = 0; i < size; i++) {
            empLinkedListArray[i] = new EmpLinkedList();
        }
    }

    public void add(Emp emp) {
        int empLinkedListNo = hashFun(emp.id);
        empLinkedListArray[empLinkedListNo].add(emp);
    }

    public void list() {
        for (int i = 0; i < size; i++) {
            empLinkedListArray[i].list(i);
        }
    }

    public int hashFun(int id) {
        return id % size;
    }

    public void findEmpId(int id) {
        int empLinkedListNo = hashFun(id);
        Emp emp = empLinkedListArray[empLinkedListNo].findEmpById(id);
        if(emp != null){
            System.out.println(emp.toString());
        }else {
            System.out.println("the emp is not in the hashtable");
        }
    }
}

class Emp {
    public int id;
    public String name;
    public Emp next;

    public Emp(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Emp{" +
                "id=" + id +
                ", name='" + name + " }";
    }
}


class EmpLinkedList {
    public Emp head;

    public void add(Emp emp) {
        if (head == null) {
            head = emp;
            return;
        }
        Emp curEmp = head;
        while (true) {
            if (curEmp.next == null) {
                break;
            }
            curEmp = curEmp.next;
        }
        curEmp.next = emp;
    }

    public void list(int no) {
        if (head == null) {
            System.out.println("the " + no + " list is empty");
            return;
        }
        Emp curEmp = head;
        System.out.print("the " + no + " list is: ");
        while (true) {
            System.out.println(curEmp.toString());
            if (curEmp.next == null) {
                break;
            }
            curEmp = curEmp.next;
        }
    }

    public Emp findEmpById(int id) {
        if (head == null) {
            return null;
        }
        Emp curEmp = head;
        while (true) {
            if (curEmp.id == id) {
                break;
            }
            if (curEmp.next == null) {
                return null;
            }
            curEmp = curEmp.next;
        }
        return curEmp;
    }

}

Tree

package com.test.binarytree;

public class BinaryTreeDemo {
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        HeroNode root = new HeroNode(1, "albert");
        HeroNode node2 = new HeroNode(2, "alex");
        HeroNode node3 = new HeroNode(3, "bob");
        HeroNode node4 = new HeroNode(4, "mary");

        root.setLeft(node2);
        root.setRight(node3);
        node3.setRight(node4);

        binaryTree.setRoot(root);

        System.out.println("preOrder: ");
        binaryTree.preOrder();
        System.out.println("infixOrder: ");
        binaryTree.infixOrder();
        System.out.println("preOrder: ");
        binaryTree.postOrder();
    }
}

class HeroNode{
    private int no;
    private String name;
    private HeroNode left;
    private HeroNode right;

    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '/'' +
                '}';
    }

    //preorder traversal
    public void preOrder(){
        System.out.println(this);
        if(this.left != null){
            this.left.preOrder();
        }
        if (this.right != null){
            this.right.preOrder();
        }
    }
    //infixorder traversal
    public void infixOrder (){
        if(this.left != null){
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null){
            this.right.infixOrder();
        }
    }
    //post-order traversal
    public void postOrder(){
        if(this.left != null){
            this.left.postOrder();
        }
        if (this.right != null){
            this.right.postOrder();
        }
        System.out.println(this);
    }

}
//create a binary tree
class BinaryTree{
    private HeroNode root;

    public void setRoot(HeroNode root) {
        this.root = root;
    }

    public void preOrder(){
        if (this.root != null) {
            this.root.preOrder();
        }else {
            System.out.println("the tree is empty");
        }
    }

    public void infixOrder(){
        if (this.root != null) {
            this.root.infixOrder();
        }else {
            System.out.println("the tree is empty");
        }
    }

    public void postOrder(){
        if (this.root != null) {
            this.root.postOrder();
        }else {
            System.out.println("the tree is empty");
        }
    }

}

前中后序查找

package com.test.binarytree;

public class BinaryTreeDemo {
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        HeroNode root = new HeroNode(1, "albert");
        HeroNode node2 = new HeroNode(2, "alex");
        HeroNode node3 = new HeroNode(3, "bob");
        HeroNode node4 = new HeroNode(4, "mary");

        root.setLeft(node2);
        root.setRight(node3);
        node3.setRight(node4);

        binaryTree.setRoot(root);

        System.out.println("preOrder: ");
        binaryTree.preOrder();
        System.out.println("infixOrder: ");
        binaryTree.infixOrder();
        System.out.println("preOrder: ");
        binaryTree.postOrder();

        System.out.println(binaryTree.postOrderSearch(4));
    }
}

class HeroNode{
    private int no;
    private String name;
    private HeroNode left;
    private HeroNode right;

    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '/'' +
                '}';
    }

    //preorder traversal
    public void preOrder(){
        System.out.println(this);
        if(this.left != null){
            this.left.preOrder();
        }
        if (this.right != null){
            this.right.preOrder();
        }
    }
    //infixorder traversal
    public void infixOrder (){
        if(this.left != null){
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null){
            this.right.infixOrder();
        }
    }
    //post-order traversal
    public void postOrder(){
        if(this.left != null){
            this.left.postOrder();
        }
        if (this.right != null){
            this.right.postOrder();
        }
        System.out.println(this);
    }

    public HeroNode preOrderSearch(int no){
        if(this.getNo() == no){
            return this;
        }
        HeroNode heroNode =null;
        if(this.left != null){
            heroNode = this.left.preOrderSearch(no);
        }
        //this statement is very important, it means if the we find the node is a father
        // we can't continue traverse the right sons.
        if(heroNode != null){
            return heroNode;
        }

        if(this.right != null){
            heroNode = this.right.preOrderSearch(no);
        }
        return heroNode;
    }

    public HeroNode infixOrderSearch(int no){
        HeroNode heroNode =null;
        if(this.left != null){
            heroNode = this.left.infixOrderSearch(no);
        }
        //this statement is very important, it means if the we find the node is a father
        // we can't continue traverse the right sons.
        if(heroNode != null){
            return heroNode;
        }

        if(this.getNo() == no){
            return this;
        }
        if(this.right != null){
            heroNode = this.right.infixOrderSearch(no);
        }
        return heroNode;
    }

    public HeroNode postOrderSearch(int no){
        HeroNode heroNode =null;
        if(this.left != null){
            heroNode = this.left.postOrderSearch(no);
        }
        //this statement is very important, it means if the we find the node is a father
        // we can't continue traverse the right sons.
        if(heroNode != null){
            return heroNode;
        }

        if(this.right != null){
            heroNode = this.right.postOrderSearch(no);
        }
        //this statement is very important, it means if the we find the node is a father
        // we can't continue traverse the next node.
        if(heroNode != null){
            return heroNode;
        }


        if(this.getNo() == no){
            return this;
        }
        return heroNode;
    }

}
//create a binary tree
class BinaryTree{
    private HeroNode root;

    public void setRoot(HeroNode root) {
        this.root = root;
    }

    public void preOrder(){
        if (this.root != null) {
            this.root.preOrder();
        }else {
            System.out.println("the tree is empty");
        }
    }

    public void infixOrder(){
        if (this.root != null) {
            this.root.infixOrder();
        }else {
            System.out.println("the tree is empty");
        }
    }

    public void postOrder(){
        if (this.root != null) {
            this.root.postOrder();
        }else {
            System.out.println("the tree is empty");
        }
    }

    public HeroNode preOrderSearch(int no){
        HeroNode heroNode = null;
        if(this.root != null){
            heroNode = this.root.preOrderSearch(no);
        }else {
            System.out.println("the tree is empty");
        }
        return heroNode;
    }

    public HeroNode infixOrderSearch(int no){
        HeroNode heroNode = null;
        if(this.root != null){
            heroNode = this.root.infixOrderSearch(no);
        }else {
            System.out.println("the tree is empty");
        }
        return heroNode;
    }
    public HeroNode postOrderSearch(int no){
        HeroNode heroNode = null;
        if(this.root != null){
            heroNode = this.root.postOrderSearch(no);
        }else {
            System.out.println("the tree is empty");
        }
        return heroNode;
    }



}

删除节点

package com.test.binarytree;

public class BinaryTreeDemo {
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        HeroNode root = new HeroNode(1, "albert");
        HeroNode node2 = new HeroNode(2, "alex");
        HeroNode node3 = new HeroNode(3, "bob");
        HeroNode node4 = new HeroNode(4, "mary");
        HeroNode node5 = new HeroNode(5, "elon");

        root.setLeft(node2);
        root.setRight(node3);
        node3.setRight(node4);
        node3.setLeft(node5);

        binaryTree.setRoot(root);
//
//        System.out.println("preOrder: ");
//        binaryTree.preOrder();
//        System.out.println("infixOrder: ");
//        binaryTree.infixOrder();
//        System.out.println("preOrder: ");
//        binaryTree.postOrder();
//
//        System.out.println(binaryTree.postOrderSearch(4));

        System.out.println("preOrder");
        binaryTree.preOrder();
        binaryTree.deleteNode(10);
        System.out.println("preOrder");
        binaryTree.preOrder();

    }
}

class HeroNode {
    private int no;
    private String name;
    private HeroNode left;
    private HeroNode right;

    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '/'' +
                '}';
    }

    //preorder traversal
    public void preOrder() {
        System.out.println(this);
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    //infixorder traversal
    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.infixOrder();
        }
    }

    //post-order traversal
    public void postOrder() {
        if (this.left != null) {
            this.left.postOrder();
        }
        if (this.right != null) {
            this.right.postOrder();
        }
        System.out.println(this);
    }

    public HeroNode preOrderSearch(int no) {
        if (this.getNo() == no) {
            return this;
        }
        HeroNode heroNode = null;
        if (this.left != null) {
            heroNode = this.left.preOrderSearch(no);
        }
        //this statement is very important, it means if the we find the node is a father
        // we can't continue traverse the right sons.
        if (heroNode != null) {
            return heroNode;
        }

        if (this.right != null) {
            heroNode = this.right.preOrderSearch(no);
        }
        return heroNode;
    }

    public HeroNode infixOrderSearch(int no) {
        HeroNode heroNode = null;
        if (this.left != null) {
            heroNode = this.left.infixOrderSearch(no);
        }
        //this statement is very important, it means if the we find the node is a father
        // we can't continue traverse the right sons.
        if (heroNode != null) {
            return heroNode;
        }

        if (this.getNo() == no) {
            return this;
        }
        if (this.right != null) {
            heroNode = this.right.infixOrderSearch(no);
        }
        return heroNode;
    }

    public HeroNode postOrderSearch(int no) {
        HeroNode heroNode = null;
        if (this.left != null) {
            heroNode = this.left.postOrderSearch(no);
        }
        //this statement is very important, it means if the we find the node is a father
        // we can't continue traverse the right sons.
        if (heroNode != null) {
            return heroNode;
        }

        if (this.right != null) {
            heroNode = this.right.postOrderSearch(no);
        }
        //this statement is very important, it means if the we find the node is a father
        // we can't continue traverse the next node.
        if (heroNode != null) {
            return heroNode;
        }


        if (this.getNo() == no) {
            return this;
        }
        return heroNode;
    }

    public void deleteNode(int no) {
        if(this.left != null && this.left.getNo() == no){
            this.left = null;
            return;
        }
        if(this.right != null && this.right.getNo() == no){
            this.right = null;
            return;
        }
        if(this.left != null && this.left.getNo() != no){
            this.left.deleteNode(no);
        }
        if(this.right != null && this.right.getNo() != no){
            this.right.deleteNode(no);
        }
    }

}

//create a binary tree
class BinaryTree {
    private HeroNode root;

    public void setRoot(HeroNode root) {
        this.root = root;
    }

    public void preOrder() {
        if (this.root != null) {
            this.root.preOrder();
        } else {
            System.out.println("the tree is empty");
        }
    }

    public void infixOrder() {
        if (this.root != null) {
            this.root.infixOrder();
        } else {
            System.out.println("the tree is empty");
        }
    }

    public void postOrder() {
        if (this.root != null) {
            this.root.postOrder();
        } else {
            System.out.println("the tree is empty");
        }
    }

    public HeroNode preOrderSearch(int no) {
        HeroNode heroNode = null;
        if (this.root != null) {
            heroNode = this.root.preOrderSearch(no);
        } else {
            System.out.println("the tree is empty");
        }
        return heroNode;
    }

    public HeroNode infixOrderSearch(int no) {
        HeroNode heroNode = null;
        if (this.root != null) {
            heroNode = this.root.infixOrderSearch(no);
        } else {
            System.out.println("the tree is empty");
        }
        return heroNode;
    }

    public HeroNode postOrderSearch(int no) {
        HeroNode heroNode = null;
        if (this.root != null) {
            heroNode = this.root.postOrderSearch(no);
        } else {
            System.out.println("the tree is empty");
        }
        return heroNode;
    }

    //if the node is a left, deleting the left, if it is a father node or root, deleting the sub-tree or tree
    public void deleteNode(int no) {
        if (this.root.getNo() == no) {
            this.root = null;
        }else {
            this.root.deleteNode(no);
        }

    }

}

package com.test.binarytree;

public class BinaryTreeDemo {
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        HeroNode root = new HeroNode(1, "albert");
        HeroNode node2 = new HeroNode(2, "alex");
        HeroNode node3 = new HeroNode(3, "bob");
        HeroNode node4 = new HeroNode(4, "mary");
        HeroNode node5 = new HeroNode(5, "elon");

        root.setLeft(node2);
        root.setRight(node3);
        node3.setRight(node4);
        node3.setLeft(node5);

        binaryTree.setRoot(root);
//
//        System.out.println("preOrder: ");
//        binaryTree.preOrder();
//        System.out.println("infixOrder: ");
//        binaryTree.infixOrder();
//        System.out.println("preOrder: ");
//        binaryTree.postOrder();
//
//        System.out.println(binaryTree.postOrderSearch(4));

        System.out.println("preOrder");
        binaryTree.preOrder();
        binaryTree.deleteNode(3);
        System.out.println("preOrder");
        binaryTree.preOrder();

    }
}

class HeroNode {
    private int no;
    private String name;
    private HeroNode left;
    private HeroNode right;

    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '/'' +
                '}';
    }

    //preorder traversal
    public void preOrder() {
        System.out.println(this);
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    //infixorder traversal
    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.infixOrder();
        }
    }

    //post-order traversal
    public void postOrder() {
        if (this.left != null) {
            this.left.postOrder();
        }
        if (this.right != null) {
            this.right.postOrder();
        }
        System.out.println(this);
    }

    public HeroNode preOrderSearch(int no) {
        if (this.getNo() == no) {
            return this;
        }
        HeroNode heroNode = null;
        if (this.left != null) {
            heroNode = this.left.preOrderSearch(no);
        }
        //this statement is very important, it means if the we find the node is a father
        // we can't continue traverse the right sons.
        if (heroNode != null) {
            return heroNode;
        }

        if (this.right != null) {
            heroNode = this.right.preOrderSearch(no);
        }
        return heroNode;
    }

    public HeroNode infixOrderSearch(int no) {
        HeroNode heroNode = null;
        if (this.left != null) {
            heroNode = this.left.infixOrderSearch(no);
        }
        //this statement is very important, it means if the we find the node is a father
        // we can't continue traverse the right sons.
        if (heroNode != null) {
            return heroNode;
        }

        if (this.getNo() == no) {
            return this;
        }
        if (this.right != null) {
            heroNode = this.right.infixOrderSearch(no);
        }
        return heroNode;
    }

    public HeroNode postOrderSearch(int no) {
        HeroNode heroNode = null;
        if (this.left != null) {
            heroNode = this.left.postOrderSearch(no);
        }
        //this statement is very important, it means if the we find the node is a father
        // we can't continue traverse the right sons.
        if (heroNode != null) {
            return heroNode;
        }

        if (this.right != null) {
            heroNode = this.right.postOrderSearch(no);
        }
        //this statement is very important, it means if the we find the node is a father
        // we can't continue traverse the next node.
        if (heroNode != null) {
            return heroNode;
        }


        if (this.getNo() == no) {
            return this;
        }
        return heroNode;
    }

    public void deleteNode(int no) {
        if(this.left != null && this.left.getNo() == no){
            HeroNode heroNode1 = this.left.left;
            HeroNode heroNode2 = this.left.right;
            if(heroNode1 != null){
                this.left = heroNode1;
                heroNode1.right = heroNode2;
            } else if(heroNode2 != null){
                this.left = heroNode2;
            } else {
                this.left = null;
            }

        }
        if(this.right != null && this.right.getNo() == no){
            HeroNode heroNode1 = this.right.left;
            HeroNode heroNode2 = this.right.right;
            if(heroNode1 != null){
                this.right = heroNode1;
                heroNode1.right = heroNode2;
            } else if(heroNode2 != null){
                this.right = heroNode2;
            } else {
                this.right = null;
            }
            return;
        }
        if(this.left != null && this.left.getNo() != no){
            this.left.deleteNode(no);
        }
        if(this.right != null && this.right.getNo() != no){
            this.right.deleteNode(no);
        }
    }

}

//create a binary tree
class BinaryTree {
    private HeroNode root;

    public void setRoot(HeroNode root) {
        this.root = root;
    }

    public void preOrder() {
        if (this.root != null) {
            this.root.preOrder();
        } else {
            System.out.println("the tree is empty");
        }
    }

    public void infixOrder() {
        if (this.root != null) {
            this.root.infixOrder();
        } else {
            System.out.println("the tree is empty");
        }
    }

    public void postOrder() {
        if (this.root != null) {
            this.root.postOrder();
        } else {
            System.out.println("the tree is empty");
        }
    }

    public HeroNode preOrderSearch(int no) {
        HeroNode heroNode = null;
        if (this.root != null) {
            heroNode = this.root.preOrderSearch(no);
        } else {
            System.out.println("the tree is empty");
        }
        return heroNode;
    }

    public HeroNode infixOrderSearch(int no) {
        HeroNode heroNode = null;
        if (this.root != null) {
            heroNode = this.root.infixOrderSearch(no);
        } else {
            System.out.println("the tree is empty");
        }
        return heroNode;
    }

    public HeroNode postOrderSearch(int no) {
        HeroNode heroNode = null;
        if (this.root != null) {
            heroNode = this.root.postOrderSearch(no);
        } else {
            System.out.println("the tree is empty");
        }
        return heroNode;
    }

    //if the node is a left, deleting the left, if it is a father node or root, deleting the sub-tree or tree
    public void deleteNode(int no) {
        if (this.root.getNo() == no) {
            this.root = null;
        }else {
            this.root.deleteNode(no);
        }

    }

}

顺序存储二叉树

package com.test.binarytree;

public class ArrBinaryTreeDemo {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7};
        ArrBinaryTree arrBinaryTree = new ArrBinaryTree();
        arrBinaryTree.preOrder(arr, 0);
        System.out.println("==========");
        arrBinaryTree.infixOrder(arr, 0);
        System.out.println("==========");
        arrBinaryTree.postOrder(arr, 0);
    }
}

class ArrBinaryTree {
    public void preOrder(int[] arr, int index) {
        if (arr.length == 0 || arr == null) {
            System.out.println("array is empty");
            return;
        }
        System.out.println(arr[index]);
        if (2 * index + 1 < arr.length) {
            preOrder(arr, 2 * index + 1);
        }
        if (2 * index + 2 < arr.length) {
            preOrder(arr, 2 * index + 2);
        }
    }

    public void infixOrder(int[] arr, int index) {
        if (arr.length == 0 || arr == null) {
            System.out.println("array is empty");
            return;
        }
        if (2 * index + 1 < arr.length) {
            infixOrder(arr, 2 * index + 1);
        }
        System.out.println(arr[index]);
        if (2 * index + 2 < arr.length) {
            infixOrder(arr, 2 * index + 2);
        }
    }

    public void postOrder(int[] arr, int index) {
        if (arr.length == 0 || arr == null) {
            System.out.println("array is empty");
            return;
        }
        if (2 * index + 1 < arr.length) {
            postOrder(arr, 2 * index + 1);
        }
        if (2 * index + 2 < arr.length) {
            postOrder(arr, 2 * index + 2);
        }
        System.out.println(arr[index]);
    }
}

线索化二叉树

构建

package com.test.binarytree;

public class ThreadedBinaryTreeDemo {
    public static void main(String[] args) {

        Node a = new Node(1, "a");
        Node b = new Node(3, "a");
        Node c = new Node(6, "a");
        Node d = new Node(8, "a");
        Node e = new Node(10, "a");
        Node f = new Node(14, "a");

        ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
        threadedBinaryTree.setRoot(a);
        a.setLeft(b);
        a.setRight(c);
        b.setLeft(d);
        b.setRight(e);
        c.setLeft(f);

        threadedBinaryTree.threadedNode();
        System.out.println(e.getLeft());
        System.out.println(e.getRight());

    }
}

class Node {
    private int no;
    private String name;
    private Node left;
    private Node right;

    //if it is 1, the left is the front-node
    private int leftType;
    private int RightType;

    public int getLeftType() {
        return leftType;
    }

    public void setLeftType(int leftType) {
        this.leftType = leftType;
    }

    public int getRightType() {
        return RightType;
    }

    public void setRightType(int rightType) {
        RightType = rightType;
    }

    public Node(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                ", name='" + name + '/'' +
                '}';
    }

    //preorder traversal
    public void preOrder() {
        System.out.println(this);
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    //infixorder traversal
    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.infixOrder();
        }
    }

    //post-order traversal
    public void postOrder() {
        if (this.left != null) {
            this.left.postOrder();
        }
        if (this.right != null) {
            this.right.postOrder();
        }
        System.out.println(this);
    }
}

//create a binary tree
class ThreadedBinaryTree {
    private Node root;

    private Node pre;

    public void threadedNode(){
        threadedNode(root);
    }

    public void threadedNode(Node node){
        if(node == null){
            return;
        }
        threadedNode(node.getLeft());
        if(node.getLeft() == null){
            node.setLeft(pre);
            node.setLeftType(1);
        }
        if(pre != null && pre.getRight() == null){
            pre.setRight(node);
            pre.setRightType(1);
        }
        pre = node;
        threadedNode(node.getRight());
    }

    public void setRoot(Node root) {
        this.root = root;
    }

    public void preOrder() {
        if (this.root != null) {
            this.root.preOrder();
        } else {
            System.out.println("the tree is empty");
        }
    }

    public void infixOrder() {
        if (this.root != null) {
            this.root.infixOrder();
        } else {
            System.out.println("the tree is empty");
        }
    }

    public void postOrder() {
        if (this.root != null) {
            this.root.postOrder();
        } else {
            System.out.println("the tree is empty");
        }
    }
}

遍历

编写思路：

确定它是哪种遍历，如中序遍历
每次输出前都要找到当前子树的左叶子节点
然后输出
如果当前的节点有后继节点，循环输出后继节点
没有，则将右子节点设为当前节点

package com.test.binarytree;

public class ThreadedBinaryTreeDemo {
    public static void main(String[] args) {

        Node a = new Node(1, "a");
        Node b = new Node(3, "a");
        Node c = new Node(6, "a");
        Node d = new Node(8, "a");
        Node e = new Node(10, "a");
        Node f = new Node(14, "a");

        ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
        threadedBinaryTree.setRoot(a);
        a.setLeft(b);
        a.setRight(c);
        b.setLeft(d);
        b.setRight(e);
        c.setLeft(f);

        threadedBinaryTree.threadedNode();
        System.out.println(e.getLeft());
        System.out.println(e.getRight());
        threadedBinaryTree.threadedList();

    }
}

class Node {
    private int no;
    private String name;
    private Node left;
    private Node right;

    //if it is 1, the left is the front-node
    private int leftType;
    private int RightType;

    public int getLeftType() {
        return leftType;
    }

    public void setLeftType(int leftType) {
        this.leftType = leftType;
    }

    public int getRightType() {
        return RightType;
    }

    public void setRightType(int rightType) {
        RightType = rightType;
    }

    public Node(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                ", name='" + name + '/'' +
                '}';
    }

    //preorder traversal
    public void preOrder() {
        System.out.println(this);
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    //infixorder traversal
    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.infixOrder();
        }
    }

    //post-order traversal
    public void postOrder() {
        if (this.left != null) {
            this.left.postOrder();
        }
        if (this.right != null) {
            this.right.postOrder();
        }
        System.out.println(this);
    }
}

//create a binary tree
class ThreadedBinaryTree {
    private Node root;

    private Node pre;

    private boolean haveThreaded = false;

    public void setRoot(Node root) {
        this.root = root;
    }

    public void threadedNode() {
        threadedNode(root);
        haveThreaded = true;
    }

    public void threadedNode(Node node) {
        if (node == null) {
            return;
        }
        threadedNode(node.getLeft());
        if (node.getLeft() == null) {
            node.setLeft(pre);
            node.setLeftType(1);
        }
        if (pre != null && pre.getRight() == null) {
            pre.setRight(node);
            pre.setRightType(1);
        }
        pre = node;
        threadedNode(node.getRight());
    }

    public void threadedList() {
        if (haveThreaded == false) {
            System.out.println("it hasn't threaded");
            return;
        }
        if (root == null) {
            System.out.println("tree is empty");
            return;
        }
        Node tmpNode = null;
        tmpNode = root;
        while (tmpNode != null){

            //find the left node
            while (tmpNode.getLeftType() == 0){
                tmpNode = tmpNode.getLeft();
            }

            System.out.println(tmpNode);
            //print right
            while (tmpNode.getRightType() == 1){
                tmpNode = tmpNode.getRight();
                System.out.println(tmpNode);
            }
            tmpNode = tmpNode.getRight();

        }

    }


    public void preOrder() {
        if (this.root != null) {
            this.root.preOrder();
        } else {
            System.out.println("the tree is empty");
        }
    }

    public void infixOrder() {
        if (this.root != null) {
            this.root.infixOrder();
        } else {
            System.out.println("the tree is empty");
        }
    }

    public void postOrder() {
        if (this.root != null) {
            this.root.postOrder();
        } else {
            System.out.println("the tree is empty");
        }
    }
}

堆排序

编写思路：

根据需求先变成大顶堆还是小顶堆。
对树中数据的处理是从左至右，从下至上
先编写对 i 节点的子树的处理，先比较其左右字节的，如果是大顶堆，让大的子节点与 i 节点比较,并交换
对与完全二叉树层数和节点的关系是 n = 2^(l-1)-1 + m；l：层数；m：最后一层的节点数 n: 节点数
如果节点有10个， l = 4, 从倒数第二层开始处理子树数据则 i 节点 = 10/2 -1
处理完之后从数中 pop 出根节点（与最后一个叶节点交换）
然后从顶部开始重新整理数，因为每次只 pop 一个根节点，只有一个数据发生了变化，所以可以从顶部直接循环，即如果和左子节点交换，右子节点为父节点的子树一定是有序的。

package com.test.binarytree;

import java.util.Arrays;

public class HeapSort {

    public static void main(String[] args) {
        int arr[] = {4, 6, 8, 5, 9};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void heapSort(int[] arr) {
        int tmp = 0;
        //to adjust the tree to the big top heap
        for (int i = arr.length/2-1; i >=0 ; i--) {
            adjustHeap(arr,i, arr.length);
        }

        //pop the root
        for (int i = arr.length-1; i >0 ; i--) {
            tmp = arr[i];
            arr[i] = arr[0];
            arr[0] = tmp;
            adjustHeap(arr,0, i);
        }
    }

    /**
     * The method is to adjust the sub-tree of node i
     *
     * @param arr    the array needs to be adjust
     * @param i      the index of non-leaf node
     * @param length the number of nodes need to be adjust
     */
    public static void adjustHeap(int[] arr, int i, int length) {
        int tmp = arr[i];
        //k: left son node
        for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
            //for improve the efficiency
            if (k + 1 < length && arr[k] < arr[k + 1]) {
                k++;
            }
            if (arr[k] > tmp){
                arr[i] = arr[k];
                i = k;
            }else {
                break;
            }
        }
        arr[i] = tmp;
    }
}

赫夫曼树

到 13 节点的路径长度是 2，带权路径长度是 2*13 = 26

编写思路：

对节点排序，如果使用集合的排序方法（Collections.sort(para)）需要实现Comparable 接口中的compareTo 方法
每次操作前先排序
每次生成子树所使用的节点需要从List 中删除并将其父节点放入 list

package com.test.huffmantree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class HuffmanTree {
    public static void main(String[] args) {
        int[] arr = {13, 7, 8, 3, 29, 6, 1};
        Node root = createHuffmanTree(arr);
        preOrderTree(root);
    }
    public static void preOrderTree(Node root){
        if(root == null){
            System.out.println("Tree is empty");
            return;
        }
        root.preOrder();
    }

    public static Node createHuffmanTree(int[] arr){
        List<Node> nodes = new ArrayList<>();
        for (int value : arr) {
            nodes.add(new Node(value));
        }

        while (true) {
            if(nodes.size() == 1){
                break;
            }
            Collections.sort(nodes);
            Node leftNode = nodes.get(0);
            Node rightNode = nodes.get(1);
            //create a new tree
            Node parent = new Node(leftNode.getValue() + rightNode.getValue());
            parent.setLeft(leftNode);
            parent.setRight(rightNode);
            //delete nodes have been done
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            nodes.add(parent);

        }
        return nodes.get(0);
    }
}

class Node implements Comparable<Node> {
    private int value;
    private Node left;
    private Node right;

    public Node(int value) {
        this.value = value;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }

    @Override
    public int compareTo(Node o) {
        //from lower to bigger
        return this.value - o.value;
    }

    //preOrder traverse
    public void preOrder(){
        System.out.println(this);
        if(this.left != null){
            this.left.preOrder();
        }
        if(this.right != null){
            this.right.preOrder();
        }
    }
}

赫夫曼编码

数据压缩

package com.test.HuffmanCode;

import java.io.*;
import java.nio.CharBuffer;
import java.util.*;

public class HuffmanCode {
    public static void main(String[] args) {

        //String srcFile = "input/123.jpg";
        //String dstFile = "input/zip123.zip";
        //(srcFile, dstFile);
        String zipFile = "input/zip123.zip";
        String dstFile = "input/456.jpg";
        unZipFile(zipFile,dstFile);

        /*
        String content = "i like like like java do you like a java";
        //System.out.println(Arrays.toString(huffmanZip(content)));
        byte[] contentBytes = content.getBytes();
        byte[] huffmanBytes = huffmanZip(contentBytes);
        byte[] decode = decode(huffmanCodes, huffmanBytes);
        for (byte b : decode) {
            System.out.print((char) (int) b);
        }

         */
    }

    public static void unZipFile(String zipFile, String dstFile) {
        InputStream is = null;
        ObjectInputStream ois = null;
        OutputStream os = null;

        try {
            is = new FileInputStream(zipFile);
            ois = new ObjectInputStream(is);
            //read huffmanBytes
            byte[] huffmanBytes = (byte[]) ois.readObject();
            //read huffmanCode
            Map<Byte, String> huffmanCode = (Map<Byte, String>) ois.readObject();

            byte[] decode = decode(huffmanCode, huffmanBytes);

            os = new FileOutputStream(dstFile);

            os.write(decode);


        } catch (Exception e) {
            e.printStackTrace();
        } finally {
            try {
                os.close();
                ois.close();
                is.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }

    /**
     * encode a file
     *
     * @param srcFile path of source file
     * @param dstFile path of finished zipped file
     */
    public static void zipFile(String srcFile, String dstFile) {
        FileInputStream fis = null;
        FileOutputStream fos = null;
        ObjectOutputStream oos = null;
        try {
            fis = new FileInputStream(srcFile);
            //create type array, fis.available(): size of file
            byte[] b = new byte[fis.available()];
            fis.read(b);
            byte[] huffmanBytes = huffmanZip(b);
            //create a output stream
            fos = new FileOutputStream(dstFile);
            oos = new ObjectOutputStream(fos);
            oos.writeObject(huffmanBytes);

            //write the code into the file
            oos.writeObject(huffmanCodes);

        } catch (Exception e) {
            e.printStackTrace();
        } finally {
            try {
                fis.close();
                oos.close();
                fos.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }


    //decompression
    //1. translate huffman Zip to huffman code string
    //2. translate string to initial string

    /**
     * @param huffmanCode  huffman code table
     * @param huffmanBytes huffman Zip
     * @return
     */
    private static byte[] decode(Map<Byte, String> huffmanCode, byte[] huffmanBytes) {
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < huffmanBytes.length; i++) {
            boolean flag = !(i == huffmanBytes.length - 1);
            stringBuilder.append(byteToBitString(flag, huffmanBytes[i]));
        }
        //To swap the key and value of huffman code for quickly querying find value
        HashMap<String, Byte> deHuffman = new HashMap<>();
        for (Map.Entry<Byte, String> entry : huffmanCode.entrySet()) {
            deHuffman.put(entry.getValue(), entry.getKey());
        }

        ArrayList<Byte> list = new ArrayList<>();
        int i = 0;
        while (i < stringBuilder.length()) {
            int index = 1; // for scan a completed number, such as 111
            boolean flag = true;
            Byte tmp = null;

            while (flag) {
                String key = stringBuilder.substring(i, i + index);
                tmp = deHuffman.get(key);
                if (tmp != null) {
                    list.add(tmp);
                    i += index;
                    break;
                } else {
                    index++;
                }
            }
        }
        byte[] initialBytes = new byte[list.size()];
        for (int j = 0; j < list.size(); j++) {
            initialBytes[j] = list.get(j);
        }
        return initialBytes;

    }

    private static String byteToBitString(boolean flag, byte b) {
        int tmp = b; // translate b to int
        //if it is not the last number
        if (flag) {
            tmp |= 256; //bitwise OR 256 1 0000 0000 | 0000 0001 = 1 0000 0001
        }
        //System.out.println(tmp);
        String str = Integer.toBinaryString(tmp); //translate tmp into binary complement
        if (flag || tmp < 0) {
            return str.substring(str.length() - 8);
        } else {
            return str;
        }
    }


    //To seal the huffman code zip
    private static byte[] huffmanZip(byte[] contentBytes) {

        //put the contentBytes into a list
        List<Node> nodes = getNodes(contentBytes);

        //transform the list to a huffman tree
        Node root = createHuffmanTree(nodes);

        //get the huffman code
        HashMap<Byte, String> huffmanCode = getCode(root);

        //return the zip string translated by huffman code
        return zip(contentBytes, huffmanCode);
    }

    /**
     * to translate the string to zip code
     *
     * @param bytes       the initial byte of string
     * @param huffmanCode the huffman code
     * @return the huffman code of the initial string
     * 10101000....
     * put 8 bits in a byte huffmanCodeBytes[0] = 10101000 -> -88
     */
    private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCode) {
        //1. translate huffmanCode to huffman string
        StringBuilder stringBuilder = new StringBuilder();
        for (byte b : bytes) {
            stringBuilder.append(huffmanCode.get(b));
        }

        //to calculate the number of huffmanCodeBytes
        int len;
        if (stringBuilder.length() % 8 == 0) {
            len = stringBuilder.length() / 8;
        } else {
            len = stringBuilder.length() / 8 + 1;
        }

        //
        byte[] huffmanCodeBytes = new byte[len];
        int index = 0;
        for (int i = 0; i < stringBuilder.length(); i += 8) {
            String strByte;
            if (i + 8 > stringBuilder.length()) {
                strByte = stringBuilder.substring(i);
            } else {
                strByte = stringBuilder.substring(i, i + 8);
            }
            huffmanCodeBytes[index] = (byte) Integer.parseInt(strByte, 2);
            index++;
        }
        return huffmanCodeBytes;
    }

    //To generate Huffman code
    //1. put huffman code in a map Map<Byte, String> 32->01...
    //2. using a StringBuilder to store path of leaf
    static HashMap<Byte, String> huffmanCodes = new HashMap<>();
    static StringBuilder stringBuilder = new StringBuilder();

    public static HashMap<Byte, String> getCode(Node root) {
        if (root == null) {
            System.out.println("The tree is empty");
        }
        getCode(root, "", stringBuilder);
        return huffmanCodes;
    }

    /**
     * transform the leaves to huffman code in a map
     *
     * @param node          the input node
     * @param code          path: left node: 0 ,right node: 1
     * @param stringBuilder combine path
     */
    private static void getCode(Node node, String code, StringBuilder stringBuilder) {
        StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
        stringBuilder2.append(code);
        if (node != null) {
            //node is non-leaf node
            if (node.data == null) {
                //recursion left
                getCode(node.left, "0", stringBuilder2);
                //recursion right
                getCode(node.right, "1", stringBuilder2);
            } else {
                huffmanCodes.put(node.data, stringBuilder2.toString());
            }
        }
    }


    private static void preOrderTree(Node root) {
        if (root == null) {
            System.out.println("the Tree is empty");
            return;
        }
        root.preOrder();
    }

    private static Node createHuffmanTree(List<Node> nodes) {
        while (true) {
            if (nodes.size() == 1) {
                break;
            }
            nodes.sort((node1, node2) -> {
                return node1.weight - node2.weight;
            });
            Node leftNode = nodes.get(0);
            Node rightNode = nodes.get(1);
            Node parent = new Node(null, leftNode.weight + rightNode.weight);
            parent.left = leftNode;
            parent.right = rightNode;
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            nodes.add(parent);
        }
        return nodes.get(0);
    }

    private static List<Node> getNodes(byte[] bytes) {
        List<Node> nodes = new ArrayList<>();
        //using map to store each number of char
        Map<Byte, Integer> counts = new HashMap<>();
        for (byte b : bytes) {
            Integer count = counts.get(b);
            if (count == null) {
                counts.put(b, 1);
            } else {
                counts.put(b, count + 1);
            }
        }
        for (Map.Entry<Byte, Integer> entry : counts.entrySet()) {
            nodes.add(new Node(entry.getKey(), entry.getValue()));
        }
        return nodes;
    }
}

//class Node implements Comparable<Node>
class Node {
    Byte data; // store data 'a' => 97
    int weight; // number of char
    Node left;
    Node right;

    public Node(Byte data, int weight) {
        this.data = data;
        this.weight = weight;
    }


//    @Override
//    public int compareTo(Node o) {
//        return this.weight - o.weight;
//    }

    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                ", weight=" + weight +
                '}';
    }

    public void preOrder() {
        System.out.println(this);
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }
}

小节（注意事项)

二叉排序树

package com.test.binarysorttree;

public class BinarySortTreeDemo {
    public static void main(String[] args) {
        int[] arr = {7, 3, 10, 12, 5, 1, 9};
        BinarySortTree bsTree = new BinarySortTree();
        for (int i : arr) {
            bsTree.add(new Node(i));
        }
        bsTree.infixOrder();
    }
}

class BinarySortTree {
    private Node root;


    public void add(Node node) {
        if (node == null) {
            return;
        }
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }

    }

    public void infixOrder() {
        if (root == null) {
            return;
        }
        root.infixOrder();
    }
}


class Node {
    private int value;
    private Node left;
    private Node right;

    public Node(int value) {
        this.value = value;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }

    public void add(Node node) {
        if (node == null) {
            return;
        }
        if (node.value < this.value) {
            if (this.left == null) {
                this.left = node;
            } else {
                this.left.add(node);
            }
        } else {
            if (this.right == null) {
                this.right = node;
            } else {
                this.right.add(node);
            }
        }
    }

    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.infixOrder();
        }
    }
}

删除节点

package com.test.binarysorttree;

public class BinarySortTreeDemo {
    public static void main(String[] args) {
        int[] arr = {7, 3, 10, 12, 5, 1, 9, 2};
        BinarySortTree bsTree = new BinarySortTree();
        for (int i : arr) {
            bsTree.add(new Node(i));
        }
        bsTree.infixOrder();
        System.out.println("============");
        bsTree.delNode(2);
        bsTree.delNode(5);
        bsTree.delNode(9);
        bsTree.delNode(12);
        bsTree.delNode(7);
        bsTree.delNode(3);
        bsTree.delNode(10);
        bsTree.delNode(1);

        bsTree.infixOrder();
        bsTree.getRoot();
    }
}

class BinarySortTree {
    private Node root;

    public Node getRoot() {
        return root;
    }

    public void add(Node node) {
        if (node == null) {
            return;
        }
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }

    }

    public void infixOrder() {
        if (root == null) {
            return;
        }
        root.infixOrder();
    }

    public Node search(int value) {
        if (root == null) {
            return null;
        } else {
            return root.search(value);
        }
    }

    public Node searchParent(int value) {
        if (root == null) {
            return null;
        } else {
            return root.searchParent(value);
        }
    }

    public void delNode(int value) {
        if (root == null) {
            return;
        } else {
            Node targetNode = search(value);
            if (targetNode == null) {
                return;
            }
            if (root.getLeft() == null && root.getRight() == null) {
                if (root.getValue() == value) {
                    root = null;
                }
                return;
            }

            //To find parent node of target node
            Node parentNode = searchParent(value);

            //if the target node is leaf node
            if (targetNode.getLeft() == null && targetNode.getRight() == null) {
                if (parentNode.getLeft() != null &&
                        parentNode.getLeft().getValue() == value) {
                    parentNode.setLeft(null);
                } else if (parentNode.getRight() != null &&
                        parentNode.getRight().getValue() == value) {
                    parentNode.setRight(null);
                }

                //if the target node has two sub-trees
            } else if (targetNode.getLeft() != null &&
                    targetNode.getRight() != null) {
                int minValue = delRightTreeMin(targetNode.getRight());
                targetNode.setValue(minValue);


                //if the target node has one sub-tree
            } else {
                //if target node have left node
                if (targetNode.getLeft() != null) {
                    //need to consider the parent node is null
                    if(parentNode != null){
                        //if target node is the left node of parent node
                        if (parentNode.getLeft().getValue() == value) {
                            parentNode.setLeft(targetNode.getLeft());
                        }
                        //if target node is the right node of parent node
                        else {
                            parentNode.setRight(targetNode.getLeft());
                        }
                    }else {
                        root = targetNode.getLeft();
                    }

                } else {//if target node have right node
                    //if target node is the left node of parent node
                    //need to consider the parent node is null
                    if(parentNode != null){
                        if (parentNode.getLeft().getValue() == value) {
                            parentNode.setLeft(targetNode.getRight());
                        }
                        //if target node is the right node of parent node
                        else {
                            parentNode.setRight(targetNode.getRight());
                        }
                    }else {
                        root = targetNode.getRight();
                    }

                }
            }
        }

    }


    //To find the min value of the right sub-tree
    //return the min value to give the target node
    //delete the min node
    public int delRightTreeMin(Node node) {
        Node tmp = node;
        //
        while (tmp.getLeft() != null) {
            tmp = tmp.getLeft();
        }
        delNode(tmp.getValue());
        return tmp.getValue();
    }
}


class Node {
    private int value;
    private Node left;
    private Node right;

    public Node(int value) {
        this.value = value;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }

    public void add(Node node) {
        if (node == null) {
            return;
        }
        if (node.value < this.value) {
            if (this.left == null) {
                this.left = node;
            } else {
                this.left.add(node);
            }
        } else {
            if (this.right == null) {
                this.right = node;
            } else {
                this.right.add(node);
            }
        }
    }

    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.infixOrder();
        }
    }

    //To find the node needed to be deleted
    public Node search(int value) {
        if (value == this.value) {
            return this;
        } else if (value < this.value) {
            if (this.left == null) {
                return null;
            }
            return this.left.search(value);
        } else {
            if (this.right == null) {
                return null;
            }
            return this.right.search(value);
        }
    }

    //To find the parent node of the node needed to be deleted
    // value: for searching
    public Node searchParent(int value) {
        if ((this.left != null && this.left.value == value) ||
                (this.right != null && this.right.value == value)) {
            return this;
        } else {
            if (value < this.value && this.left != null) {
                return this.left.searchParent(value);
            } else if (value >= this.value && this.right != null) {
                return this.right.searchParent(value);
            } else {
                return null;
            }
        }
    }
}

平衡二叉树 AVL 树

左旋转

package com.test.avl;

public class AvlTreeDemo {
    public static void main(String[] args) {
        int[] arr = {4, 3, 6, 5, 7, 8};
        AvlTree avlTree = new AvlTree();
        for (int i : arr) {
            avlTree.add(new Node(i));
        }
        avlTree.infixOrder();
        System.out.println("The height of tree: " + avlTree.getRoot().height());
        System.out.println("The height of left sub-tree: " + avlTree.getRoot().getLeft().height());
        System.out.println("The height of right sub-tree: " + avlTree.getRoot().getRight().height());
        System.out.println("balance:");
//        avlTree.getRoot().leftRotate();
//        avlTree.infixOrder();
//        System.out.println("The height of tree: " + avlTree.getRoot().height());
//        System.out.println("The height of left sub-tree: " + avlTree.getRoot().getLeft().height());
//        System.out.println("The height of right sub-tree: " + avlTree.getRoot().getRight().height());
    }
}

class AvlTree {

    private Node root;

    public Node getRoot() {
        return root;
    }

    public void add(Node node) {
        if (node == null) {
            return;
        }
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }

    }

    public void infixOrder() {
        if (root == null) {
            return;
        }
        root.infixOrder();
    }

    public Node search(int value) {
        if (root == null) {
            return null;
        } else {
            return root.search(value);
        }
    }

    public Node searchParent(int value) {
        if (root == null) {
            return null;
        } else {
            return root.searchParent(value);
        }
    }

    public void delNode(int value) {
        if (root == null) {
            return;
        } else {
            Node targetNode = search(value);
            if (targetNode == null) {
                return;
            }
            if (root.getLeft() == null && root.getRight() == null) {
                if (root.getValue() == value) {
                    root = null;
                }
                return;
            }

            //To find parent node of target node
            Node parentNode = searchParent(value);

            //if the target node is leaf node
            if (targetNode.getLeft() == null && targetNode.getRight() == null) {
                if (parentNode.getLeft() != null &&
                        parentNode.getLeft().getValue() == value) {
                    parentNode.setLeft(null);
                } else if (parentNode.getRight() != null &&
                        parentNode.getRight().getValue() == value) {
                    parentNode.setRight(null);
                }

                //if the target node has two sub-trees
            } else if (targetNode.getLeft() != null &&
                    targetNode.getRight() != null) {
                int minValue = delRightTreeMin(targetNode.getRight());
                targetNode.setValue(minValue);


                //if the target node has one sub-tree
            } else {
                //if target node have left node
                if (targetNode.getLeft() != null) {
                    //need to consider the parent node is null
                    if (parentNode != null) {
                        //if target node is the left node of parent node
                        if (parentNode.getLeft().getValue() == value) {
                            parentNode.setLeft(targetNode.getLeft());
                        }
                        //if target node is the right node of parent node
                        else {
                            parentNode.setRight(targetNode.getLeft());
                        }
                    } else {
                        root = targetNode.getLeft();
                    }

                } else {//if target node have right node
                    //if target node is the left node of parent node
                    //need to consider the parent node is null
                    if (parentNode != null) {
                        if (parentNode.getLeft().getValue() == value) {
                            parentNode.setLeft(targetNode.getRight());
                        }
                        //if target node is the right node of parent node
                        else {
                            parentNode.setRight(targetNode.getRight());
                        }
                    } else {
                        root = targetNode.getRight();
                    }

                }
            }
        }

    }


    //To find the min value of the right sub-tree
    //return the min value to give the target node
    //delete the min node
    public int delRightTreeMin(Node node) {
        Node tmp = node;
        //
        while (tmp.getLeft() != null) {
            tmp = tmp.getLeft();
        }
        delNode(tmp.getValue());
        return tmp.getValue();
    }

}

class Node {
    private int value;
    private Node left;
    private Node right;

    public int leftHeight() {
        if (left == null) {
            return 0;
        }
        return left.height();
    }

    public int rightHeight() {
        if (right == null) {
            return 0;
        }
        return right.height();
    }


    //return the height of the sub-tree which the node is as root
    public int height() {
        return Math.max(left == null ? 0 : left.height(),
                right == null ? 0 : right.height()) + 1;
    }

    //left Rotate
    public void leftRotate(){
        //create a new node
        Node newNode = new Node(value);

        //set the left node of current node to the left of newNode
        newNode.setLeft(this.left);

        //set the left node of right son node of current node to the right of newNode
        newNode.setRight(this.right.left);

        //set the value of right son node to the current node
        this.value = this.right.value;

        //set the right node of right node of current node to the right of current node
        this.right = this.right.right;

        //set the newNode to the left of current node
        this.left = newNode;

    }

    public Node(int value) {
        this.value = value;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }

    public void add(Node node) {
        if (node == null) {
            return;
        }
        if (node.value < this.value) {
            if (this.left == null) {
                this.left = node;
            } else {
                this.left.add(node);
            }
        } else {
            if (this.right == null) {
                this.right = node;
            } else {
                this.right.add(node);
            }
        }

        //if it adds a node
        //and the value of height of right sub-tree
        //minus height of left sub-tree is bigger than 1,
        //it needs left rotate
        if(rightHeight() - leftHeight() > 1){
            leftRotate();
        }
    }

    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.infixOrder();
        }
    }

    //To find the node needed to be deleted
    public Node search(int value) {
        if (value == this.value) {
            return this;
        } else if (value < this.value) {
            if (this.left == null) {
                return null;
            }
            return this.left.search(value);
        } else {
            if (this.right == null) {
                return null;
            }
            return this.right.search(value);
        }
    }

    //To find the parent node of the node needed to be deleted
    // value: for searching
    public Node searchParent(int value) {
        if ((this.left != null && this.left.value == value) ||
                (this.right != null && this.right.value == value)) {
            return this;
        } else {
            if (value < this.value && this.left != null) {
                return this.left.searchParent(value);
            } else if (value >= this.value && this.right != null) {
                return this.right.searchParent(value);
            } else {
                return null;
            }
        }
    }
}

右旋转

package com.test.avl;

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};
        AvlTree avlTree = new AvlTree();
        for (int i : arr) {
            avlTree.add(new Node(i));
        }
        avlTree.infixOrder();
        System.out.println("The height of tree: " + avlTree.getRoot().height());
        System.out.println("The height of left sub-tree: " + avlTree.getRoot().getLeft().height());
        System.out.println("The height of right sub-tree: " + avlTree.getRoot().getRight().height());
        System.out.println("balance:");
//        avlTree.getRoot().leftRotate();
//        avlTree.infixOrder();
//        System.out.println("The height of tree: " + avlTree.getRoot().height());
//        System.out.println("The height of left sub-tree: " + avlTree.getRoot().getLeft().height());
//        System.out.println("The height of right sub-tree: " + avlTree.getRoot().getRight().height());
    }
}

class AvlTree {

    private Node root;

    public Node getRoot() {
        return root;
    }

    public void add(Node node) {
        if (node == null) {
            return;
        }
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }

    }

    public void infixOrder() {
        if (root == null) {
            return;
        }
        root.infixOrder();
    }

    public Node search(int value) {
        if (root == null) {
            return null;
        } else {
            return root.search(value);
        }
    }

    public Node searchParent(int value) {
        if (root == null) {
            return null;
        } else {
            return root.searchParent(value);
        }
    }

    public void delNode(int value) {
        if (root == null) {
            return;
        } else {
            Node targetNode = search(value);
            if (targetNode == null) {
                return;
            }
            if (root.getLeft() == null && root.getRight() == null) {
                if (root.getValue() == value) {
                    root = null;
                }
                return;
            }

            //To find parent node of target node
            Node parentNode = searchParent(value);

            //if the target node is leaf node
            if (targetNode.getLeft() == null && targetNode.getRight() == null) {
                if (parentNode.getLeft() != null &&
                        parentNode.getLeft().getValue() == value) {
                    parentNode.setLeft(null);
                } else if (parentNode.getRight() != null &&
                        parentNode.getRight().getValue() == value) {
                    parentNode.setRight(null);
                }

                //if the target node has two sub-trees
            } else if (targetNode.getLeft() != null &&
                    targetNode.getRight() != null) {
                int minValue = delRightTreeMin(targetNode.getRight());
                targetNode.setValue(minValue);


                //if the target node has one sub-tree
            } else {
                //if target node have left node
                if (targetNode.getLeft() != null) {
                    //need to consider the parent node is null
                    if (parentNode != null) {
                        //if target node is the left node of parent node
                        if (parentNode.getLeft().getValue() == value) {
                            parentNode.setLeft(targetNode.getLeft());
                        }
                        //if target node is the right node of parent node
                        else {
                            parentNode.setRight(targetNode.getLeft());
                        }
                    } else {
                        root = targetNode.getLeft();
                    }

                } else {//if target node have right node
                    //if target node is the left node of parent node
                    //need to consider the parent node is null
                    if (parentNode != null) {
                        if (parentNode.getLeft().getValue() == value) {
                            parentNode.setLeft(targetNode.getRight());
                        }
                        //if target node is the right node of parent node
                        else {
                            parentNode.setRight(targetNode.getRight());
                        }
                    } else {
                        root = targetNode.getRight();
                    }

                }
            }
        }

    }


    //To find the min value of the right sub-tree
    //return the min value to give the target node
    //delete the min node
    public int delRightTreeMin(Node node) {
        Node tmp = node;
        //
        while (tmp.getLeft() != null) {
            tmp = tmp.getLeft();
        }
        delNode(tmp.getValue());
        return tmp.getValue();
    }

}

class Node {
    private int value;
    private Node left;
    private Node right;

    public int leftHeight() {
        if (left == null) {
            return 0;
        }
        return left.height();
    }

    public int rightHeight() {
        if (right == null) {
            return 0;
        }
        return right.height();
    }


    //return the height of the sub-tree which the node is as root
    public int height() {
        return Math.max(left == null ? 0 : left.height(),
                right == null ? 0 : right.height()) + 1;
    }

    //left Rotate
    public void leftRotate() {
        //create a new node
        Node newNode = new Node(value);

        //set the left node of current node to the left of newNode
        newNode.setLeft(this.left);

        //set the left node of right son node of current node to the right of newNode
        newNode.setRight(this.right.left);

        //set the value of right son node to the current node
        this.value = this.right.value;

        //set the right node of right node of current node to the right of current node
        this.right = this.right.right;

        //set the newNode to the left of current node
        this.left = newNode;

    }

    public void rightRotate() {
        Node newNode = new Node(value);

        newNode.setRight(this.right);

        newNode.setLeft(this.left.right);

        this.setValue(this.left.value);

        this.setLeft(this.left.left);

        this.setRight(newNode);
    }


    public Node(int value) {
        this.value = value;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }

    public void add(Node node) {
        if (node == null) {
            return;
        }
        if (node.value < this.value) {
            if (this.left == null) {
                this.left = node;
            } else {
                this.left.add(node);
            }
        } else {
            if (this.right == null) {
                this.right = node;
            } else {
                this.right.add(node);
            }
        }

        //if it adds a node
        //and the value of height of right sub-tree
        //minus height of left sub-tree is bigger than 1,
        //it needs left rotate
        if (rightHeight() - leftHeight() > 1) {
            leftRotate();
        }

        if (leftHeight() - rightHeight() > 1) {
            rightRotate();
        }
    }

    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.infixOrder();
        }
    }

    //To find the node needed to be deleted
    public Node search(int value) {
        if (value == this.value) {
            return this;
        } else if (value < this.value) {
            if (this.left == null) {
                return null;
            }
            return this.left.search(value);
        } else {
            if (this.right == null) {
                return null;
            }
            return this.right.search(value);
        }
    }

    //To find the parent node of the node needed to be deleted
    // value: for searching
    public Node searchParent(int value) {
        if ((this.left != null && this.left.value == value) ||
                (this.right != null && this.right.value == value)) {
            return this;
        } else {
            if (value < this.value && this.left != null) {
                return this.left.searchParent(value);
            } else if (value >= this.value && this.right != null) {
                return this.right.searchParent(value);
            } else {
                return null;
            }
        }
    }
}

双旋转

在节点的 add 方法中加这几行代码：

注意：

//if it adds a node
 //and the value of height of right sub-tree
 //minus height of left sub-tree is bigger than 1,
 //it needs left rotate
 if (rightHeight() - leftHeight() > 1) {
     if (right != null && right.leftHeight() > right.rightHeight()) {
         right.rightRotate();
         leftRotate();
     }
     leftRotate();
 }

 if (leftHeight() - rightHeight() > 1) {
     //if the height of right sub-tree of its left node is bigger
     //than height of its right sub-tree
     if (left != null && left.rightHeight() > left.leftHeight() ) {
         left.leftRotate();
         rightRotate();
     } else {
         rightRotate();
     }
 }

多路查找树

图

package com.test.graph;

import java.util.ArrayList;

public class Graph {

    private ArrayList<String> vertexList;
    private int[][] edges;
    private int numOfEdges;

    public static void main(String[] args) {
        Graph graph = new Graph(5);
        String[] vertexes = {"A", "B", "C", "D", "E"};

        //add vertex
        for (String vertex : vertexes) {
            graph.insertVertex(vertex);
        }

        //add edge
        //A-B,A-C,B-C,B-D,B-E
        graph.insertEdge(0,1,1);
        graph.insertEdge(0,2,1);
        graph.insertEdge(1,2,1);
        graph.insertEdge(1,3,1);
        graph.insertEdge(1,4,1);

        graph.showGraph();
    }

    public Graph(int n) {
        edges = new int[n][n];
        vertexList = new ArrayList<String>(n);
        numOfEdges = 0;
    }

    public int getNumOfVertex() {
        return vertexList.size();
    }

    public int getNumOfEdges() {
        return numOfEdges;
    }

    public String getValueByIndex(int i) {
        return vertexList.get(i);
    }

    public int getWeight(int v1, int v2) {
        return edges[v1][v2];
    }

    public void showGraph() {
        for (int[] edge : edges) {
            for (int weight : edge) {
                System.out.print(weight + "/t");
            }
            System.out.println();
        }
    }

    public void insertVertex(String vertex) {
        vertexList.add(vertex);
    }


    //v1 : A->0, v2: B->1
    public void insertEdge(int v1, int v2, int weight) {
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        numOfEdges++;
    }


}

深度优先遍历 DFS

编写思路：

访问节点 v ，并标记已访问
查找 v 的下一个邻接节点 w，使用一个函数去获取 w
如果 w 没有被访问过，就递归访问 w，查找 w 的下一个邻接节点
如果 w 访问过（由3可知 w 及其 w 邻接之后的点都已经被访问过了），访问与 v 邻接的下一个节点，从 v 的第一个邻接节点开始往后找，如果下一个邻接被访问，就再从下一个邻接开始找，直至找到或者所有都被访问完了。
如果找的 v 的下一个邻接，即递归访问 v 的下一个邻接。

//isVisited: the element of class graph to label the vertex has been visited when value of it is true
public void dfs(boolean[] isVisited, int i) {
    //1. visit the vertex
    System.out.println(getValueByIndex(i) + "->");
    // set the vertex have been visited
    isVisited[i] = true;

    //2. find the first neighbor vertex
    int firstNeighbor = getFirstNeighbor(i);
    //3. firstNeighbor is exist
    //there aren't isolated vertex, then it doesn't need else
    if (firstNeighbor != -1) {
        //4. the first vertex hasn't been visited.
        if (!isVisited[firstNeighbor]) {
            dfs(isVisited, firstNeighbor);
        }
        int nextNeighbor = getNextNeighbor(i, firstNeighbor);
        do {
            //it has next neighbor vertex
            if (nextNeighbor != -1 && !isVisited[nextNeighbor]) {
                dfs(isVisited, nextNeighbor);
            }
            //its next neighbor vertex has been visited, to find followings
            nextNeighbor = getNextNeighbor(i, nextNeighbor);
            //it doesn't have next neighbor vertex
            if (nextNeighbor == -1) {
                break;
            }
        } while (true);
    }
}

public int getFirstNeighbor(int index) {
    for (int i = 0; i < vertexList.size(); i++) {
        if (edges[index][i] > 0) {
            return i;
        }
    }
    return -1;
}

public int getNextNeighbor(int v1, int v2) {
    for (int i = v2 + 1; i < vertexList.size(); i++) {
        if (edges[v1][i] > 0) {
            return i;
        }
    }
    return -1;
}

Method 2：

编写思路：

分别编写两个函数，一个函数处理一个节点的，并对其进行深度优先搜索，另一个函数遍历所有节点检查未被处理的函数

public void dfs(boolean[] isVisited, int i) {
    //to print the current value
    System.out.print(getValueByIndex(i) + " => ");
    isVisited[i] = true;

    int w = getFirstNeighbor(i);
    while (w != -1) {
        if(!isVisited[w]){
            dfs(isVisited, w);
        }
        w = getNextNeighbor(i,w);
    }

}

public void dfs(){
    for (int i = 0; i < getNumOfVertex(); i++) {
        if(!isVisited[i]){
            dfs(isVisited,i);
        }
    }
}

广度优先搜索 BFS

编写思路：

输出当前节点并标记
将当前节点存入带邻接队列
先从队列中取出当前节点，然后找其邻接节点
循环获取当前节点的邻接节点，然后入队
当前邻接节点全部入队完之后，对其邻接节点再次寻找邻接节点，直至队列空。

//BFS for a vertex
public void bfs(boolean[] isVisited, int i) {
    int u; // the head node in queue
    int w; // the adjacent vertex of u
    //queue to record visited order of vertex
    LinkedList<Integer> queue = new LinkedList<>();
    //visited the vertex and to print
    System.out.print(getValueByIndex(i) + " => ");
    //label it has been visited
    isVisited[i] = true;
    queue.add(i);

    //if the queue is not empty
    while (!queue.isEmpty()) {
        //get the head node of the queue
        u = queue.removeFirst();
        //get the first neighbor
        w = getFirstNeighbor(u);
        //to find all adjacent vertexes of u
        while (w != -1) {
            if (!isVisited[w]) {
                System.out.print(getValueByIndex(w) + " => ");
                isVisited[w] = true;
                queue.addLast(w);
            }
            w = getNextNeighbor(u, w);
        }
    }
}

public void bfs() {
    for (int i = 0; i < getNumOfVertex(); i++) {
        if (!isVisited[i]) {
            bfs(isVisited, i);
        }
    }
}

十个常用算法

二分查找（非递归）

/**
 * @param arr
 * @param target the num for finding
 * @return the index or -1 which it doesn't be found
 */
public 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 if(arr[mid] < target){
            left = mid + 1;
        }
    }
    return -1;
}

分治算法

汉诺塔

public class HanoiTower {
    public static void main(String[] args) {
        hanoiTower(4, 'A', 'B', 'C');
    }

    public static void hanoiTower(int num, char a, char b, char c) {
        if (num == 1) {
            System.out.println(a + " -> " + c);
        } else {
            //1.  the top plates a -> b
            hanoiTower(num - 1, a, c, b);
            //2. the bottom plate move to c
            System.out.println("num: " + num + " " + a + " -> " + c);
            //3. the top plates b -> c
            hanoiTower(num - 1, b, a, c);
        }
    }
}

动态规划算法

package com.test.Algorithm.dynamic;

public class KnapsackProblem {
    public static void main(String[] args) {
        int[] w = {1, 4, 3}; // the weight of products
        int[] val = {1500, 3000, 2000};// the value of products
        int m = 4; // the capacity of the package
        int n = val.length; // the num of the products

        //the two-dimension array for getting the best result
        //v[i][j] the best value of putting product i;
        int[][] v = new int[n + 1][m + 1];

        //for storing the strategy of putting products
        int[][] strategy = new int[n + 1][m + 1];

        //initialing the v[i][0] and v[0][j]
        for (int i = 0; i < v.length; i++) {
            v[i][0] = 0;
        }

        for (int i = 0; i < v[0].length; i++) {
            v[0][i] = 0;
        }

        for (int i = 1; i < v.length; i++) {
            for (int j = 1; j < v[0].length; j++) {
                //because the index of v is beginning from 1
                //and the index of w is beginning from 0;
                //the w needs beginning from i-1
                if (w[i - 1] > j) {
                    v[i][j] = v[i - 1][j];
                } else {
                    //the operation of val is like w
                    //v[i][j] = Math.max(v[i - 1][j], val[i - 1] + v[i - 1][j - w[i - 1]]);
                    if(v[i - 1][j] < val[i - 1] + v[i - 1][j - w[i - 1]]){
                        //only here is to putting products
                        v[i][j] = val[i - 1] + v[i - 1][j - w[i - 1]];
                        strategy[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[0].length; j++) {
                System.out.print(v[i][j] + " ");{
                }
            }
            System.out.println();
        }
        System.out.println("============");
        for (int i = 0; i < strategy.length; i++) {
            for (int j = 0; j < strategy[0].length; j++) {
                System.out.print(strategy[i][j] + " ");{
                }
            }
            System.out.println();
        }

        System.out.println("============");
        //the best strategy is usually on the last
        int i = strategy.length - 1;
        int j = strategy[0].length - 1;
        while (i>0 && j>0){
            if(strategy[i][j] == 1){
                //if we put product i in the package, the strategy[i]
                //must have 1 in the array
                //only here is to putting products
                //v[i][j] = val[i - 1] + v[i - 1][j - w[i - 1]];
                System.out.println("Put the product " + i);
                //if we put product i in the package, we must put the product
                //which is put in v[i - 1][j - w[i - 1]];
                j -= w[i-1];
            }
            i--;
        }
    }

}

//============================== result ==============================
0 0 0 0 0 
0 1500 1500 1500 1500 
0 1500 1500 1500 3000 
0 1500 1500 2000 3500 
============
0 0 0 0 0 
0 1 1 1 1 
0 0 0 0 1 
0 0 0 1 1 
============
Put the product 3
Put the product 1

KMP 算法

暴力匹配

public static int violenceMatch(String str1, String str2) {
    char[] s1 = str1.toCharArray();
    char[] s2 = str2.toCharArray();

    int s1Len = s1.length;
    int s2Len = s2.length;

    int i = 0;
    int j = 0;
    while (i < s1Len && j < s2Len) {
        if (s1[i] == s2[j]) {
            i++;
            j++;
        } else {
            i = i - j + 1;
            j = 0;
        }
    }

    //if it successfully matches, j == s2Len
    if(j == s2Len){
        return i-j;
    }else {
        return -1;
    }

}

KMP

KMP详细讲解

如何找到部分匹配表

package com.test.Algorithm.kmp;

public class KMPAlgorithm {
    public static void main(String[] args) {
        String str1 = "BBC ABCDAB ABCDABCDABDE";
        String str2 = "ABCDABD";
        int[] next = kmpNext(str2);
        System.out.println(kmpSearch(str1, str2, next));
    }

    /**
     * @param str1 src string
     * @param str2 sub string
     * @param next part matching table
     * @return index of src string of -1 which means it doesn't be found
     */
    public static int kmpSearch(String str1, String str2, int[] next) {
        for (int i = 0, j = 0; i < str1.length(); i++) {

            while (j > 0 && str1.charAt(i) != str2.charAt(j)) {
                j = next[j - 1];
            }
            if (str1.charAt(i) == str2.charAt(j)) {
                j++;
            }
            if (j == str2.length()) {
                return i - j + 1;
            }
        }
        return -1;
    }

    //get the part matching table of a string
    //to calculate the common substr length of the string
    public static int[] kmpNext(String dest) {
        int[] next = new int[dest.length()];
        //if the length of the str is 1, the part matching value is 1
        next[0] = 0;
        //i the beginning index of substr to compare the substr of beginning of j
        for (int i = 1, j = 0; i < dest.length(); i++) {

            while (j > 0 && dest.charAt(i) != dest.charAt(j)) {
                j = next[j - 1];
            }

            if (dest.charAt(i) == dest.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }
}

贪心算法

编写思路：

为不同广播覆盖位置创建 key-value 的 map HashMap<String, HashSet/>
获得所有地区的集合
每次循环比较不同广播台的地区与所有地区获取其交集，并在一次循环中获取最大的交集数的广播台放入到一个 list 中
并再所有地区集合中清除该广播台覆盖区域
最终 list 就获得每次循环的最优解即为最终解

package com.test.Algorithm.greedy;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

public class GreedyAlgorithm {
    public static void main(String[] args) {
        HashMap<String, HashSet<String>> broadcasts = new HashMap<>();
        HashSet<String> regions1 = new HashSet<>();
        regions1.add("beijing");
        regions1.add("shanghai");
        regions1.add("tianjin");
        HashSet<String> regions2 = new HashSet<>();
        regions2.add("guangzhou");
        regions2.add("beijing");
        regions2.add("shenzhen");
        HashSet<String> regions3 = new HashSet<>();
        regions3.add("chengdu");
        regions3.add("shanghai");
        regions3.add("hangzhou");
        HashSet<String> regions4 = new HashSet<>();
        regions4.add("shanghai");
        regions4.add("tianjin");
        HashSet<String> regions5 = new HashSet<>();
        regions5.add("hangzhou");
        regions5.add("dalian");

        broadcasts.put("K1", regions1);
        broadcasts.put("K2", regions2);
        broadcasts.put("K3", regions3);
        broadcasts.put("K4", regions4);
        broadcasts.put("K5", regions5);

        //to store all regions
        HashSet<String> allRegions = new HashSet<>();
        allRegions.add("beijing");
        allRegions.add("shanghai");
        allRegions.add("tianjin");
        allRegions.add("guangzhou");
        allRegions.add("shenzhen");
        allRegions.add("chengdu");
        allRegions.add("hangzhou");
        allRegions.add("dalian");

        ArrayList<String> selections = new ArrayList<>();


        //to store union data of regions and all regions during
        //traverse the regions
        HashSet<String> tempSet = new HashSet<>();
        //to use maxKey to store the key of regions which has the most numerous
        //union data
        String maxKey = null;
        //to store the tempSize of the biggest size for comparing with this time
        int tempSize = 0;

        while (allRegions.size() != 0) {
            maxKey = null;
            tempSize = 0;
            for (String key : broadcasts.keySet()) {

//                if(maxKey!=null && tempSize < tempSet.size()){
//                    tempSize = tempSet.size();
//                }
                tempSet.clear();
                HashSet<String> regions = broadcasts.get(key);
                tempSet.addAll(regions);
                //get the union date from tempSet and allRegions
                //and the results give to tempSet
                tempSet.retainAll(allRegions);

                if (tempSet.size() > 0 && (maxKey == null || tempSet.size() > tempSize)) {
                    maxKey = key;
                    tempSize = tempSet.size();
                }
            }
            if(maxKey != null){
                selections.add(maxKey);
                allRegions.removeAll(broadcasts.get(maxKey));
            }
        }
        System.out.println(selections);
    }
}

普利姆算法 Prim

尽可能选择少的路线，并且每条路最小，保证总里程数最少

package com.test.Algorithm.prim;

import java.util.Arrays;

public class PrimAlgorithm {

    public static void main(String[] args) {
        char[] data = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int numOfVertexes = data.length;
        int[][] weight = { //10000: non-connection
                {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 = new MGraph(numOfVertexes);
        mGraph.createGraph(mGraph,numOfVertexes,data,weight);
        mGraph.showGraph(mGraph);

        MinTree minTree = new MinTree();
        minTree.prim(mGraph,0);
    }
}
class MinTree{
    /**
     *
     * @param graph graph
     * @param v the index of beginning vertex
     */
    public void prim(MGraph graph, int v){
        int[] isVisited = new int[graph.numOfVertexes];

        isVisited[v] = 1;
        //to store vertex v and the closest vertex of v
        int h1 = -1;
        int h2 = -2;
        //for comparing weight of each line
        int tempWeight = 10000;

        //for graph which has num vertexes, it has num - 1 line in min tree
        for (int i = 0; i < graph.numOfVertexes - 1; i++) {

            //To find the closest vertex of each vertex which has been visited
            for (int j = 0; j < graph.numOfVertexes; j++) {
                for (int k = 1; k < graph.numOfVertexes; k++) {
                    if(isVisited[j] == 1 &&
                            isVisited[k] == 0 &&
                            graph.weight[j][k] < tempWeight){
                        h1 = j;
                        h2 = k;
                        tempWeight = graph.weight[j][k];
                    }
                }
            }
            System.out.println(graph.data[h1] +" -w: "+tempWeight+" -> " + graph.data[h2]);
            //set the h2 has been visited for h1
            isVisited[h2] = 1;
            //reset
            tempWeight = 10000;

        }
    }
}

class MGraph {
    int numOfVertexes;
    char[] data; //data of vertex
    int[][] weight; //adjacent matrix

    public MGraph(int numOfVertexes) {
        this.numOfVertexes = numOfVertexes;
        data = new char[numOfVertexes];
        weight = new int[numOfVertexes][numOfVertexes];
    }

    public void createGraph(MGraph graph, int numOfVertexes, char[] data, int[][] weight) {
        for (int i = 0; i < numOfVertexes; i++) {
            graph.data[i] = data[i];
            for (int j = 0; j < numOfVertexes; j++) {
                graph.weight[i][j] = weight[i][j];
            }
        }
    }

    public void showGraph(MGraph graph) {
        for (int[] ints : graph.weight) {
            System.out.println(Arrays.toString(ints));
        }
    }
}

克鲁斯卡尔算法 Kruskal

编写思路：

获取矩阵的边
对边排序
设置动态数组 ends 及其函数，记录每次加入新的边时，获取该边的两个节点 i, j (char 比较 i < j)的终点值，然后对比，如果不同就不形成回路，更新 ends 即 char 小的节点下标指向 char 大的节点 ends[i] = j;
并将当前节点放入结果数组中。

package com.test.Algorithm.Kruskal;

import java.util.ArrayList;
import java.util.Arrays;

public class KruskalCase {

    private int edgeNum;
    private char[] vertexes;
    private int[][] matrix;
    //non-connection
    private static final int INF = Integer.MAX_VALUE;

    public static void main(String[] args) {
        char[] vertexes = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int[][] matrix = {
                {0, 12, INF, INF, INF, 16, 14},
                {12, 0, 10, INF, INF, 7, INF},
                {INF, 10, 0, 3, 5, 6, INF},
                {INF, INF, 3, 0, 4, INF, INF},
                {INF, INF, 5, 4, 0, 2, 8},
                {16, 7, 6, INF, 2, 0, 9},
                {14, INF, INF, INF, 8, 9, 0}};
        KruskalCase kruskalCase = new KruskalCase(vertexes, matrix);
        kruskalCase.kruskal();
    }

    public KruskalCase(char[] vertexes, int[][] matrix) {
        int vLen = vertexes.length;

        //deep copy
        this.vertexes = new char[vLen];
        for (int i = 0; i < vLen; i++) {
            this.vertexes[i] = vertexes[i];
        }
        //deep copy
        this.matrix = new int[vLen][vLen];
        for (int i = 0; i < vLen; i++) {
            for (int j = 0; j < vLen; j++) {
                this.matrix[i][j] = matrix[i][j];
            }
        }
    }

    public void showGraph() {
        for (int[] ints : this.matrix) {
            for (int anInt : ints) {
                System.out.printf("%15d", anInt);
            }
            System.out.println();
        }
    }

    //sort edges
    public void sortEdges(ArrayList<EdgeData> edgeData) {
        edgeData.sort((v1, v2) -> {
            return v1.weight - v2.weight;
        });
    }

    //for getting index of vertex
    public int getIndex(char ch) {
        for (int i = 0; i < this.vertexes.length; i++) {
            if (this.vertexes[i] == ch) {
                return i;
            }
        }
        return -1;
    }

    public ArrayList<EdgeData> getEdges() {
        ArrayList<EdgeData> edgeData = new ArrayList<>();
        for (int i = 0; i < this.vertexes.length; i++) {
            for (int j = i + 1; j < this.vertexes.length; j++) {
                if (this.matrix[i][j] < INF) {
                    edgeData.add(new EdgeData(this.vertexes[i], this.vertexes[j], this.matrix[i][j]));
                }
            }
        }
        return edgeData;
    }

    //find the end index of the vertex i in their line
    public int getEnd(int[] ends, int i) {
        while (ends[i] != 0) {
            i = ends[i];
        }
        return i;
    }

    public void kruskal() {

        //sort edges
        ArrayList<EdgeData> edgeList = getEdges();
        sortEdges(edgeList);

        //for recording end point of each vertexes
        int[] ends = new int[edgeList.size()];

        //for recording result
        EdgeData[] edgeData = new EdgeData[edgeList.size()];



        for (int i = 0; i < edgeList.size(); i++) {
            int v1 = getIndex(edgeList.get(i).Vertex1);
            int v2 = getIndex(edgeList.get(i).Vertex2);

            //To know there is a loop when add edge<v1, v2>
            int m = getEnd(ends, v1);
            int n = getEnd(ends, v2);
            if (m != n) {
                //when we put the chars in arraylist, v1 is always smaller than v2
                //there could be A->B, no B->A
                ends[m] = n;
                edgeData[i] = edgeList.get(i);
            }

        }
        //print the min Tree
        for (EdgeData edgeDatum : edgeData) {
            if(edgeDatum != null){
                System.out.println(edgeDatum);
            }
        }

    }

}

class EdgeData {
    char Vertex1;
    char Vertex2;
    int weight;

    public EdgeData(char vertex1, char vertex2, int weight) {
        Vertex1 = vertex1;
        Vertex2 = vertex2;
        this.weight = weight;
    }

    @Override
    public String toString() {
        return "EdgeData{" +
                "Vertex1=" + Vertex1 +
                ", Vertex2=" + Vertex2 +
                ", weight=" + weight +
                '}';
    }
}

迪杰斯特拉算法 Dijkstra

编写思路：

构建 VisitedVertex 类，并初始化每个属性
写辅助函数用于更新 already_arr，pre_visitied (可以获得两点之间最短的路径见代码结果), dis 的值
写一个函数调用上面的更新方法
由于节点距离需要累加如 G->D （i）要经过 A（index） len = visitedVertex.getDis(index) + matrix/[index][i];
更新前驱节点和距离
对于一个节点完成之后，写一个函数寻找它最近的节点
再用最近的节点去更新 already_arr，pre_visitied, dis 的值

package com.test.Algorithm.dijkstra;

import java.util.Arrays;

public class dijkstraAlgorithm {

    public static void main(String[] args) {
        char[] vertexes = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        final int N = 65535;
        int[][] matrix = {
                {N, 5, 7, N, N, N, 2},
                {5, N, N, 9, N, N, 3},
                {7, N, N, N, 8, N, N},
                {N, 9, N, N, N, 4, N},
                {N, N, 8, N, N, 5, 4},
                {N, N, N, 4, 5, N, 6},
                {2, 3, N, N, 4, 6, N}};
        Graph graph = new Graph(vertexes, matrix);
        graph.showGraph();
        graph.dsj(6);
        VisitedVertex visitedVertex = graph.getVisitedVertex();
        System.out.println("======");
        System.out.println(Arrays.toString(visitedVertex.already_arr));
        System.out.println(Arrays.toString(visitedVertex.pre_visited));
        System.out.println(Arrays.toString(visitedVertex.dis));
    }

}

class Graph {
    private char[] vertexes;
    private int[][] matrix;
    private VisitedVertex visitedVertex;

    public VisitedVertex getVisitedVertex() {
        return visitedVertex;
    }

    public Graph(char[] vertexes, int[][] matrix) {
        this.vertexes = vertexes;
        this.matrix = matrix;
    }

    public void showGraph() {
        for (int[] ints : this.matrix) {
            System.out.println(Arrays.toString(ints));
        }
    }

    public void dsj(int index) {
        visitedVertex = new VisitedVertex(vertexes.length, index);
        update(index);

        for (int i = 1; i < vertexes.length; i++) {
            index = visitedVertex.updateArr();
            update(index);
        }

    }

    private void update(int index) {
        int len = 0;
        for (int i = 0; i < matrix[index].length; i++) {
            //to record the distance from vertex to vertex of index to vertex of i
            len = visitedVertex.getDis(index) + matrix[index][i];

            //len < visitedVertex.getDis(i): new distance is smaller than the distance
            // which stores in array of dis.
            if (!visitedVertex.isVisited(i) && len < visitedVertex.getDis(i)) {
                visitedVertex.updatePre(i, index);
                visitedVertex.updateDis(i, len);
            }
        }

    }

}

class VisitedVertex {
    //to record vertex which has been visited
    public int[] already_arr;

    //to record vertex which connects this vertex
    public int[] pre_visited;

    //to record distance from current vertex to each vertexes which connect with it
    public int[] dis;

    public VisitedVertex(int length, int index) {
        this.already_arr = new int[length];
        this.pre_visited = new int[length];
        this.dis = new int[length];
        //initial dis
        Arrays.fill(dis, 65535);
        this.dis[index] = 0;
        this.already_arr[index] = 1;
    }

    public boolean isVisited(int index) {
        return already_arr[index] == 1;
    }

    //update the distance from this vertex to vertex of index
    public void updateDis(int index, int len) {
        dis[index] = len;
    }


    public void updatePre(int pre, int index) {
        pre_visited[pre] = index;
    }

    public int getDis(int index) {
        return dis[index];
    }


    //to get the next VisitedVertex
    public int updateArr() {
        int min = 65535;
        //the index of the closest vertex for current vertex
        int index = 0;
        for (int i = 0; i < already_arr.length; i++) {
            if (already_arr[i] == 0 && dis[i] < min) {
                min = dis[i];
                index = i;
            }
        }
        already_arr[index] = 1;
        return index;
    }
}

/*
result
[1, 1, 1, 1, 1, 1, 1]
[6, 6, 0, 5, 6, 6, 0]
[2, 3, 9, 10, 4, 6, 0]
G->D : [6, 6, 0, 5, 6, 6, 0],we could know that pre_visited[3:D] = 5 and G should pass index = 5(6:F) to D  
*/

弗洛伊德算法（Floyd）

中间顶点 [ A, B, C, D, E, F, G ]

出发顶点 [ A, B, C, D, E, F, G ]

终止顶点 [ A, B, C, D, E, F, G ]

以 A 为中间顶点，遍历 A 为出发顶点时的终止顶点，直至遍历完所有的出发顶点，然后遍历下一个中间节点直至结束

package com.test.Algorithm.floyd;

import java.util.Arrays;

public class FloydAlgorithm {
    public static void main(String[] args) {
        char[] vertexes = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        final int N = 65535;
        int[][] matrix = {
                {0, 5, 7, N, N, N, 2},
                {5, 0, N, 9, N, N, 3},
                {7, N, 0, N, 8, N, N},
                {N, 9, N, 0, N, 4, N},
                {N, N, 8, N, 0, 5, 4},
                {N, N, N, 4, 5, 0, 6},
                {2, 3, N, N, 4, 6, 0}};
        Graph graph = new Graph(vertexes.length,vertexes, matrix);

        graph.floyd();
        graph.showGraphPreAndDis();
    }
}

class Graph{
    private char[] vertex;
    private int[][] dis; //distance
    private int[][] pre;

    public Graph(int length, char[] vertex, int[][] matrix) {
        this.vertex = vertex;
        this.dis = matrix;
        this.pre = new int[length][length];
        //initialing the pre matrix
        for (int i = 0; i < length; i++) {
            Arrays.fill(pre[i],i);
        }
    }

    public void showGraphPreAndDis(){
        for (int[] ints : this.pre) {
            for (int anInt : ints) {
                System.out.print(vertex[anInt] + " ");
            }
            System.out.println();
        }

        for (int[] di : this.dis) {
            for (int i : di) {
                System.out.printf("%12d", i);
            }
            System.out.println();
        }
    }

    public void floyd(){
        //to store the distance
        int len = 0;

        //traverse middle vertex
        for (int i = 0; i < dis.length; i++) {
            //traverse starting vertex
            for (int j = 0; j < dis.length; j++) {
                //traverse ending vertex
                for (int k = 0; k < dis.length; k++) {
                    //dis[j][i] + dis[i][k] : j -> i -> k
                    len = dis[j][i] + dis[i][k];
                    if(len < dis[j][k]){
                        dis[j][k] = len;
                        //pre[i][k]: store the middle vertex of i->k
                        //such ads A -> D (A->G->F->D)
                        //the middle vertex is to find the middle vertex of G->F->D : F
                        //if pre[j][k] = i, here well be put in G which doesn't be wished
                        pre[j][k] = pre[i][k];
                    }
                }
            }
        }
    }
}

骑士周游

编写思路：

使用 next 函数获取当前节点可以走的下一步节点的集合
递归集合中的节点
当集合中的节点发现无路可走时， step < 棋盘格子数，就需要重设当前格子为未走过，以便之后其他路径可以选择当前格子
如果遍历结束，step == 棋盘格子数，设置变量 finish 已经完成， if( step < X * Y && !finished )
由于 step < 棋盘格子数有两种情况 1. 没有完成 2. 处于回溯之中，为了保证处于回溯中的数据不被修改 !finished 在完成之后就会变成 false 就不会去重设当前格子。

package com.test.horse;

import java.awt.*;
import java.util.ArrayList;
import java.util.Arrays;

public class HorseChessBoard {

    private static int X; //column
    private static int Y; //row
    //To label the position which has been visited
    private static boolean visited[];
    //To know it successfully finished
    private static boolean finished;


    public static void main(String[] args) {
        X = 8;
        Y = 8;
        int row = 1;
        int column = 1;
        int[][] chessBoard = new int[X][Y];
        visited = new boolean[X * Y];
        long start = System.currentTimeMillis();
        traversalChessBoard(chessBoard,row-1, column-1, 1);
        long end = System.currentTimeMillis();
        System.out.println((end-start) + " ms");

        for (int[] ints : chessBoard) {
            for (int anInt : ints) {
                System.out.print(anInt + " ");
            }
            System.out.println();
        }
    }

    public static void traversalChessBoard(int[][] chessBoard, int row, int column, int step) {
        chessBoard[row][column] = step;
        //using one-dimension array to present position
        visited[row * X + column] = true;
        //get next point
        ArrayList<Point> ps = next(new Point(column, row));
        //traverse ps
        while (!ps.isEmpty()) {
            Point p = ps.remove(0);
            if (!visited[p.y * X + p.x]) {
                traversalChessBoard(chessBoard, p.y, p.x, step + 1);
            }
        }
        //if this position couldn't help to successfully finish the task,
        //this position has been traversed and it also could be traversed from other ways
        //value of step is changing with different calls
        //step < X * Y: 1. it doesn't finish
        //              2. it is during the procedure of recalls
        if (step < X * Y && !finished) {
            chessBoard[row][column] = 0;
            visited[row * X + column] = false;
        } else {
            finished = true;
        }
    }


    //To calculate next step that horse could go
    public static ArrayList<Point> next(Point curPoint) {
        ArrayList<Point> ps = new ArrayList<>();
        Point p1 = new Point();
        //To judge 8 positions that horse could go
        //from the up graph
        //Pos.5
        if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y - 1) >= 0) {
            ps.add(new Point(p1));
        }
        //Pos.6
        if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y - 2) >= 0) {
            ps.add(new Point(p1));
        }
        //Pos.7
        if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y - 2) >= 0) {
            ps.add(new Point(p1));
        }
        //Pos.0
        if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) >= 0) {
            ps.add(new Point(p1));
        }
        //Pos.1
        if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y) {
            ps.add(new Point(p1));
        }
        //Pos.2
        if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y) {
            ps.add(new Point(p1));
        }
        //Pos.3
        if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y) {
            ps.add(new Point(p1));
        }
        //Pos.4
        if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < Y) {
            ps.add(new Point(p1));
        }
        return ps;
    }
}
/*
23380 ms
1 8 11 16 3 18 13 64 
10 27 2 7 12 15 4 19 
53 24 9 28 17 6 63 14 
26 39 52 23 62 29 20 5 
43 54 25 38 51 22 33 30 
40 57 42 61 32 35 48 21 
55 44 59 50 37 46 31 34 
58 41 56 45 60 49 36 47
*/

贪心算法优化

马儿走的下一步是下一步集合中数目最少的从而减少回溯的次数。

package com.test.horse;

import java.awt.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

public class HorseChessBoard {

    private static int X; //column
    private static int Y; //row
    //To label the position which has been visited
    private static boolean visited[];
    //To know it successfully finished
    private static boolean finished;


    public static void main(String[] args) {
        X = 8;
        Y = 8;
        int row = 1;
        int column = 1;
        int[][] chessBoard = new int[X][Y];
        visited = new boolean[X * Y];
        long start = System.currentTimeMillis();
        traversalChessBoard(chessBoard,row-1, column-1, 1);
        long end = System.currentTimeMillis();
        System.out.println((end-start) + " ms");

        for (int[] ints : chessBoard) {
            for (int anInt : ints) {
                System.out.print(anInt + " ");
            }
            System.out.println();
        }
    }

    public static void traversalChessBoard(int[][] chessBoard, int row, int column, int step) {
        chessBoard[row][column] = step;
        //using one-dimension array to present position
        visited[row * X + column] = true;
        //get next point
        ArrayList<Point> ps = next(new Point(column, row));
        
        //the addition!!!
        //sort points in ps by the size of collections of each next point of this points
        sort(ps);
        
        //traverse ps
        while (!ps.isEmpty()) {
            Point p = ps.remove(0);
            if (!visited[p.y * X + p.x]) {
                traversalChessBoard(chessBoard, p.y, p.x, step + 1);
            }
        }
        //if this position couldn't help to successfully finish the task,
        //this position has been traversed and it also could be traversed from other ways
        //value of step is changing with different calls
        //step < X * Y: 1. it doesn't finish
        //              2. it is during the procedure of recalls
        if (step < X * Y && !finished) {
            chessBoard[row][column] = 0;
            visited[row * X + column] = false;
        } else {
            finished = true;
        }
    }


    //To calculate next step that horse could go
    public static ArrayList<Point> next(Point curPoint) {
        ArrayList<Point> ps = new ArrayList<>();
        Point p1 = new Point();
        //To judge 8 positions that horse could go
        //from the up graph
        //Pos.5
        if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y - 1) >= 0) {
            ps.add(new Point(p1));
        }
        //Pos.6
        if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y - 2) >= 0) {
            ps.add(new Point(p1));
        }
        //Pos.7
        if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y - 2) >= 0) {
            ps.add(new Point(p1));
        }
        //Pos.0
        if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) >= 0) {
            ps.add(new Point(p1));
        }
        //Pos.1
        if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y) {
            ps.add(new Point(p1));
        }
        //Pos.2
        if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y) {
            ps.add(new Point(p1));
        }
        //Pos.3
        if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y) {
            ps.add(new Point(p1));
        }
        //Pos.4
        if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < Y) {
            ps.add(new Point(p1));
        }
        return ps;
    }
    
//the addition!!!
    public static void sort(ArrayList<Point> ps){
//        ps.sort(new Comparator<Point>() {
//            @Override
//            public int compare(Point o1, Point o2) {
//                int size1 = next(o1).size();
//                int size2 = next(o2).size();
//                if(size1 <size2){
//                    return -1;
//                }else if(size1 == size2){
//                    return 0;
//                }else {
//                    return 1;
//                }
//            }
//        });
        ps.sort((p1,p2)->{
            return next(p1).size() - next(p2).size();
        });
    }
}

/*
100 ms
1 16 37 32 3 18 47 22 
38 31 2 17 48 21 4 19 
15 36 49 54 33 64 23 46 
30 39 60 35 50 53 20 5 
61 14 55 52 63 34 45 24 
40 29 62 59 56 51 6 9 
13 58 27 42 11 8 25 44 
28 41 12 57 26 43 10 7 
*/

Date Structure > Algorithm > Java

#Algorithm #Java #Date Structure

Java Data Structure and Algorithm

http://example.com/2022/06/19/Java-data-structure-and-algorithm/

作者

Zhao Zhuoyue

发布于

2022年6月19日

许可协议

Code Daily (1) 上一篇

Hello World 下一篇

Java Data Structure and Algorithm

Java 数据结构与算法

选择排序

递归

链表 队列

双向链表

单向环形链表 约瑟夫问题

栈

栈实现综合计算器

中缀表达式转后缀表达式

递归

迷宫问题：

八皇后问题

排序算法

冒泡排序

选择排序

插入排序

希尔排序

交换式：

移动法

快速排序

编写思路：

归并排序

编写思路

基数排序

排序对比

查找算法

二分查找

插值查找

斐波拉契查找

哈希表

Tree

前中后序查找

删除节点

顺序存储二叉树

线索化二叉树

构建

遍历

堆排序

赫夫曼树

赫夫曼编码

数据压缩

小节（注意事项)

二叉排序树

删除节点

平衡二叉树 AVL 树

左旋转

右旋转

双旋转

多路查找树

图

深度优先遍历 DFS

广度优先搜索 BFS

十个常用算法

二分查找（非递归）

分治算法

汉诺塔

动态规划算法

KMP 算法

暴力匹配

KMP

贪心算法

普利姆算法 Prim

克鲁斯卡尔算法 Kruskal

迪杰斯特拉算法 Dijkstra

弗洛伊德算法（Floyd）

骑士周游

贪心算法优化

链表队列

单向环形链表约瑟夫问题