小灰（小白）的算法之旅

第一章 算法概述

1.1 算法和數(shù)據(jù)結(jié)構(gòu)

• 算法（Algorithm）：在數(shù)學(xué)領(lǐng)域用于解決某一類問題的公式和思想敢辩。如高斯算法：n×(1+n)÷2，可以用于解決1+2+3+……+(n-1)+n的問題藤违。在計算機(jī)領(lǐng)域用于解決特定的運算和邏輯問題。如：運算、查找、排序愚臀、最優(yōu)決策。
• 數(shù)據(jù)結(jié)構(gòu)（Data Structure）：數(shù)據(jù)的組織矾利、管理和存儲格式姑裂。其使用目的是為了高效的訪問和修改數(shù)據(jù)。如：線性結(jié)構(gòu)（數(shù)組男旗、鏈表）舶斧、樹（二叉樹、二叉堆）察皇、圖（多對多）茴厉、其他數(shù)據(jù)結(jié)構(gòu)（哈希鏈表、跳表什荣、位圖等）等矾缓。
• 衡量算法的標(biāo)準(zhǔn)有兩個時間復(fù)雜度和空間復(fù)雜度。

1.2 時間復(fù)雜度

• 基本操作次數(shù)T(n)：線性T(n) = n稻爬；對數(shù)T(n) = log(n)嗜闻；常量T(n) = 1；多項式T(n) = n2+n桅锄。

• 漸進(jìn)時間復(fù)雜度：官方定義所存在函數(shù)f(n)琉雳，使得當(dāng)n趨近于無窮大時，T(n)/f(n)的極限值為不等于零的常數(shù)友瘤，則稱f(n)是T(n)的同數(shù)量級函數(shù)翠肘。記作T(n)=O(f(n))，稱為O(f(n))辫秧，O為算法的漸進(jìn)時間復(fù)雜度束倍，簡稱為時間復(fù)雜度。

• 時間復(fù)雜度推到原則：
  -- 如果運行時間是常數(shù)量級茶没，則用常數(shù)1表示肌幽；
  -- 只保留時間函數(shù)中的最高階項；
  -- 如果最高階項存在抓半，則省去最高階項前面的系數(shù)喂急。

• 大O表示法及時長對比：常量O(1) < 對數(shù)O(n) =O(logN) < 線性O(shè)(n) = n < 多項式O(n) = n2。
  其他算法時間復(fù)雜度：O(nlogn)笛求、O(n3)廊移、O(mn)糕簿、O(2^n)、O(n!)

1.3 空間復(fù)雜度

• 空間計算公式：S(n) = O(f(n))狡孔；常量空間O(1)懂诗、線性空間O(n)、二維空間O(n2)苗膝、遞歸空間O(n)

遞歸算法的空間復(fù)雜度度同深度成正比殃恒。

第二章 數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)

2.1 數(shù)組

• 數(shù)組（Array）是有限個相同類型的變量所組成的有序集合，每一個變量被稱為元素辱揭。
• 數(shù)組在內(nèi)存中是順序存儲离唐。
• 操作：讀取和更新時間復(fù)雜度為O(1)，插入和刪除時間復(fù)雜度為O(n)问窃。
• 優(yōu)勢和劣勢：數(shù)組適合讀操作多亥鬓，寫操作少的場景。
• 數(shù)組基本操作相關(guān)代碼：

public class ArrayBaseOperation {
    //數(shù)組定義
    private int[] array = new int[]{3, 1, 2, 5, 4, 9, 7, 2};
    //記錄元素個數(shù)
    private int size = array.length;

    private void demo() {
        //讀取
        System.out.println("原始數(shù)據(jù)：");
        output();
        //更新
        array[2] = 10;
        //插入
        insert(8, 2);
        System.out.println("插入后的數(shù)據(jù)：");
        output();

        //刪除
        delete(5);
        System.out.println("刪除后的數(shù)據(jù)：");
        output();

    }

    private void output(){
        for (int i = 0; i < size; i++) {
            System.out.print(array[i] + " ");
        }
        //System.out.println(Arrays.toString(array));
    }

    /**
     * 刪除操作
     * @param index 刪除的位置
     * @return
     */
    public int delete(int index) {
        checkIndexBounds(index);
        int deletedElement = array[index];
        for (int i = index; i < size; i++) {
            array[i] = array[i + 1];
        }
        size--;
        return deletedElement;
    }

    /**
     * 插入操作
     * @param element 插入的元素
     * @param index   插入的位置
     */
    public void insert(int element, int index) {
        checkIndexBounds(index);
        if (size >= array.length) {
            //擴(kuò)容
            resize();
        }
        for (int i = size - 1; i >= index; i--) {
            array[i + 1] = array[i];
        }
        array[index] = element;
        size++;
    }

    private void checkIndexBounds(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("超出數(shù)組實際元素范圍!");
        }
    }

    /**
     * 擴(kuò)容
     */
    private void resize() {
        int[] arrayNew = new int[array.length * 2];
        System.arraycopy(array, 0, arrayNew, 0, array.length);
        array = arrayNew;
    }

    /**
     * @return 獲取元素個數(shù)
     */
    public int getSize() {
        return size;
    }

    public static void main(String[] args) {
        ArrayBaseOperation operation = new ArrayBaseOperation();
        operation.demo();
    }
}

輸出結(jié)果：

> Task :lib:ArrayBaseOperation.main()
原始數(shù)據(jù)：
3 1 2 5 4 9 7 2 
插入后的數(shù)據(jù)：
3 1 8 10 5 4 9 7 2 
刪除后的數(shù)據(jù)：
3 1 8 10 5 9 7 2 
BUILD SUCCESSFUL in 0s

2.2 鏈表

• 鏈表（Linked List）是一種在物理上非連續(xù)域庇、非順序的數(shù)據(jù)結(jié)構(gòu)嵌戈，由若干節(jié)點（node）所組成。
• 鏈表在內(nèi)存中是隨機(jī)存儲听皿。
• 鏈表分單向鏈表和雙向鏈表熟呛。
• 操作：查找時間復(fù)雜度是O(n)，更新写穴、插入惰拱、刪除時間復(fù)雜度是O(1)（不考慮查找過程）雌贱。
• 優(yōu)勢和劣勢：與數(shù)組相反啊送，適合讀操作少，寫操作多的場景欣孤。
• 鏈表相關(guān)操作代碼：

public class LinkedListBaseOperation {
    private Node head;//頭節(jié)點
    private Node last;//尾節(jié)點
    private int size;//鏈表長度

    public void demo() {
        //插入數(shù)據(jù)
        insert(3, 0);
//        output();
        insert(5, 1);
//        output();
        insert(7, 2);
//        output();
        insert(9, 0);
//        output();
        insert(4, 3);
//        output();
        insert(2, 3);
//        output();
        insert(1, 1);
        System.out.println("插入數(shù)據(jù)后：");
        //讀取數(shù)據(jù)
        output();
        //刪除數(shù)據(jù)
        remove(0);
        remove(3);
//        remove(4);
        System.out.println("刪除數(shù)據(jù)后：");
        output();
    }

    /**
     * 數(shù)據(jù)輸出
     */
    public void output() {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
        System.out.println();
    }

    /**
     * 數(shù)據(jù)刪除
     * @param index 指定刪除節(jié)點位置
     */
    public Node remove(int index) {
        checkIndexBounds(index);
        Node removedNode;
        if (index == 0) {//刪除頭節(jié)點
            removedNode = head;
            head = head.next;
        } else if (index == size - 1) {//刪除尾節(jié)點
            Node prevNode = get(index-1);
            removedNode = prevNode.next;
            prevNode.next = null;
            last = prevNode;
        } else {
            Node prevNode = get(index-1);
            Node nextNode = prevNode.next.next;
            removedNode = prevNode.next;
            prevNode.next = nextNode;
        }
        size--;
        return removedNode;
    }

    /**
     * @param data  插入的數(shù)據(jù)
     * @param index 插入的位置
     */
    public void insert(int data, int index) {
        checkIndexBounds(index);
        Node insertedNode = new Node(data);
        if (size == 0) {
            head = insertedNode;
            last = insertedNode;
        } else if (index == 0) {
            insertedNode.next = head;
            head = insertedNode;
        } else {
            Node prevNode = get(index - 1);//查找數(shù)據(jù)
            Node nextNode = prevNode.next;
            insertedNode.next = nextNode;
            prevNode.next = insertedNode;
        }
        size++;
    }

    /**
     * 數(shù)據(jù)查找
     * @param index 節(jié)點位置
     * @return 獲取指定位置節(jié)點
     */
    private Node get(int index) {
        checkIndexBounds(index);
        Node temp = head;
        for (int i = 0; i < index; i++) {
            temp = temp.next;
        }
        return temp;
    }

    private void checkIndexBounds(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("超出鏈表節(jié)點范圍馋没！");
        }
    }

    /**
     * 單向鏈表
     */
    private static class Node {
        int data;
        Node next;

        Node(int data) {
            this.data = data;
        }
    }

    /**
     * 雙向鏈表
     */
    private static class NodeTW {
        int data;
        NodeTW next;
        NodeTW prev;

        NodeTW(int data) {
            this.data = data;
        }
    }

    public static void main(String[] args) {
        LinkedListBaseOperation operation = new LinkedListBaseOperation();
        operation.demo();
    }
}

輸出結(jié)果：

> Task :lib:LinkedListBaseOperation.main()
插入數(shù)據(jù)后：
9 1 3 5 2 4 7 
刪除數(shù)據(jù)后：
1 3 5 4 7 
BUILD SUCCESSFUL in 0s

2.3 棧和隊列

• 棧是一種線性結(jié)構(gòu)，它就像入口和出口是同一個口的圓桶容器降传，元素只能先進(jìn)后出（First In Last Out篷朵，簡稱FILO）。最先進(jìn)入的叫棧底婆排，最后進(jìn)入的叫棧頂声旺。
• 棧的基本操作：入棧（push）新元素進(jìn)入棧中成為新的棧頂；出棧（pop）棧頂出棧段只，前一個元素成為新的棧頂腮猖。時間復(fù)雜度都是O(1)。
• 隊列是一種線性結(jié)構(gòu)赞枕，它就像出口和入口是不同口的單行隧道澈缺，元素只能先入先出（First In First Out坪创，簡稱FIFO）。出口端是隊頭姐赡，入口端是隊尾莱预。
• 操作：入隊（enqueue）是把新的元素放入隊列中并且成為新的隊尾。出隊（dequeue）就是把元素移除隊列项滑，并且后一個元素成為新的隊頭依沮。
• 應(yīng)用：棧可以用來做歷史回溯枪狂，例如瀏覽器的回溯上一個頁面悉抵。隊列可以用來做歷史順序重演，例如公平鎖隊列等待摘完，或者是網(wǎng)絡(luò)爬蟲模擬網(wǎng)站數(shù)據(jù)抓取姥饰。

實現(xiàn)方式：棧和隊列都可以用數(shù)組或鏈表實現(xiàn)，但是隊列中使用數(shù)組實現(xiàn)孝治，稱為循環(huán)隊列列粪，容量比數(shù)組長度小1。
循環(huán)隊列關(guān)鍵算法：{（隊頭/隊尾下標(biāo)+1）%數(shù)組長度 }計算新隊頭/隊尾下標(biāo)谈飒，如果與隊頭下標(biāo)相等岂座，則隊列已滿。
雙端隊列：隊頭隊尾都可以做入隊或出隊操作杭措。
優(yōu)先隊列：非線性結(jié)構(gòu)费什，按優(yōu)先規(guī)則出隊，如二叉堆手素。

• 循環(huán)隊列相關(guān)代碼

/**
 * 循環(huán)隊列
 */
public class QueueBaseOperation {
    private int[] array;
    private int front;
    private int rear;
    private int size;

    public QueueBaseOperation(int capacity) {
        array = new int[capacity];
    }

    public void demo() {
        try {
            enQueue(1); enQueue(3); enQueue(5); enQueue(7); enQueue(9); enQueue(7);
            System.out.println("入隊后：");
            output();
            deQueue();deQueue();deQueue();
            System.out.println("出隊后：");
            output();
            System.out.println("再入隊：");
            enQueue(1); enQueue(3); enQueue(5); enQueue(7);
            output();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    public void output() {
        for (int i = 0; i < size; i++) {
            System.out.print(array[(front + i) % array.length] + " ");
        }
        System.out.println();
    }

    /**
     * 入隊
     *
     * @param element 入隊元素
     * @throws Exception 隊列滿了鸳址，拋出異常
     */
    public void enQueue(int element) throws Exception {
        if ((rear + 1) % array.length == front) {
            throw new Exception("隊列已滿！");
        }
        array[rear] = element;
        rear = (rear + 1) % array.length;
        size++;
    }

    /**
     * 出隊
     *
     * @return 出隊元素
     * @throws Exception 隊列空了泉懦，拋出異常
     */
    public int deQueue() throws Exception {
        if (rear == front) {
            throw new Exception("隊列已空稿黍！");
        }
        int deQueueElement = array[front];
        front = (front + 1) % array.length;
        size--;
        return deQueueElement;
    }

    public static void main(String[] args) {
        QueueBaseOperation operation = new QueueBaseOperation(10);
        operation.demo();
    }
}

輸出結(jié)果：

> Task :lib:QueueBaseOperation.main()
入隊后：
1 3 5 7 9 7 
出隊后：
7 9 7 
7 9 7 1 3 5 7 9 7 
BUILD SUCCESSFUL in 0s

2.4 散列表

• 散列表又叫哈希表（hash table），存儲鍵（key）和值（value）的映射關(guān)系的集合（數(shù)組+鏈表/紅黑樹）崩哩。對于某一個key巡球，散列表可以在接近O(1)的時間進(jìn)行讀寫操作。散列表通過哈希函數(shù)實現(xiàn)Key和數(shù)組下標(biāo)的轉(zhuǎn)換邓嘹，通過開放尋址法和鏈表法來解決哈希沖突酣栈。

哈希沖突：哈希算法在計算數(shù)組下標(biāo)的時候可能會產(chǎn)生相同的下標(biāo)，這就是所謂的沖突汹押。
開放尋址法：產(chǎn)生哈希沖突矿筝，就向后移位尋找空位。如Java中ThreadLocal使用的就是此方法鲸阻。
鏈表法：數(shù)組中每個元素可以作為鏈表頭節(jié)點跋涣，沖突的元素向鏈表沖插入即可缨睡。
擴(kuò)容（resize）：當(dāng)元素的數(shù)量>=負(fù)載因子×數(shù)組長度時，需要進(jìn)行擴(kuò)充哈希表容量陈辱，首先是生成新的數(shù)組奖年，然后對原始數(shù)據(jù)中的元素重新Hash（rehash）計算，放入新的哈希表中沛贪。

第三章 樹和二叉樹

3.1 樹

• 樹（tree）是n（n>=0）個節(jié)點的有限集陋守。當(dāng)n=0時，稱為空樹利赋。在任意一個非空樹中水评，有如下特點：1.有且有一個特定的稱為根的節(jié)點。2.當(dāng)n>1時媚送，其余節(jié)點可分為m（m>0）個互不相交的有限集中燥，每個集合又是一個樹，并稱為根的子樹塘偎。
• 二叉樹：是樹的特殊形式疗涉，每個節(jié)點最多又兩個子節(jié)點。
• 滿二叉樹：一個二叉樹的所有非葉子節(jié)點都存在左右孩子吟秩，并且所有葉子節(jié)點都在同一層級上咱扣。
• 完全二叉樹：對一個有n個節(jié)點的二叉樹，按層級順序編號涵防，則所有節(jié)點的編號為從1到n闹伪。如果這個樹的所有節(jié)點和同樣深度的滿二叉樹的編號為從1到n的節(jié)點位置相同浦辨，則這個二叉樹為完全二叉樹妻柒。
• 鏈?zhǔn)酱鎯Y(jié)構(gòu)：數(shù)據(jù)變量榛斯、左孩子指針姚糊、右孩子指針。
• 數(shù)組存儲：父節(jié)點parent镶殷、左孩子下標(biāo)2×parent+1茶鹃、有孩子下標(biāo)2×parent+2。
• 查找應(yīng)用：二叉查找樹（binary search tree）
  --如果左樹不為空熏矿，則左子樹所有節(jié)點的值均小于根節(jié)點的值。
  --如果右樹不為空离钝，則右子樹所有節(jié)點的值均大于根節(jié)點的值票编。
  --左、右子樹也都是二叉查找樹卵渴。
  對于節(jié)點分布相對均衡的二叉查找樹來說慧域，如果節(jié)點總數(shù)是n，那么搜索節(jié)點的時間復(fù)雜度就是O(logn)浪读，和樹的深度一樣昔榴。（類似二分查找）
• 維持相對順序應(yīng)用：二叉排序樹（binary sort tree）
  二叉排序樹即是二叉查找樹辛藻，在插入元素時同樣要滿足左、右子樹特點互订，但是有時候會導(dǎo)致元素分布不均衡的情況吱肌，需要通過自平衡解決，如紅黑樹仰禽、AVL樹氮墨、樹堆等。

3.2 二叉樹的遍歷

• 深度優(yōu)先遍歷
  --前序遍歷：根節(jié)點吐葵、左子樹规揪、右子樹。
  --中序遍歷：左子樹温峭、根節(jié)點猛铅、右子樹。
  --后序遍歷：左子樹凤藏、右子樹奕坟、根節(jié)點。
  實現(xiàn)方式用遞歸或棧清笨。
• 廣度優(yōu)先遍歷
  --層序遍歷：從根節(jié)點到葉子節(jié)點逐層遍歷月杉。
  實現(xiàn)方式用隊列。
• 二叉樹遍歷相關(guān)代碼：

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class BinaryTreeTraversal {

    public void demo() {
        LinkedList<Integer> inputList = new LinkedList<>(Arrays.asList(3, 2, 9, null, null, 10, null, null, 8, null, 4));
        TreeNode node = createBinaryTree(inputList);
        System.out.println("前序遍歷：");
        preOrderTraversal(node);
        System.out.println();
        System.out.println("中序遍歷：");
        inOrderTraversal(node);
        System.out.println();
        System.out.println("后序遍歷：");
        postOrderTraversal(node);
        System.out.println();
        System.out.println("層序遍歷：");
        levelOrderTraversal(node);
    }

    /**
     * 構(gòu)建二叉樹
     * @param inputList 數(shù)據(jù)列表
     * @return 根節(jié)點
     */
    public TreeNode createBinaryTree(LinkedList<Integer> inputList) {
        TreeNode treeNode = null;
        if (inputList != null && !inputList.isEmpty()) {
            Integer data = inputList.removeFirst();
            if (data != null) {
                treeNode = new TreeNode(data);
                treeNode.leftChild = createBinaryTree(inputList);
                treeNode.rightChild = createBinaryTree(inputList);
            }
        }
        return treeNode;
    }

    /**
     * 前序遍歷
     * @param node 根節(jié)點
     */
    public void preOrderTraversal(TreeNode node) {
        if (node == null) return;
        System.out.print(node.data + " ");
        preOrderTraversal(node.leftChild);
        preOrderTraversal(node.rightChild);
    }

    /**
     * 中序遍歷
     * @param node 根節(jié)點
     */
    public void inOrderTraversal(TreeNode node) {
        if (node == null) return;
        inOrderTraversal(node.leftChild);
        System.out.print(node.data + " ");
        inOrderTraversal(node.rightChild);
    }

    /**
     * 后序遍歷
     * @param node 根節(jié)點
     */
    public void postOrderTraversal(TreeNode node) {
        if (node == null) return;
        postOrderTraversal(node.leftChild);
        postOrderTraversal(node.rightChild);
        System.out.print(node.data + " ");
    }

    /**
     * 層序遍歷
     * @param node 根節(jié)點
     */
    public void levelOrderTraversal(TreeNode node) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(node);
        while (!queue.isEmpty()) {
            TreeNode treeNode = queue.poll();
            System.out.print(treeNode.data + " ");
            if (treeNode.leftChild != null) {
                queue.offer(treeNode.leftChild);
            }
            if (treeNode.rightChild != null) {
                queue.offer(treeNode.rightChild);
            }
        }
    }

    private static class TreeNode {
        int data;
        TreeNode leftChild;
        TreeNode rightChild;

        TreeNode(int data) {
            this.data = data;
        }
    }

    public static void main(String[] args) {
        BinaryTreeTraversal traversal = new BinaryTreeTraversal();
        traversal.demo();
    }
}

輸出內(nèi)容：

> Task :lib:BinaryTreeTraversal.main()
前序遍歷：
3 2 9 10 8 4 
中序遍歷：
9 2 10 3 8 4 
后序遍歷：
9 10 2 4 8 3 
層序遍歷：
3 2 8 9 10 4 
BUILD SUCCESSFUL in 0s

樹形圖：

                3
             /      \
           2          8
         /   \       /   \
        9    10    null    4
      /   \ /   \ 
  null null null null

構(gòu)建二叉樹的構(gòu)建遞歸過程比較難理解抠艾，先左后右苛萎，null值控制左右節(jié)點遞歸回溯（如果列表中沒有null值，則所有數(shù)據(jù)為左樹子節(jié)點）检号，數(shù)據(jù)列表順序與前序遍歷順序一致

3.3 二叉堆

• 最大堆（大頂堆）：任何一個父節(jié)點的值腌歉，都大于或等于它左、右孩子節(jié)點的值齐苛。
• 最小堆（小頂堆）：任何一個父節(jié)點的值翘盖，都小于或等于它左、右孩子節(jié)點的值凹蜂。
• 插入節(jié)點：插入位置是完全二叉樹最后一個位置馍驯，然后與父節(jié)點對比做“上浮”操作。
• 刪除節(jié)點：刪除堆頂玛痊，將完全二叉樹最后一個節(jié)點移位到堆頂汰瘫，與左右孩子中最小或最大節(jié)點對比做“下沉”操作。
• 構(gòu)建二叉堆：將一個無序的二叉樹調(diào)整為一個二叉堆擂煞，本質(zhì)是讓所有非葉子節(jié)點依次下沉混弥。（與左右孩子中最小或最大節(jié)點對比）

插入和刪除時間復(fù)雜度是：O(logn)；構(gòu)建二叉堆時間復(fù)雜度是：O(n)对省。

• 二叉堆操作相關(guān)代碼：

import java.util.Arrays;

public class BinaryTreeHeap {

    public void demo() {
        System.out.println("上浮前：");
        int[] array = new int[]{1, 3, 2, 6, 5, 7, 8, 9, 10, 0};
        System.out.println(Arrays.toString(array));
        upAdjust(array);
        System.out.println("上浮后：");
        System.out.println(Arrays.toString(array));
        System.out.println("無序數(shù)組：");
        array = new int[]{7, 1, 3, 10, 5, 2, 8, 9, 6};
        System.out.println(Arrays.toString(array));
        buildHeap(array);
        System.out.println("構(gòu)建成二叉堆后：");
        System.out.println(Arrays.toString(array));
    }

    /**
     * 上富饶谩（最小堆）
     * @param array 待調(diào)整數(shù)組
     */
    public void upAdjust(int[] array) {
        int childIndex = array.length - 1;
        int parentIndex = (childIndex - 1) / 2;
        int temp = array[childIndex];
        while (childIndex > 0 && temp < array[parentIndex]) {
            array[childIndex] = array[parentIndex];
            childIndex = parentIndex;
            parentIndex = (parentIndex - 1) / 2;
        }
        array[childIndex] = temp;
    }

    /**
     * 下噶滥蟆（最小堆）
     * @param array 待調(diào)整數(shù)組
     * @param parentIndex 父節(jié)點位置
     */
    public void downAdjust(int[] array, int parentIndex) {
        int temp = array[parentIndex];
        int childIndex = parentIndex * 2 + 1;
        int length = array.length;
        while (childIndex < length) {
            if (childIndex + 1 < length && array[childIndex + 1] < array[childIndex]) {
                childIndex++;
            }
            if (temp <= array[childIndex]) {
                break;
            }
            array[parentIndex] = array[childIndex];
            parentIndex = childIndex;
            childIndex = childIndex * 2 + 1;
        }
        array[parentIndex] = temp;
    }

    /**
     * 將無序數(shù)組構(gòu)建二叉堆（最小堆）
     * @param array 無序的數(shù)組
     */
    public void buildHeap(int[] array) {
        for (int i = (array.length - 2) / 2; i >= 0; i--) {
            downAdjust(array, i);
        }
    }

    public static void main(String[] args) {
        BinaryTreeHeap heap = new BinaryTreeHeap();
        heap.demo();
    }
}

輸出結(jié)果：

> Task :lib:BinaryTreeHeap.main()
上浮前：
[1, 3, 2, 6, 5, 7, 8, 9, 10, 0]
上浮后：
[0, 1, 2, 6, 3, 7, 8, 9, 10, 5]
無序數(shù)組：
[7, 1, 3, 10, 5, 2, 8, 9, 6]
構(gòu)建成二叉堆后：
[1, 5, 2, 6, 7, 3, 8, 9, 10]
BUILD SUCCESSFUL in 0s

二叉堆為順序存儲（數(shù)組），childLeft = parent2+1哀托，childRight = parent2+2粟瞬。
上面的demo都是以最小堆特點進(jìn)行構(gòu)建和排序。

3.4 優(yōu)先隊列

• 隊列的特點是先進(jìn)先出（FIFO）萤捆，而優(yōu)先隊列裙品，則是基于二叉堆的特點所實現(xiàn)的一種順序隊列。優(yōu)先隊列可以根據(jù)對比元素的大小值俗或，進(jìn)而判斷元素的優(yōu)先出隊順序市怎，于元素的入隊順序無關(guān)。
• 優(yōu)先隊列的代碼實現(xiàn)基本與二叉堆無異辛慰，只是在入隊時需要進(jìn)行動態(tài)擴(kuò)容区匠，出隊時需要刪除堆頂。

第四章 排序算法

4.1 引言

希爾排序比較特殊岔擂，它的性能略優(yōu)于O(n2)，但又略低于O(nlogn)

• 穩(wěn)定排序和不穩(wěn)定排序：穩(wěn)定排序能保證相同元素在排序前和排序后的相對順序浪耘，不穩(wěn)定排序則不能乱灵。

4.2 冒泡排序

• 冒泡排序（dubble sort），是一種基礎(chǔ)的交換排序七冲。
  升序：把相鄰的兩個元素進(jìn)行比較痛倚，當(dāng)一個元素大于右側(cè)相鄰元素時，交換他們的位置澜躺；當(dāng)一個元素小于或等于相鄰元素時蝉稳，位置不變。
  冒泡排序?qū)儆诜€(wěn)定排序苗踪，時間復(fù)雜度為O(n2)颠区。
• 雞尾酒排序：由冒泡排序演化而來，如果說普通冒泡排序是單向排序通铲，雞尾酒則是雙向排序。適用于大部分元素有序的情況器贩。
• 代碼實現(xiàn)：

package com.power.dapengeducation.lib;

import java.util.Arrays;
import java.util.Random;

public class BubbleSort {

    private int[] arr = {7, 8, 9, 1, 2, 3, 6, 5, 4};

    public void demo() {
//        int len = 100000;
//        arr = new int[len];
//        Random random = new Random();
//        for (int i = 0; i<len;i++){
//            arr[i] = random.nextInt();
//        }
        long start = System.currentTimeMillis();
//        baseSortAsc(arr);
//        optimalSortAsc(arr);
        cocktailSort(arr);
        long end = System.currentTimeMillis();
        System.out.println("運行時長：" + (end - start));
        System.out.println("排序結(jié)果：" + Arrays.toString(arr));
    }

    /**
     * 雞尾酒排序,適用于大部分元素有序的情況
     *
     * @param array 待排序數(shù)組
     */
    public void cocktailSort(int[] array) {
        int tmp = 0;
        for (int i = 0; i < array.length / 2; i++) {
            boolean isSorted = true;
            //左半邊右移
            for (int j = i; j < array.length - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    tmp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = tmp;
                    isSorted = false;
                }
            }
            if (isSorted) break;
            isSorted = true;
            //右半邊左移
            for (int j = array.length - i - 1; j > i; j--) {
                if (array[j] < array[j - 1]) {
                    tmp = array[j];
                    array[j] = array[j - 1];
                    array[j - 1] = tmp;
                    isSorted = false;
                }
            }
            if (isSorted) break;
        }
    }

    /**
     * 二次優(yōu)化的冒泡排序（升序）
     *
     * @param array 待排序數(shù)組
     */
    public static void optimalSortAsc(int[] array) {
        int sortBorder = array.length - 1;//記錄無序邊界
        int sortBorderTemp = 0;
        for (int i = 0; i < array.length; i++) {
            boolean isSorted = true;//有序標(biāo)記
            for (int j = 0; j < sortBorder; j++) {
                if (array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    isSorted = false;
                    sortBorderTemp = j;
                }
            }
            sortBorder = sortBorderTemp;
            if (isSorted) {
                break;
            }
        }
    }

    /**
     * 無優(yōu)化的冒泡排序(升序)
     *
     * @param array 待排序數(shù)組
     */
    private static void baseSortAsc(int array[]) {
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array.length - 1; j++) {
                if (array[j] > array[j + 1]) {
                    int tmp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = tmp;
                }
            }
        }
    }

    public static void main(String[] args) {
        BubbleSort sort = new BubbleSort();
        sort.demo();
    }
}

輸出結(jié)果：

> Task :lib:BubbleSort.main()
排序結(jié)果：[1, 2, 3, 4, 5, 6, 7, 8, 9]
BUILD SUCCESSFUL in 0s

4.3 快速排序

• 快速排序也屬于交換排序颅夺。快速排序在每一輪挑選一個基準(zhǔn)元素朋截，并讓其他比它大的元素移動到數(shù)列一邊，比它小的元素移動到另一邊吧黄，從而把數(shù)列拆解成兩個部分部服。這種思路叫分治法。
• 平均時間復(fù)雜度O(nlogn)拗慨。
• 選擇基準(zhǔn)元素：隨機(jī)廓八。
• 元素交換：雙邊循環(huán)法和單邊循環(huán)法。
• 相關(guān)代碼實現(xiàn)：

import java.util.Arrays;

public class QuickSort {

    public void demo() {
        int[] arr = {4, 4, 6, 5, 3, 2, 8, 1};
        System.out.println("排序前：" + Arrays.toString(arr));
//        quickSortBilateral(arr, 0, arr.length - 1);
        quickSortUnilateral(arr, 0, arr.length - 1);
        System.out.println("排序后：" + Arrays.toString(arr));
    }

    /**
     * 單邊循環(huán)法快速排序
     *
     * @param arr        待排序數(shù)組
     * @param startIndex 起始位置
     * @param endIndex   結(jié)束位置
     */
    public void quickSortUnilateral(int[] arr, int startIndex, int endIndex) {
        if (startIndex >= endIndex) return;
        int pivotIndex = partitionUnilateral(arr, startIndex, endIndex);
        quickSortUnilateral(arr, startIndex, pivotIndex - 1);
        quickSortUnilateral(arr, pivotIndex + 1, endIndex);
    }

    /**
     * 單邊循環(huán)法分治
     *
     * @param arr        待排序數(shù)組
     * @param startIndex 起始位置
     * @param endIndex   結(jié)束位置
     * @return 基準(zhǔn)位置
     */
    private int partitionUnilateral(int[] arr, int startIndex, int endIndex) {
        int pivot = arr[startIndex];
        int mark = startIndex;
        for (int i = startIndex + 1; i <= endIndex; i++) {
            if (arr[i] < pivot) {
                mark++;
                int temp = arr[i];
                arr[i] = arr[mark];
                arr[mark] = temp;
            }
        }
        arr[startIndex] = arr[mark];
        arr[mark] = pivot;
        return mark;
    }

    /**
     * 雙邊循環(huán)快速排序
     *
     * @param arr        待排序數(shù)組
     * @param startIndex 起始下標(biāo)
     * @param endIndex   結(jié)束下標(biāo)
     */
    public void quickSortBilateral(int[] arr, int startIndex, int endIndex) {
        if (startIndex >= endIndex) return;
        int pivotIndex = partitionBilateral(arr, startIndex, endIndex);
        quickSortBilateral(arr, startIndex, pivotIndex - 1);
        quickSortBilateral(arr, pivotIndex + 1, endIndex);
    }

    /**
     * 雙邊循環(huán)分治
     *
     * @param arr        待交換數(shù)組
     * @param startIndex 起始下標(biāo)
     * @param endIndex   結(jié)束下標(biāo)
     * @return
     */
    public int partitionBilateral(int[] arr, int startIndex, int endIndex) {
        int pivot = arr[startIndex];//也可以隨機(jī)選擇基準(zhǔn)元素
        int left = startIndex;
        int right = endIndex;

        while (left != right) {
            while (right > left && arr[right] > pivot) {
                right--;
            }
            while (left < right && arr[left] <= pivot) {
                left++;
            }
            if (arr[left] > arr[right]) {
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
            }
        }
        arr[startIndex] = arr[left];
        arr[left] = pivot;
        return left;
    }

    public static void main(String[] args) {
        QuickSort sort = new QuickSort();
        sort.demo();
    }
}

輸出結(jié)果：

> Task :lib:QuickSort.main()
排序前：[4, 4, 6, 5, 3, 2, 8, 1]
排序后：[1, 2, 3, 4, 4, 5, 6, 8]
BUILD SUCCESSFUL in 0s

以上排序代碼是用遞歸方式實現(xiàn)赵抢，也可以用棧模擬遞歸實現(xiàn)排序算法剧蹂，代碼略微復(fù)雜，此處省略烦却。

4.4 堆排序

• 堆排序同3.3節(jié) 二叉堆的上浮宠叼、下浮操作。
• 與快速排序對比：平均時間復(fù)雜度都是O(nlogn)其爵，并且都是不穩(wěn)定排序冒冬。快速排序最壞時間復(fù)雜度是O(n2)摩渺，而堆排序最壞時間復(fù)雜度穩(wěn)定在O(nlogn)简烤。空間復(fù)雜度：快速排序是O(logn)，堆排序是O(1).

4.5 計數(shù)排序和桶排序

• 計數(shù)排序：對原始數(shù)據(jù)不做變更摇幻，先生成一個統(tǒng)計數(shù)組乐埠，統(tǒng)計數(shù)組長度為待排序數(shù)組的最大值（max value），利用統(tǒng)計數(shù)組下標(biāo)與待排序數(shù)組元素對比囚企，相同就在統(tǒng)計數(shù)組對應(yīng)下標(biāo)的元素+1丈咐，最后按照統(tǒng)計數(shù)組中記錄的個數(shù)依次輸出下標(biāo)值（0跳過）的順序，既是排序后的數(shù)據(jù)龙宏。

計數(shù)排序優(yōu)化（穩(wěn)定排序）：統(tǒng)計數(shù)組長度為（max - min +1）棵逊。統(tǒng)計數(shù)組中元素值與前面所有元素值相加（變形），得出最終排序位置银酗，然后對待排序數(shù)組進(jìn)行倒序遍歷辆影，在統(tǒng)計數(shù)組查出對應(yīng)元素的值并-1，便會得出待排序數(shù)組元素排序后的下標(biāo)值黍特。
計數(shù)排序適用于整數(shù)排序蛙讥，不適用于最大值與最小值差距過大或者元素不是整數(shù)。

• 優(yōu)化后的計數(shù)排序代碼：

import java.util.Arrays;

public class CountSort {

    public void demo() {
        int[] arr = {95, 94, 91, 98, 99, 90, 99, 93, 91, 92};
        System.out.println(Arrays.toString(countSort(arr)));
    }

    public int[] countSort(int[] arr) {
        int max = arr[0];
        int min = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (max < arr[i]) {
                max = arr[i];
            }
            if (min > arr[i]) {
                min = arr[i];
            }
        }
        int d = max - min;
        //創(chuàng)建統(tǒng)計數(shù)組并統(tǒng)計元素個數(shù)
        int[] countArray = new int[d + 1];
        for (int i = 0; i < arr.length; i++) {
            countArray[arr[i] - min]++;
        }
        //變形處理
        for (int i = 1; i < countArray.length; i++) {
            countArray[i] += countArray[i - 1];
        }
        //根據(jù)統(tǒng)計數(shù)組得出排序后數(shù)組
        int[] sortedArray = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            sortedArray[countArray[arr[i] - min] - 1] = arr[i];
            countArray[arr[i] - min]--;
        }
        return sortedArray;
    }

    public static void main(String[] args) {
        CountSort countSort = new CountSort();
        countSort.demo();
    }
}

輸出結(jié)果：

:lib:CountSort.main()
[90, 91, 91, 92, 93, 94, 95, 98, 99, 99]
BUILD SUCCESSFUL in 2s

• 桶排序：桶排序需要創(chuàng)建若干個桶協(xié)助排序可以與元素個數(shù)相同或其他灭衷，每個桶代表一個區(qū)間范圍區(qū)間跨度 = (max - min) /（ 同數(shù)量-1）次慢，里面可以裝載一個或多個元素，桶按照區(qū)間值大小順序排列，再分別對每個桶中的元素進(jìn)行排序排序算法自行選擇迫像。

桶排序能解決計數(shù)排序的缺點劈愚，對整型或浮點型數(shù)據(jù)都支持，需要注意的是桶的數(shù)量控制闻妓。

• 桶排序相關(guān)代碼：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;

public class BucketSort {

    public void demo() {
        double[] arr = {4.12, 6.421, 0.0023, 3.0, 2.123, 8.122, 4.12, 10.09};
        System.out.println(Arrays.toString(bucketSort(arr)));
    }

    public double[] bucketSort(double[] array) {
        double max = array[0];
        double min = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
            if (array[i] < min) {
                min = array[i];
            }
        }
        //初始化桶
        int bucketNum = array.length;
        double d = max - min;
        ArrayList<LinkedList<Double>> bucketList = new ArrayList<>(bucketNum);
        for (int i = 0; i < bucketNum; i++) {
            bucketList.add(new LinkedList<Double>());
        }
        //向桶中填充元素
        for (int i = 0; i < array.length; i++) {
            //找出桶的位置（有點難理解）
            int index = (int) ((array[i] - min) * (bucketNum - 1) / d);
            //放入桶中
            bucketList.get(index).add(array[i]);
        }
        //排序
        for (int i = 0; i < bucketList.size(); i++) {
            Collections.sort(bucketList.get(i));
        }
        //輸出
        double[] sortedArray = new double[array.length];
        int index = 0;
        for (LinkedList<Double> list : bucketList) {
            for (double element : list) {
                sortedArray[index] = element;
                index++;
            }
        }
        return sortedArray;
    }

    public static void main(String[] args) {
        BucketSort sort = new BucketSort();
        sort.demo();
    }
}

輸出結(jié)果：

> Task :lib:BucketSort.main()
[0.0023, 2.123, 3.0, 4.12, 4.12, 6.421, 8.122, 10.09]
BUILD SUCCESSFUL in 0s

4.6 小結(jié)

第五章 面試中的算法

5.1 判斷鏈表有環(huán)及環(huán)長度

• 雙指針追及法：一個指p1針做單步遍歷p1.next菌羽，另一個指針p2做雙步遍歷p2.next.next，如果有環(huán)由缆，則一定會出現(xiàn)重合p1==p2注祖，環(huán)長度：D頭節(jié)點到入環(huán)節(jié)點距離，S1入環(huán)節(jié)點到相遇節(jié)點距離均唉，S2相遇節(jié)點到入環(huán)節(jié)點距離是晨。p2走兩步，所以行走距離D+S1+S2+S1浸卦，p1走一步署鸡，所以行走距離是D+S1，重合時p2走的距離是p1的兩倍限嫌，所以2(D+S1) = D+2S1+S2 => D=S2靴庆。當(dāng)?shù)谝淮沃睾蠒r，挪動一個指針到head怒医，且兩個指針都做單步遍歷炉抒，當(dāng)再次相遇則是入環(huán)節(jié)點，由此可以得出D/S2的長度稚叹，所以環(huán)長度=鏈表長度-D
• 相關(guān)代碼：

import com.ieugene.algorithmdemo.LinkedListBaseOperation.Node;

public class LinkedCycle {
    private int nodeSize = 0;//demo

    public void demo() {
        Node node1 = new Node(5);
        nodeSize++;
        Node node2 = new Node(3);
        nodeSize++;
        Node node3 = new Node(7);
        nodeSize++;
        Node node4 = new Node(2);
        nodeSize++;
        Node node5 = new Node(6);
        nodeSize++;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node2;
        System.out.println("鏈表環(huán)長度：" + cycleLength(node1));
        System.out.println("鏈表是否有環(huán)：" + hasCycle(node1));
    }

    public int cycleLength(Node head) {
        Node head1 = head;
        Node head2 = head;
        while (head1.next != null && head2.next.next != null) {
            head1 = head1.next;
            head2 = head2.next.next;
            if (head1 == head2) {
                head2 = head;
                break;
            }
        }
        int len = 0;
        while (head1.next != null && head1 != head2) {
            head1 = head1.next;
            head2 = head2.next;
            len++;
        }
        return nodeSize - len;
    }

    /**
     * 判斷鏈表中是否有環(huán)
     *
     * @param head 鏈表頭節(jié)點
     * @return 有環(huán)返回true焰薄，否則是false
     */
    public boolean hasCycle(Node head) {
        Node head1 = head;
        Node head2 = head;
        while (head1.next != null && head2.next.next != null) {
            head1 = head1.next;
            head2 = head2.next.next;
            if (head1 == head2) return true;
        }
        return false;
    }

    public static void main(String[] args) {
        LinkedCycle cycle = new LinkedCycle();
        cycle.demo();
    }
}

輸出結(jié)果：

鏈表環(huán)長度：4
鏈表是否有環(huán)：true
Process finished with exit code 0

5.2 最小棧

• 題要求：保證出棧、入棧扒袖、取最小值時間復(fù)雜度都是O(1)塞茅。
• 思路：用備用棧存儲最小值。
• 相關(guān)代碼：

import java.util.Stack;

public class MinStack {
    private Stack<Integer> mainStack = new Stack<>();
    private Stack<Integer> minStack = new Stack<>();

    public void demo() {
        push(4);
        push(9);
        push(7);
        push(3);
        push(8);
        push(5);
        System.out.println("最小值：" + getMin());
        pop();
        pop();
        pop();
        System.out.println("三次出棧后最小值：" + getMin());
    }

    public void push(int element) {
        mainStack.push(element);
        if (minStack.isEmpty() || minStack.peek() >= element) {
            minStack.push(element);
        }
    }

    public int pop() {
        int element = mainStack.pop();
        if (!minStack.isEmpty() && minStack.peek().equals(element)) {
            minStack.pop();
        }
        return element;
    }

    public int getMin() {
        return minStack.peek();
    }

    public static void main(String[] args) {
        MinStack stack = new MinStack();
        stack.demo();
    }
}

輸出結(jié)果：

最小值：3
三次出棧后最小值：4
Process finished with exit code 0

5.4 求最大公約數(shù)

• 如果數(shù)a能被數(shù)b整除季率，a就叫做b的倍數(shù)野瘦，b就叫做a的約數(shù)。最大公約數(shù)指的是兩個或多個整數(shù)共同的最大約數(shù)飒泻，也叫最大公因數(shù)鞭光。
• 思路：
  --輾轉(zhuǎn)相除法（歐幾里得算法），兩個正整數(shù)a和b（a>b）泞遗，它們的最大公約數(shù)等于a除以b的余數(shù)c和b之間的最大公約數(shù)惰许。
  --更相減損法（更相減損術(shù)），是出自《九章算術(shù)》的一種求最大公約數(shù)的算法史辙，它原本是為約分而設(shè)計的汹买，但它適用于任何需要求最大公約數(shù)的場合佩伤。
  -- 對比：輾轉(zhuǎn)相除法（歐幾里得算法）是基于取模運算，當(dāng)兩個數(shù)較大時卦睹，性能較差畦戒；更相減損法（更相減損術(shù)）是基于減法運算得出結(jié)果方库，當(dāng)兩個數(shù)大小差距較大時结序，計算性能也會被降低。
  --結(jié)論：兩個算法結(jié)合應(yīng)用纵潦，并在更相減損法（更相減損術(shù)）基礎(chǔ)上使用移位運算。

《九章算術(shù)》是中國古代的數(shù)學(xué)專著，其中的“更相減損術(shù)”可以用來求兩個數(shù)的最大公約數(shù)坯门，即“可半者半之椅挣，不可半者，副置分母寥院、子之?dāng)?shù)劲赠，以少減多，更相減損秸谢，求其等也凛澎。以等數(shù)約之」捞悖”
-翻譯成現(xiàn)代語言如下：
第一步：任意給定兩個正整數(shù)塑煎；判斷它們是否都是偶數(shù)。若是臭蚁，則用2約簡最铁；若不是則執(zhí)行第二步。
第二步：以較大的數(shù)減較小的數(shù)垮兑，接著把所得的差與較小的數(shù)比較冷尉，并以大數(shù)減小數(shù)。繼續(xù)這個操作系枪，直到所得的減數(shù)和差相等為止雀哨。
則第一步中約掉的若干個2與第二步中等數(shù)的乘積就是所求的最大公約數(shù)。
其中所說的“等數(shù)”嗤无，就是最大公約數(shù)震束。求“等數(shù)”的辦法是“更相減損”法。所以更相減損法也叫等值算法当犯。
移位運算：位運算相關(guān)知識
當(dāng)a和b均為偶數(shù)時垢村，gcd(a,b) = 2 × gcd(a/2, b/2) = gcd(a>>1, b>>1)<<1。
當(dāng)a為偶數(shù)嚎卫，b為奇數(shù)時嘉栓，gcd(a,b) = gcd(a>>1, b)宏榕。
當(dāng)a為奇數(shù)，b為偶數(shù)時侵佃，gcd(a,b) = gcd(a, b>>1)麻昼。
當(dāng)a和b均為奇數(shù)時，做一次更相減損gcd(a,b) = gcd(a-b, b)馋辈。

• 相關(guān)代碼

public class GreatestCommonDivisor {

    public void demo() {
        System.out.println(getGCD(25, 5));
        System.out.println(getGCD(100, 80));
        System.out.println(getGCD(27, 14));

        //System.out.println(getGCD2(25, 5));
        //System.out.println(getGCD2(100, 80));
        //System.out.println(getGCD2(27, 14));

        //System.out.println(getGCD3(25, 5));
        //System.out.println(getGCD3(100, 80));
        //System.out.println(getGCD3(27, 14));
    }

    public int getGCD(int a, int b) {
        if (a == b) return a;
        if ((a & 1) == 0 && (b & 1) == 0) {
            return getGCD(a >> 1, b >> 1) << 1;
        } else if ((a & 1) == 0 && (b & 1) != 0) {
            return getGCD(a >> 1, b);
        } else if ((a & 1) != 0 && (b & 1) == 0) {
            return getGCD(a, b >> 1);
        } else {
            int big = Math.max(a, b);
            int small = Math.min(a, b);
            return getGCD(big - small, small);
        }
    }

    /**
     * 輾轉(zhuǎn)相除法
     *
     * @param a 正整數(shù)
     * @param b 正整數(shù)
     * @return 最大公約數(shù)
     */
    public int getGCD2(int a, int b) {
        int big = Math.max(a, b);
        int small = Math.min(a, b);
        if (big % small == 0) return small;
        return getGCD2(big % small, small);
    }

    /**
     * 更相減損術(shù)
     *
     * @param a 正整數(shù)
     * @param b 正整數(shù)
     * @return 最大公約數(shù)
     */
    public int getGCD3(int a, int b) {
        if (a == b) return a;
        int big = Math.max(a, b);
        int small = Math.min(a, b);
        return getGCD3(big - small, small);
    }

    public static void main(String[] args) {
        GreatestCommonDivisor divisor = new GreatestCommonDivisor();
        divisor.demo();
    }
}

輸出結(jié)果：

5
20
1
Process finished with exit code 0

5.5 求無序數(shù)列排序后相鄰元素最大差

• 思路：利用桶排序原理抚芦，將無序數(shù)列放置到各自桶中，同時得出每個桶中的最大值和最小值迈螟，然后遍歷每個桶叉抡，用前面的桶最大值與后面桶最小值做差值計算，遍歷完成邊能得出最大差值答毫。

5.6 用棧實現(xiàn)隊列

• 思路：用兩個棧存儲隊列元素褥民，棧A模擬入棧操作，棧B模擬出棧操作洗搂。出棧操作之前如果棧B空了消返，需要將棧A中的元素導(dǎo)入棧B中。
• 相關(guān)代碼：

import java.util.Stack;

public class StackSimulateQueue {
    Stack<Integer> pushStack = new Stack<>();
    Stack<Integer> popStack = new Stack<>();

    public void demo() {
        enqueue(1);
        enqueue(2);
        enqueue(3);
        System.out.println("第一次出隊：" + dequeue());
        System.out.println("第二次出隊：" + dequeue());
        enqueue(4);
        System.out.println("第三次出隊：" + dequeue());
        System.out.println("第四次出隊：" + dequeue());
    }

    //入隊
    public void enqueue(int element) {
        pushStack.push(element);
    }

    //出隊
    public Integer dequeue() {
        if (popStack.isEmpty()) {
            if (pushStack.isEmpty()) {
                return null;
            }
            transfer();
        }
        return popStack.pop();
    }

    private void transfer() {
        while (!pushStack.isEmpty()) {
            popStack.push(pushStack.pop());
        }
    }

    public static void main(String[] args) {
        StackSimulateQueue queue = new StackSimulateQueue();
        queue.demo();
    }
}

輸出結(jié)果：

第一次出隊：1
第二次出隊：2
第三次出隊：3
第四次出隊：4
Process finished with exit code 0

5.7 尋找全排列的下一個數(shù)

• 題意：整數(shù)中全部數(shù)組重新排列耘拇，找出一個僅大于原數(shù)的數(shù)列撵颊。例如給出數(shù)字12345，全排列的下一個數(shù)是12354驼鞭。
• 思路：字典序算法
  --從后向前查看逆序區(qū)秦驯，找到逆序區(qū)域的前一位，也就是數(shù)字置換的邊界挣棕。
  --從逆序區(qū)域的前一位和逆序區(qū)與中大于它的最小的數(shù)字交換位置译隘。
  --把原來的逆序區(qū)域轉(zhuǎn)為順序狀態(tài)。
• 相關(guān)代碼：

import java.util.Arrays;

public class FindNearestNumber {

    public void demo() {
//        int[] numbers = {1, 2, 3, 4, 5};
//        int[] numbers = {1, 2, 3, 5, 4};
        int[] numbers = {1, 2, 3, 5, 4, 7, 9};
        System.out.println(Arrays.toString(findNearestNumber(numbers)));
    }

    public int[] findNearestNumber(int[] numbers) {
        //從后向前查找逆序邊界
        int index = findTransferPoint(numbers);
        //復(fù)制并入?yún)⒙逍模苊庵苯有薷娜雲(yún)?        int[] numbersCopy = Arrays.copyOf(numbers, numbers.length);
        //如果邊界值是0固耘，說明當(dāng)前是最小值
        if (index == 0) return reverseLast(numbersCopy);
        //把逆序區(qū)域的前一位和逆序區(qū)域中剛剛大于它的數(shù)字交換位置
        exchangeHead(numbersCopy, index);
        //把原來逆序區(qū)轉(zhuǎn)為順序
        reverse(numbersCopy, index);
        return numbersCopy;
    }

    private int[] reverseLast(int[] numbers) {
        int len = numbers.length;
        int temp = numbers[len - 1];
        numbers[len - 1] = numbers[len - 2];
        numbers[len - 2] = temp;
        return numbers;
    }

    private int findTransferPoint(int[] numbers) {
        for (int i = numbers.length - 1; i > 0; i--) {
            if (numbers[i - 1] > numbers[i]) {
                return i - 1;
            }
        }
        return 0;
    }

    private int[] exchangeHead(int[] number, int index) {
        int head = number[index - 1];
        int nearestIndex = 0;
        int min = Integer.MAX_VALUE;
        for (int i = number.length - 1; i >= index; i--) {
            if (head < number[i] && (number[i] - head) < min) {
                nearestIndex = i;
                min = number[i] - head;
            }
        }
        number[index - 1] = number[nearestIndex];
        number[nearestIndex] = head;
        return number;
    }

    private int[] reverse(int[] number, int index) {
        for (int i = index; i < number.length; i++) {
            boolean isSorted = true;
            for (int j = index; j < number.length - 1; j++) {
                if (number[j] > number[j + 1]) {
                    int temp = number[j];
                    number[j] = number[j + 1];
                    number[j + 1] = temp;
                    isSorted = false;
                }
            }
            if (isSorted) break;
        }
        return number;
    }

    public static void main(String[] args) {
        FindNearestNumber nearestNumber = new FindNearestNumber();
        nearestNumber.demo();
    }
}

輸出結(jié)果：

[1, 2, 4, 3, 5, 7, 9]
Process finished with exit code 0

5.8 刪去k個數(shù)字后的最小值

• 題意：從一個整數(shù)中刪去k個數(shù)字，使得新整數(shù)的值盡量小词身。例如：1593212厅目，刪除后是1212。
• 思路：貪心算法法严，依次求得局部最優(yōu)解损敷，最終得到全局最優(yōu)解。
  --局部最優(yōu)解：完全正序數(shù)列12345的最大值是它的逆序數(shù)列54321深啤，反過來依然成立拗馒，由此可以得出逆序數(shù)列邊界刪除，便是局部最優(yōu)解溯街。
• 相關(guān)代碼：

public class RemoveDigits {

    public void demo() {
        System.out.println(removeDigits("1593212", 3));
        System.out.println(removeDigits("30200", 1));
        System.out.println(removeDigits("10", 2));
        System.out.println(removeDigits("541270936", 3));
    }

    public String removeDigits(String num, int k) {
        //創(chuàng)建一個棧用于接收所有數(shù)字
        char[] stack = new char[num.length()];
        int top = 0;
        for (int i = 0; i < num.length(); i++) {
            //遍歷當(dāng)前數(shù)字
            char c = num.charAt(i);
            //當(dāng)棧頂數(shù)字大于當(dāng)前遍歷的數(shù)字诱桂，棧頂出棧洋丐，新數(shù)字入棧
            while (top > 0 && stack[top - 1] > c && k > 0) {
                k -= 1;
                top -= 1;
            }
            stack[top++] = c;
        }
        //找出棧底開始都是0的位置
        int offset = 0;
        int newLen = num.length() - k;
        while (offset < newLen && stack[offset] == '0') {
            offset++;
        }
        return offset == newLen ? "0" : new String(stack, offset, newLen - offset);
    }

    public static void main(String[] args) {
        new RemoveDigits().demo();
    }
}

輸出結(jié)果：

1212   
200 
0
120936   
Process finished with exit code 0

5.9 大整數(shù)相加

• 題意：兩個長度超過long類型的大整數(shù)相加，求結(jié)果挥等。
• 思路：拆分?jǐn)?shù)據(jù)友绝，拆分長度為可以直接計算的長度即可，例如int類型數(shù)據(jù)是10位肝劲，為了防止溢出迁客，可以拆分到9位即可。
• 相關(guān)代碼

import java.util.Arrays;

public class BigNumberSum {

    final int MAX_LENGTH = 9;
    final int CARRY_VALUE = 1000000000;

    public void demo() {
        System.out.println(bigNumberSum("987654321987654321987", "222234567891"));
    }

    public String bigNumberSum(String bigNumberA, String bigNumberB) {
        //拆分大數(shù)字
        int[] arrayA = splitBigNumber(bigNumberA);
        int[] arrayB = splitBigNumber(bigNumberB);
        //創(chuàng)建與最大數(shù)字等長的數(shù)組涡相，用于接收計算結(jié)果
        int[] arraySum = new int[Math.max(arrayA.length, arrayB.length)];
        System.out.println("array A: " + Arrays.toString(arrayA));
        System.out.println("array B: " + Arrays.toString(arrayB));
        int minLen = Math.min(arrayA.length, arrayB.length);
        //判斷是否需要進(jìn)位
        boolean isCarry = false;
        for (int i = 0; i < minLen; i++) {
            arraySum[i] = arrayA[i] + arrayB[i];
            if (isCarry) {
                arraySum[i] += 1;
                isCarry = false;
            }
            if (arraySum[i] >= CARRY_VALUE) {
                arraySum[i] -= CARRY_VALUE;
                isCarry = true;
            }
        }
        for (int i = minLen; i < arraySum.length; i++) {
            if (arrayA.length > arrayB.length) {
                arraySum[i] = arrayA[i];
            } else {
                arraySum[i] = arrayB[i];
            }
            if (isCarry) {
                arraySum[i] += 1;
                isCarry = false;
            }
        }
        StringBuilder builder = new StringBuilder();
        for (int i = arraySum.length - 1; i >= 0; i--) {
            if (arraySum[i] == 0) {
                builder.append("000000000");
            } else {
                builder.append(arraySum[i]);
            }

        }
        return builder.toString();
    }

    private int[] splitBigNumber(String number) {
        int length = getArrayLength(number);
        int[] array = new int[length];
        int end = number.length();
        int start;
        for (int i = 0; i < length; i++) {
            start = Math.max(end - MAX_LENGTH, 0);
            array[i] = Integer.parseInt(number.substring(start, end));
            end = start;
        }
        return array;
    }

    private int getArrayLength(String number) {
        int len = 1;
        if (number.length() > MAX_LENGTH) {
            len = number.length() / MAX_LENGTH;
            if (number.length() % MAX_LENGTH != 0)
                len++;
        }
        return len;
    }

    public static void main(String[] args) {
        new BigNumberSum().demo();
    }
}

輸出結(jié)果：

array A: [654321987, 654321987, 987]
array B: [234567891, 222]
987654322209888889878
Process finished with exit code 0

5.10 求解金礦問題

• 題：有五個金礦哲泊，每個金礦含金量不同剩蟀，每個金礦要求的開采開采人數(shù)不同催蝗，不允許開采一部分，要么都開采育特，要不都不采丙号。
• 思路：這個問題屬于動態(tài)規(guī)劃類問題，類似與著名的“背包問題”缰冤，記得《算法圖解》中就是用的背包問題進(jìn)行講解的犬缨。
  --動態(tài)規(guī)劃要點：確定全局最優(yōu)解和最優(yōu)子結(jié)構(gòu)之間的關(guān)系，以及問題的邊界棉浸。
  --動態(tài)規(guī)劃核心：自底向上求解怀薛。
  --這個關(guān)系用數(shù)學(xué)公式表達(dá)：狀態(tài)轉(zhuǎn)移方程式。

//n為金礦數(shù)量
//w為工人數(shù)量
//g[]為金礦含金量數(shù)組
//p[]金礦開采所需人數(shù)數(shù)組
F(n,w) = 0 (n=0或w=0)  //邊界情況
F(n,w) = F(n-1,w)(n>=1,w<p[n-1])  //剩余工人不夠開采當(dāng)前金礦迷郑，只有一種最優(yōu)子結(jié)構(gòu)
F(n,w) = max(F(n-1,w), F(n-1, w-p[n-1])+g[n-1])(n>=1,w>=p[n-1]) //常規(guī)情況枝恋，具有兩種最優(yōu)子結(jié)構(gòu)（當(dāng)前金礦開采或不開采）

• 相關(guān)代碼

public class BestGoldMining {

    public void demo() {
        int w = 10;
        int[] p = {5, 5, 3, 4, 3};
        int[] g = {400, 500, 200, 300, 350};
        System.out.println("最優(yōu)收益：" + getBestGoldMining(w, p, g));
    }

    /**
     * 開采金礦最優(yōu)收益
     *
     * @param w 總?cè)藬?shù)
     * @param p 金礦所需人數(shù)
     * @param g 金礦含量
     * @return
     */
    public int getBestGoldMining(int w, int[] p, int[] g) {
        //創(chuàng)建當(dāng)前結(jié)果
        int[] results = new int[w + 1];
        //填充一維數(shù)組
        for (int i = 1; i <= g.length; i++) {
            for (int j = w; j >= 1; j--) {
                if (j >= p[i - 1]) {
                    results[j] = Math.max(results[j], results[j - p[i - 1]] + g[i - 1]);
                }
            }
        }
        //返回最后一個格子的值
        return results[w];
    }

    public static void main(String[] args) {
        new BestGoldMining().demo();
    }
}

輸出結(jié)果：

最優(yōu)收益：900
Process finished with exit code 0

5.11 尋找缺失的整數(shù)

• 題1：一個無序數(shù)組里有99個不重復(fù)的正整數(shù)，范圍是1~100嗡害，唯獨缺少范圍內(nèi)的一個整數(shù)焚碌，找出這個缺失的整數(shù)。
• 解1：1~100的和減去無序數(shù)組所有元素的和霸妹，差值便是缺失的整數(shù)十电。
• 題2：一個無序整數(shù)數(shù)組里有若干個正整數(shù)，范圍是1~100叹螟，其中99個數(shù)出現(xiàn)偶數(shù)次鹃骂，只有一個整數(shù)出現(xiàn)奇數(shù)次，找出出現(xiàn)奇數(shù)次的整數(shù)罢绽。
• 解2：利用異或運算（XOR）畏线，同位得0，不同位得1有缆。將所有元素依次做異或運算象踊，出現(xiàn)偶數(shù)次的元素相互抵消温亲，最后只剩下出現(xiàn)奇數(shù)次的元素。
• 題3：如果題2中有兩個出現(xiàn)奇數(shù)次的元素杯矩，請找出栈虚。
• 解3：利用分治法。假設(shè)兩個數(shù)是A和B史隆，如果所有元素依次做異或運算魂务，就相當(dāng)于A和B做異或運算，根據(jù)異或運算規(guī)則可以得出泌射，A和B的二進(jìn)制一定會有一個不同位粘姜，一個是1，一個是0熔酷，然后根據(jù)這個二進(jìn)制數(shù)的特點進(jìn)行分類孤紧，倒數(shù)第二位為1的歸為一類，倒數(shù)第二位為0的歸為一類拒秘。這樣問題就回歸到問題2号显，按照問題2的解法便可以找出A和B。
• 相關(guān)代碼：

import java.util.Arrays;

public class FindLostNumber {

    public void demo() {
        int[] array = {4, 1, 2, 2, 5, 1, 4, 3};
        System.out.println("兩個數(shù)是：" + Arrays.toString(findLostNumber(array)));
    }

    public int[] findLostNumber(int[] array) {
        //存儲結(jié)果
        int[] reslut = new int[2];
        //第一次做整體異或運算
        int xorResult = 0;
        for (int i = 0; i < array.length; i++) {
            xorResult ^= array[i];
        }
        if (xorResult == 0) return null;//等于0說明輸入數(shù)據(jù)不符合題要求
        //確定兩個整數(shù)的不同位躺酒，以此來做分組
        int separator = 1;
        while (0 == (xorResult & separator)) {
            separator <<= 1;
        }
        //第二次分組押蚤，進(jìn)行異或運算
        for (int i = 0; i < array.length; i++) {
            if (0 == (array[i] & separator)) {
                reslut[0] ^= array[i];
            } else {
                reslut[1] ^= array[i];
            }
        }
        return reslut;
    }

    public static void main(String[] args) {
        new FindLostNumber().demo();
    }
}

輸出結(jié)果：

兩個數(shù)是：[5, 3]
Process finished with exit code 0

第六章 算法的實際應(yīng)用

6.1 Bitmap的巧用

• Bitmap算法又稱位圖算法。低內(nèi)存占用羹应，高性能位運算是它的優(yōu)勢揽碘。缺點是最大最小值差距不能太大。
• 場景：用戶標(biāo)簽分類查找
• Bitmap算法參考：JDK中BitSet
• Bitmap讀寫操作相關(guān)代碼：

public class Bitmap {
    //每一個word是一個long類型元素园匹，對應(yīng)一個64位二進(jìn)制數(shù)據(jù)
    private long[] words;
    //Bitmap的位數(shù)大小
    private int size;

    public Bitmap(int size) {
        this.size = size;
        this.words = new long[(getWordIndex(size - 1)) + 1];
    }

    /**
     * 判單Bitmap某一位狀態(tài)
     *
     * @param bitIndex 位圖的第bitIndex位（bitIndex=0表示Bitmap左數(shù)第一位）
     * @return
     */
    public boolean getBit(int bitIndex) {
        checkBounds(bitIndex);
        int wordIndex = getWordIndex(bitIndex);
        return (words[wordIndex] & (1L << bitIndex)) != 0;
    }

    private void checkBounds(int index) {
        if (index < 0 || index > this.size - 1) {
            throw new IndexOutOfBoundsException("超過Bitmap的有效范圍");
        }
    }

    /**
     * 把Bitmap的某一位設(shè)置為true
     *
     * @param bitIndex 位圖的第bitIndex位（bitIndex=0表示Bitmap左數(shù)第一位）
     */
    public void setBit(int bitIndex) {
        checkBounds(bitIndex);
        int wordIndex = getWordIndex(bitIndex);
        words[wordIndex] |= (1L << bitIndex);
    }

    /**
     * 定位Bitmap某一位所對應(yīng)的word
     *
     * @param bitIndex 位圖的第bitIndex位（bitIndex=0表示Bitmap左數(shù)第一位）
     * @return
     */
    private int getWordIndex(int bitIndex) {
        return bitIndex >> 6;
    }

    public static void main(String[] args) {
        Bitmap bitmap = new Bitmap(128);
        bitmap.setBit(126);
        bitmap.setBit(75);
        System.out.println(bitmap.getBit(126));
        System.out.println(bitmap.getBit(78));
    }
}

輸出結(jié)果：

true
false
Process finished with exit code 0

6.2 LRU算法應(yīng)用

• LRU全稱Least Recently Used雳刺，最近最少使用。
• 使用場景：長期不被使用偎肃，使用機(jī)率不大的數(shù)據(jù)煞烫，當(dāng)內(nèi)存達(dá)到一定閥值，就會清理電最少被使用的數(shù)據(jù)累颂。
• 原理：內(nèi)部使用哈希鏈表數(shù)據(jù)結(jié)構(gòu)滞详，使得哈希表中無序的數(shù)據(jù)存在前驅(qū)、后繼的排列順序關(guān)系紊馏。每次數(shù)據(jù)的讀寫都會重新排列鏈表結(jié)構(gòu)料饥。Java中LinkedHashMap對哈希鏈表有了很好的實現(xiàn)。
• 相關(guān)代碼：

import com.ieugene.algorithmdemo.LinkedListBaseOperation.NodeTW;
import java.util.HashMap;

public class LRUCache {
    private NodeTW head;
    private NodeTW end;
    //存儲上限
    private final int limit;
    private final HashMap<String, NodeTW> hashMap;

    public LRUCache(int limit) {
        this.limit = limit;
        hashMap = new HashMap<>();
    }

    public Integer get(String key) {
        NodeTW node = hashMap.get(key);
        if (node == null) return null;
        refreshNode(node);
        return node.data;
    }

    public void put(String key, int value) {
        NodeTW node = hashMap.get(key);
        if (node == null) {
            //key不存在朱监，插入數(shù)據(jù)
            if (hashMap.size() >= limit) {
                String oldKey = removeNode(head);
                hashMap.remove(oldKey);
            }
            node = new NodeTW(value);
            node.key = key;
            addNode(node);
            hashMap.put(key, node);
        } else {
            //key存在岸啡，刷新數(shù)據(jù)
            node.data = value;
            refreshNode(node);
        }
    }

    public void remove(String key) {
        NodeTW node = hashMap.get(key);
        removeNode(node);
        hashMap.remove(key);
    }

    /**
     * 刷新被訪問的節(jié)點
     *
     * @param node 被訪問的節(jié)點
     */
    private void refreshNode(NodeTW node) {
        //尾節(jié)點不需要重排
        if (node == end) {
            return;
        }
        //先刪除
        removeNode(node);
        //在重新添加
        addNode(node);
    }

    /**
     * 刪除節(jié)點
     *
     * @param node 被刪除的節(jié)點
     * @return 被刪除的節(jié)點的key
     */
    private String removeNode(NodeTW node) {
        //只有一個節(jié)點
        if (node == head && node == end) {
            head = null;
            end = null;
        } else if (node == end) {
            end = end.prev;
            end.next = null;
        } else if (node == head) {
            head = head.next;
            head.prev = null;
        } else {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
        return node.key;
    }

    /**
     * 插入節(jié)點
     *
     * @param node 被插入的節(jié)點
     */
    private void addNode(NodeTW node) {
        if (end != null) {
            end.next = node;
            node.prev = end;
            node.next = null;
        }
        end = node;
        if (head == null) {
            head = node;
        }
    }

    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(5);
        lruCache.put("001", 1);
        lruCache.put("002", 1);
        lruCache.put("003", 1);
        lruCache.put("004", 1);
        lruCache.put("005", 1);
        lruCache.get("002");
        lruCache.put("004", 2);
        lruCache.put("006", 6);
        System.out.println(lruCache.get("001"));
        System.out.println(lruCache.get("006"));
    }
}

輸出結(jié)果：

null
6
Process finished with exit code 0

6.3 A星尋路算法

• A * search algorithm
• 原理：
  --兩個集合：OpenList：可到達(dá)的格子、CloseList：已到達(dá)的格子赫编。
  --一個公式：F = G + H
  --步驟：1.從起點開始放入OpenList中巡蘸，計算OpenList中F值最小的格子作為下一步即將到達(dá)的格子奋隶，然后從OpenList移除，添加到CloseList悦荒，表示已經(jīng)檢查過唯欣。2.找出上下左右所有可能到達(dá)的格子，看他們是否在兩個列表中搬味，如果不在則加入到OpenList中境氢，并計算響應(yīng)的G、H碰纬、F值萍聊，并把當(dāng)前的格子作為他們的“父節(jié)點”。以此類推悦析，重復(fù)迭代這個過程寿桨，如果OpenList中存在目標(biāo)格子，每一個父節(jié)點和目標(biāo)格子所經(jīng)歷的路徑即是最短路徑她按。

每一個格子有三個屬性牛隅，左下G：從起點走到當(dāng)前格子的成本，也就是已經(jīng)花費了多少步酌泰；右下H：在不考慮障礙的情況下，從當(dāng)前格子走到目標(biāo)格子的距離匕累，也就是離目標(biāo)還有多遠(yuǎn)陵刹；左上F：G和H的綜合評估，也就是從起點到達(dá)目標(biāo)格子的總步數(shù)欢嘿。
以估值高低來決定搜索優(yōu)先次序的方法被稱為啟發(fā)式搜索衰琐。

• 相關(guān)代碼：

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

public class AStartSearch {
    private static final int[][] MAZE = {
            {0, 0, 0, 0, 0, 0, 0},
            {0, 0, 0, 1, 0, 0, 0},
            {0, 0, 0, 1, 0, 0, 0},
            {0, 0, 0, 1, 0, 0, 0},
            {0, 0, 0, 0, 0, 0, 0}
    };

    public Grid aStartSearch(Grid start, Grid end) {
        ArrayList<Grid> openList = new ArrayList<>();
        ArrayList<Grid> closeList = new ArrayList<>();
        openList.add(start);
        while (openList.size() > 0) {
            Grid currentGrid = findMinGrid(openList);
            openList.remove(currentGrid);
            closeList.add(currentGrid);
            List<Grid> neighbors = findNeighbors(currentGrid, openList, closeList);
            for (Grid grid : neighbors) {
                if (!openList.contains(grid)) {
                    grid.initGrid(currentGrid, end);
                    openList.add(grid);
                }
            }
            for (Grid grid : openList) {
                if ((grid.x == end.x) && grid.y == end.y) {
                    return grid;
                }
            }
        }
        return null;
    }

    private Grid findMinGrid(ArrayList<Grid> openList) {
        Grid tempGrid = openList.get(0);
        for (Grid grid : openList) {
            if (grid.f < tempGrid.f) {
                tempGrid = grid;
            }
        }
        return tempGrid;
    }

    private ArrayList<Grid> findNeighbors(Grid grid, List<Grid> openList, List<Grid> closeList) {
        ArrayList<Grid> gridList = new ArrayList<>();
        if (isValidGrid(grid.x, grid.y - 1, openList, closeList)) {
            gridList.add(new Grid(grid.x, grid.y - 1));
        }
        if (isValidGrid(grid.x, grid.y + 1, openList, closeList)) {
            gridList.add(new Grid(grid.x, grid.y + 1));
        }
        if (isValidGrid(grid.x - 1, grid.y, openList, closeList)) {
            gridList.add(new Grid(grid.x - 1, grid.y));
        }
        if (isValidGrid(grid.x + 1, grid.y, openList, closeList)) {
            gridList.add(new Grid(grid.x + 1, grid.y));
        }
        return gridList;
    }

    private boolean isValidGrid(int x, int y, List<Grid> openList, List<Grid> closeList) {
        if (x < 0 || x >= MAZE.length || y < 0 || y >= MAZE[0].length) {
            return false;
        }
        //障礙物
        if (MAZE[x][y] == 1) {
            return false;
        }
        if (containGrid(openList, x, y)) {
            return false;
        }
        if (containGrid(closeList, x, y)) {
            return false;
        }
        return true;
    }

    private boolean containGrid(List<Grid> grids, int x, int y) {
        for (Grid n : grids) {
            if ((n.x == x) && (n.y == y)) {
                return true;
            }
        }
        return false;
    }

    private static class Grid {
        int x, y;
        int f, g, h;
        Grid parent;

        public Grid(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public void initGrid(Grid parent, Grid end) {
            this.parent = parent;
            if (parent != null) {
                this.g = parent.g + 1;
            } else {
                this.g = 1;
            }
            this.h = Math.abs(this.x - end.x) + Math.abs(this.y - end.y);
            this.f = this.g + this.h;
        }
    }

    public static void main(String[] args) {
        Grid startGrid = new Grid(2, 1);
        Grid endGrid = new Grid(2, 5);
        AStartSearch startSearch = new AStartSearch();
        Grid result = startSearch.aStartSearch(startGrid, endGrid);
        ArrayList<Grid> path = new ArrayList<>();
        while (result != null) {
            path.add(new Grid(result.x, result.y));
            result = result.parent;
        }
        for (int i = 0; i < MAZE.length; i++) {
            for (int j = 0; j < MAZE[0].length; j++) {
                if (startSearch.containGrid(path, i, j)) {
                    System.out.print("*, ");
                } else {
                    System.out.print(MAZE[i][j] + ", ");
                }
            }
            System.out.println();
        }
    }
}

輸出結(jié)果：

0, 0, *, *, *, *, 0, 
0, 0, *, 1, 0, *, 0, 
0, *, *, 1, 0, *, 0, 
0, 0, 0, 1, 0, 0, 0, 
0, 0, 0, 0, 0, 0, 0, 
Process finished with exit code 0

6.4 紅包算法

• 場景：隨機(jī)拆分紅包，數(shù)額差距盡量縮小炼蹦。
• 算法：
  --二倍均值法羡宙，公式：每次搶到的金額 = 隨機(jī)區(qū)間[0.01， m/n * 2 - 0.01]元掐隐，m為剩余金額狗热，n為剩余人數(shù)。
  --線段切割法虑省，n個人搶匿刮，隨機(jī)計算出n-1個切割點，隨機(jī)范圍區(qū)間是[1, m - 1]探颈，注意切割點重復(fù)和算法復(fù)雜度熟丸。
• 二倍均值法代碼：

import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class DivideRedPackage {

    public void demo() {
        List<Integer> amountList = divideRedPackage(1000, 10);
        for (Integer amount : amountList) {
            System.out.println("搶到的金額：" + new BigDecimal(amount).divide(new BigDecimal(100)));
        }
    }

    public List<Integer> divideRedPackage(Integer totalAmount, Integer totalPeopleNum) {
        List<Integer> amountList = new ArrayList<>();
        Integer restAmount = totalAmount;
        Integer restPeopleNum = totalPeopleNum;
        Random random = new Random();
        for (int i = 0; i < totalPeopleNum - 1; i++) {
            int amount = random.nextInt(restAmount / restPeopleNum * 2 - 2) + 1;
            restAmount -= amount;
            restPeopleNum--;
            amountList.add(amount);
        }
        amountList.add(restAmount);
        return amountList;
    }

    public static void main(String[] args) {
        new DivideRedPackage().demo();
    }
}

輸出結(jié)果：

搶到的金額：0.98
搶到的金額：1.5
搶到的金額：0.58
搶到的金額：0.52
搶到的金額：0.15
搶到的金額：1.55
搶到的金額：0.69
搶到的金額：2.09
搶到的金額：0.68
搶到的金額：1.26
Process finished with exit code 0

總結(jié)

總體來說還是通俗易懂的，但還是要吐槽一下勘誤略多伪节，缺乏嚴(yán)謹(jǐn)光羞，還有個別地方不統(tǒng)一绩鸣，例如最后面紅包問題描述，單位就不統(tǒng)一纱兑，一會兒是元一會兒是分全闷，對讀者來說不是很友好。