《数据结构与算法》-算法篇

[TOC]

《数据结构与算法》-算法篇

总览-算法

讲贪心算法：如何用贪心算法实现Huffman压缩编码

讲分治算法：谈一谈大规模计算框架MapReduce中的分治思想

讲回溯算法：从电影《蝴蝶效应》中学习回溯算法的核心思想

讲初识动态规划：如何巧妙解决“双十一”购物时的凑单问题

讲动态规划理论：一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题

讲动态规划实战：如何实现搜索引擎中的拼写纠错功能

讲拓扑排序：如何确定代码源文件的编译依赖关系

讲最短路径：地图软件是如何计算出最优出行路径的

讲位图：如何实现网页爬虫中的URL去重功能

讲概率统计：如何利用朴素贝叶斯算法过滤垃圾短信

讲向量空间：如何实现一个简单的音乐推荐系统

讲B+树：MySQL数据库索引是如何实现的

讲搜索：如何用A搜索算法实现游戏中的寻路功能

讲索引：如何在海量数据中快速查找某个数据

讲并行算法：如何利用并行处理提高算法的执行效率

讲贪心算法：如何用贪心算法实现Huffman压缩编码

基础的数据结构和算法在《数据结构与算法》-数据结构篇讲完了。接下来我们开始讲算法篇。讲几种更加基本的算法。它们分别是贪心算法、分治算法、回溯算法、动态规划。更加准确地说我们应该学习的是算法的思想。

贪心算法的经典应用：霍夫曼编码(Huffman Coding)、Prim和Kruskal最小生成树算法、还有Dijkstra单源最短路径算法。最小生成树算法和最短路径算法等。

问题：霍夫曼编码，它是如何利用贪心算法来实现对数据压缩编码，有效节省数据存储空间的。

如何理解”贪心算法”？

场景：在一个给定重量的背包下，要装物品总价值最大的。

思路：我们计算每个物品的单价，依次取最大放入背包中。

贪心算法解决问题的步骤

第一步，当我们看到这类问题的时候，首先要联想到贪心算法：针对一组数据，我们定义了限制值和期望值，希望从中选出几个数据，在满足限制值的情况下，期望值最大。
第二步，我们尝试看下这个问题是否可以用贪心算法解决：每次选择当前情况下，在对限制值同等贡献量的情况下，对期望值贡献最大的数据。
第三部，我们举几个例子看下贪心算法产生的结果是否是最优的。

但是贪心算法的解决问题的思路，并不总能给出最优解。

比如在有权图，找最短路径的过程。即使你的每一步在看来都是最优解，但是你第一步的选择会影响后面的选择的解。

所以，即便我们第一步选择最优的走法(边最短)，但有可能因为这一步选择，导致后面每一步的选择都很糟糕，最终也就无缘全局最优解了。

贪心算法实战分析

分糖果

问题：我们有m个糖果和n个孩子。我们现在要把糖果分给这些孩子吃，但是糖果少，孩子多(m<n)，所以糖果只能分配给一部分孩子。

每个糖果的大小不等，这m个糖果的大小分别是s1，s2，s3，……，sm。除此之外，每个孩子对糖果大小的需求也是不一样的，只有糖果的大小大于等于孩子的对糖果大小的需求的时候，孩子才得到满足。假设这n个孩子对糖果大小的需求分别是 g1，g2，g3，……，gn。

我的问题是，如何分配糖果，能尽可能满足最多数量的孩子?

解决：我们现在来看看如何用贪心算法来解决。对于一个孩子来说，如果小的糖果可以满足，我们就没必要用更大的糖果，这样更大的就可以留给其他对糖果大小需求更大的孩子。另一方面，对糖果大小需求小的孩子更容易被满足，所以，我们可以从需求小的孩子开始分配糖果。因为满足一个需求大的孩子跟满足一个需求小的孩子，对我们期望值的贡献是一样的。

我们每次从剩下的孩子中，找出对糖果大小需求最小的，然后发给他剩下的糖果中能满足他的最小的糖果，这样得到的分配方案，也就是满足的孩子个数最多的方案。

钱币找零

问题：这个问题在我们的日常生活中更加普遍。假设我们有1元、2元、5元、10元、20元、50元、100元这些面额的纸币，它们的张数分别是c1、c2、c5、c10、c20、c50、c100。我们现在要用这些钱来支付K元，最少要用多少张纸币呢?

在生活中，我们肯定是先用面值最大的来支付，如果不够，就继续用更小一点面值的，以此类推，最后剩下的用1元来补⻬。

在贡献相同期望值(纸币数目)的情况下，我们希望多贡献点金额，这样就可以让纸币数更少，这就是一种贪心算法的解决思路。直觉告诉我们，这种处理方法就是最好的。实际上，要严谨地证明这种贪心算法的正确性，需要比较复杂的、有技巧的数学推导，我不建议你花太多时间在上面，不过如果感兴趣的话，可以自己去研究下。

区间覆盖

问题：假设我们有n个区间，区间的起始端点和结束端点分别是[l1, r1]，[l2, r2]，[l3, r3]，……，[ln, rn]。我们从这n个区间中选出一部分区间，这部分区间满足两两不相交(端点相交的情况不算相交)，最多能选出多少个区间呢?

这个问题的处理思路稍微不是那么好懂，不过，我建议你最好能弄懂，因为这个处理思想在很多贪心算法问题中都有用到，比如任务调度、教师排课等等问题。

解决：这个问题的解决思路是这样的:我们假设这n个区间中最左端点是lmin，最右端点是rmax。这个问题就相当于，我们选择几个不相交的区间，从左到右将[lmin, rmax]覆盖上。我们按照起始端点从小到大的顺序对这n个区间排序。

我们每次选择的时候，左端点跟前面的已经覆盖的区间不重合的，右端点又尽量小的，这样可以让剩下的未覆盖区间尽可能的大，就可以放置更多的区间。这实际上就是一种贪心的选择方法。

图文：

问题解答

如何使用贪心算法实现霍弗码编码？
场景：我们有一个包含1000个字符的文件，每个字符占用1个byte(8 bits)，而存储1000个字符，总共需要8000bits，如何节省更多的空间？

方式一：假设我们通过统计分析发现，这1000个字符中只包含6种不同字符，假设它们分别是a、b、c、d、e、f。而3个二进制位 (bit)就可以表示8个不同的字符，所以，为了尽量减少存储空间，每个字符我们用3个二进制位来表示。那存储这1000个字符只需要3000bits就可以了，比原来的存储方式节省了很多空间。

方式二：霍夫曼编码，不仅会考察文本中有多少个不同字符，还会考察每个字符出现的频率，根据频率的不同，选择不同⻓度的编码。霍夫曼编码试图用这种不等⻓的编码方法，来进一步增加压缩的效率。

如何给不同频率的字符选择不同⻓度的编码呢?

根据贪心的思想，我们可以把出现频率比较多的字符，用稍微短一些的编码;出现频率比较少的字符，用稍微⻓一些的编码。

如何解决解压时候不等长的霍夫曼编码？

为了避免解压缩过程中的歧义，霍夫曼编码要求各个字符的编码之间，不会出现某个编码是另一个编码前缀的情况。在解压缩的时候，我们每次会读取尽可能⻓的可解压的二进制串。

实战：这1000个字符只需要2100bits就可以了。

实现技巧：

我们把每个字符看作一个节点，并且辅带着把频率放到优先级队列中。我们从队列中取出频率最小的两个节点A、B，然后新建一个节点C，把频率设置为两个节点的频率之和，并把这个新节点C作为节点A、B的父节点。最后再把C节点放入到优先级队列中。重复这个过程，直到队列中没有数据。

我们给每一条边加上画一个权值，指向左子节点的边我们统统标记为0，指向右子节点的边，我们统统标记为1，那从根节点到叶节点的路径就是叶节点对应字符的霍夫曼编码。

讲分治算法:谈一谈大规模计算框架MapReduce中的分治思想

如何理解分治算法

分治算法定义：英文是divide and conquer，分而治之。也就是将原问题划分成n个规模较小，并且结构与原问题相似的子问题，递归解决这些子问题，然后再合并其结果，就得到原问题的解。
分治和递归的区别：分治算法是一种处理问题的思想，递归是一种编程技巧。
分治算法一般比较适合用递归来实现，每一层递归都会涉及三个操作：
1. 分解:将原问题分解成一系列子问题;
2. 解决:递归地求解各个子问题，若子问题足够小，则直接求解;
3. 合并:将子问题的结果合并成原问题。
什么场景适合使用分治算法来解决？（必须要满足的条件）
1. 原问题与分解成的小问题具有相同的模式;
2. 原问题分解成的子问题可以独立求解，子问题之间没有相关性，这一点是分治算法跟动态规划的明显区别。
3. 具有分解终止条件，也就是说，当问题足够小时，可以直接求解;
4. 可以将子问题合并成原问题，而这个合并操作的复杂度不能太高，否则就起不到减小算法总体复杂度的效果了。

分治算法应用举例

如何编程求出一组数据的有序对个数或者逆序对个数？

场景：根据有序度和逆序度的概念，求解逆序对个数。
解决一：采用两个循环来解决问题，那时间复杂度为O(n²)

解决二：分治算法

我们可以将数组分成前后两半A1和A2，分别计算A1 和A2的逆序对个数K1和K2，然后再计算A1与A2之间的逆序对个数K3。那数组A的逆序对个数就等于K1+K2+K3。
如何计算A1和A2之间的逆序对个数呢？
- 需要想到归并排序的思想。

代码实现

/**
 * 描述:
 * 逆序度个数求解
 *
 * @author Noah
 * @create 2019-11-21 09:39
 */
public class _38_ReverseOrder {

    private int num = 0;

    public static void main(String[] args) {

        _38_ReverseOrder app = new _38_ReverseOrder();
        int[] a = new int[]{2, 4, 3, 1, 5, 6};
        System.out.println("逆序对的个数=" + app.count(a, a.length));
    }


    public int count(int[] a, int n) {
        num = 0;
        mergeSortCounting(a, 0, n - 1);
        return num;
    }

    private void mergeSortCounting(int[] a, int p, int r) {
        if (p >= r) return;
        int q = (p + r) / 2;
        mergeSortCounting(a, p, q);
        mergeSortCounting(a, q + 1, r);
        merge(a, p, q, r);
    }

    private void merge(int[] a, int p, int q, int r) {
        int i = p, j = q + 1, k = 0;
        int[] tmp = new int[r - p + 1];
        while (i <= q && j <= r) {
            if (a[i] <= a[j]) {
                tmp[k++] = a[i++];
            } else {
                // 统计p-q之间，比a[j]大的元素个数
                num += (q - i + 1);
                tmp[k++] = a[j++];
            }
        }
        while (i <= q) {
            // 处理剩下的
            tmp[k++] = a[i++];
        }
        while (j <= r) {
            // 处理剩下的
            tmp[k++] = a[j++];
        }
        for (i = 0; i <= r - p; ++i) {
            // 从tmp拷⻉回a
            a[p + i] = tmp[i];
        }
    }
}

分治算法的相关题目
1. 二维平面上有n个点，如何快速计算出两个距离最近的点对?
2. 有两个nn的矩阵A，B，如何快速求解两个矩阵的乘积C=AB?

分治思想在海量数据处理中的应用

分治算法的思想应用非常广泛，并不仅限于指导编程和算法设计。在海量数据处理的场景中应用十分广泛。突破单机的内存存储和单机处理。

比如前面我们讲过的给10GB的订单根据金额排序。
解决思路
1. 首先分片数据，根据桶排序（线性时间），划分金额的桶。
2. 然后每个桶之间的数据数据排序（归并排序或者快速排序）
3. 如果步骤的2数据量还是太大了，继续划分。

问题解决

为什么说MapReduce的本质就是分治思想?

对于谷歌搜索引擎来说，网⻚爬取、清洗、分析、分词、计算权重、倒排索引等等各个环节中，都会面对如此海量的数据(比如网⻚)。所以，利用集群并行处理显然是大势所趋。
一台机器过于低效，那我们就把任务拆分到多台机器上来处理。如果拆分之后的小任务之间互不干扰，独立计算，最后再将结果合并。这不就是分治思想吗?

讲回溯算法:从电影《蝴蝶效应》中学习回溯算法的核心思想

在深度优先搜索（二叉树的前序、中序、后序）利用的就是回溯算法。但是还有很多应用场景：正则表达式匹配、编译原理中的语法分析、数独、八皇后、0-1背包、图的着色、旅行商问题、全排列等等。

如何理解回溯算法？

概念：如何求解最优解，在”搜索”问题上适用（在一组可能的解中，搜索满足期望的解）。贪心算法每一步看起来是最优解，但是有些情况下最终结果并不是最优解。

八皇后问题

问题定义：我们有一个8x8的棋盘，希望往里放8个棋子(皇后)，每个棋子所在的行、列、对⻆线都不能有另一个棋子。
解决：我们把这个问题划分成8个阶段，依次将8个棋子放到第一行、第二行、第三行……第八行。在放置的过程中，我们不停地检查当前的方法，是否满足要求。如果满足，则跳到下一行继续放置棋子;如果不满足，那就再换一种方法，继续尝试。

实现：非常适合使用递归实现

/**
 * 描述:
 * 参考版
 * 使用回溯思想解决八皇后问题
 *
 * @author Noah
 * @create 2019-11-25 08:48
 */
public class _39_EightQueensProblem {
    /**
     * 全局或成员变量,下标表示行,值表示queen存储在哪一列
     */
    int[] result = new int[8];

    public static void main(String[] args) {
        _39_EightQueensProblem app = new _39_EightQueensProblem();
        app.cal8queens(0);
    }

    /**
     * // 调用方式:cal8queens(0)
     * 八皇后问题
     *
     * @param row
     */
    public void cal8queens(int row) {
        if (row == 8) {
            printQueens(result);// 8个棋子都放置好了，打印结果
            return; // 8行棋子都放好了，已经没法再往下递归了，所以就return
        }
        for (int column = 0; column < 8; ++column) { // 每一行都有8中放法
            if (isOk(row, column)) { // 有些放法不满足要求
                result[row] = column; // 第row行的棋子放到了column列
                cal8queens(row + 1); // 考察下一行
            }
        }
    }

    /**
     * 判断row行column列放置是否合适
     *
     * @param row
     * @param column
     * @return
     */
    private boolean isOk(int row, int column) {
        int leftup = column - 1, rightup = column + 1;
        for (int i = row - 1; i >= 0; --i) { // 逐行往上考察每一行
            if (result[i] == column) return false; // 第i行的column列有棋子吗?
            if (leftup >= 0) { // 考察左上对⻆线:第i行leftup列有棋子吗?
                if (result[i] == leftup) return false;
            }
            if (rightup < 8) { // 考察右上对⻆线:第i行rightup列有棋子吗?
                if (result[i] == rightup) return false;
            }
            --leftup;
            ++rightup;
        }
        return true;
    }

    /**
     * 打印出一个二维矩阵
     *
     * @param result
     */
    private void printQueens(int[] result) {
        for (int row = 0; row < 8; ++row) {
            for (int column = 0; column < 8; ++column) {
                if (result[row] == column) {
                    System.out.print("Q ");
                } else {
                    System.out.print("* ");
                }
            }
            System.out.println();
        }
        System.out.println();
    }
}

图解：有多种解，这只是其中的一个解

-

两个回溯算法的经典应用

回溯算法的实现还是比较难的，尤其是递归实现。我们通过下面的两个例子，进一步加深学习和理解。

0-1背包问题

0-1背包问题是非常经典的算法问题，很多场景都可以抽象为这个问题的模型。最经典的解法是使用冬天规划，不过还有一种简单但是没有那么高效的解法（回溯算法）。

问题：0-1背包问题有很多变体，我这里介绍一种比较基础的。我们有一个背包，背包总的承载重量是Wkg。现在我们有n个物品，每个物品的重量不等，并且不可分割。我们现在期望选择几件物品，装载到背包中。在不超过背包所能装载重量的前提下，如何让背包中物品的总重量最大?

区分：背包问题我们在贪心算法那一节，已经讲过一个了，不过那里讲的物品是可以分割的，我可以装某个物品的一部分到背包里面。今天讲的这个背包问题，物品是不可分割的，要么装要么不装，所以叫0-1背包问题。显然，这个问题已经无法通过贪心算法来解决了。

解决：

对于每个物品来说，都有两种选择，装进背包或者不装进背包。对于n个物品来说，总的装法就有2^n种，去掉总重量超过 Wkg的，从剩下的装法中选择总重量最接近Wkg的。不过，我们如何才能不重复地穷举出这2^n种装法呢?

这里就可以用回溯的方法。我们可以把物品依次排列，整个问题就分解为了n个阶段，每个阶段对应一个物品怎么选择。先对第一个物品进行处理，选择装进去或者不装进去，然后再递归地处理剩下的物品。描述起来很费劲，我们直接看代码，反而会更加清晰一些。

代码实现

/**
 * 描述:
 * 0-1背包问题，使用回溯算法解决
 *
 * @author Noah
 * @create 2019-11-25 09:06
 */
public class _39_KnapsackProblem {
    public int maxW = Integer.MIN_VALUE; //存储背包中物品总重量的最大值

    // cw表示当前已经装进去的物品的重量和;i表示考察到哪个物品了;
    // w背包重量;items表示每个物品的重量;n表示物品个数
    // 假设背包可承受重量100，物品个数10，物品重量存储在数组a中，那可以这样调用函数:
    // f(0, 0, a, 10, 100)
    public void f(int i, int cw, int[] items, int n, int w) {
        if (cw == w || i == n) { // cw==w表示装满了;i==n表示已经考察完所有的物品
            if (cw > maxW) maxW = cw;
            return;
        }
        f(i + 1, cw, items, n, w);
        if (cw + items[i] <= w) {// 已经超过可以背包承受的重量的时候，就不要再装了
            f(i + 1, cw + items[i], items, n, w);
        }
    }

}

正则表达式

场景：使用正则表达式来匹配文本中是否有符合的字符串。假设我们更改了”?”和”*”的语义。

“*”匹配任意多个(大于等于0个)任意字符，“?”匹配零个或者一个任意字符

思路：如果遇到特殊字符的时候，我们就有多种处理方式了，也就是所谓的岔路口，比如“*”有多种匹配方案，可以匹配任意个文本串中的字符，我们就先随意的选择一种匹配方案，然后继续考察剩下的字符。如果中途发现无法继续匹配下去了，我们就回到这个岔路口，重新选择一种匹配方案，然后再继续匹配剩下的字符。

代码实现

/**
 * 描述:
 * 利用回溯算法实现正则表达式匹配
 * <p>
 * “*”匹配任意多个(大于等于0个)任意字 符，“?”匹配零个或者一个任意字符
 *
 * @author Noah
 * @create 2019-11-25 09:14
 */
public class _39_Pattern {
    private boolean matched = false;
    private char[] pattern; // 正则表达式
    private int plen; // 正则表达式⻓度

    public _39_Pattern(char[] pattern, int plen) {
        this.pattern = pattern;
        this.plen = plen;
    }

    public boolean match(char[] text, int tlen) {
        matched = false;

        rmatch(0, 0, text, tlen);
        return matched;
    }

    private void rmatch(int ti, int pj, char[] text, int tlen) {
        if (matched) return; // 如果已经匹配了，就不要继续递归了
        if (pj == plen) { // 正则表达式到结尾了
            if (ti == tlen) matched = true; // 文本串也到结尾了
            return;
        }
        if (pattern[pj] == '*') { // *匹配任意个字符
            for (int k = 0; k <= tlen - ti; ++k) {
                rmatch(ti + k, pj + 1, text, tlen);
            }
        } else if (pattern[pj] == '?') { // ?匹配0个或者1个字符
            rmatch(ti, pj + 1, text, tlen);
            rmatch(ti + 1, pj + 1, text, tlen);
        } else if (ti < tlen && pattern[pj] == text[ti]) { // 纯字符匹配才行
            rmatch(ti + 1, pj + 1, text, tlen);
        }
    }

}

内容总结

回溯算法的思想非常简单，大部分情况下，都是用来解决广义的搜索问题，也就是，从一组可能的解中，选择出一个满足要求的解。回溯算法非常适合用递归来实现，在实现的过程中，剪枝操作是提高回溯效率的一种技巧。利用剪枝，我们并不需要穷举搜索所有的情况，从而提高搜索效率。

讲初识动态规划:如何巧妙解决“双十一”购物时的凑单问题

问题场景：双11有满200减50的活动，假设购物车有n个(n>100)想要买的商品，希望从里面选几个，在凑够满减条件的前提下，让选出来的商品价格总和最大程度地接近满减条件(200元) 。

如何利用动态规划来解决问题？

动态规划学习路线

动态规划比较适合用于求解最优问题，比如求最大值、最小值等等。它可以显著降低时间复杂度，提高代码的执行效率。但是它是非常难学的，跟递归类似，他并不是以人脑思考问题的方式来解决。

因此动态划分为三个章节来讲解：初识动态规划、动态规划理论、动态规划实战。

初始动态规划：通过列举两个非常经典的动态规划问题，让你知道为什么需要动态规划，以及动态规划解题方法是如何演进出来的。实际上，你只要掌握了这两个例子的解决思路，对于其他很多动态规划问题，你都可以套用类似的思路来解决。

动态规划理论：我会总结动态规划适合解决的问题的特征，以及动态规划解题思路。除此之外，我还会将贪心、分治、回溯、动态规划这四种算法思想放在一起，对比分析它们各自的特点以及适用的场景。

动态规划实战：我会教你应用第二节讲的动态规划理论知识，实战解决三个非常经典的动态规划问题，加深你对理论的理解。弄懂了这三节中的例子，对于动态规划这个知识点，你就算是入⻔了。

两个经典动态规划问题

0-1背包问题

回溯算法思想（优化）

代码实现：

/**
 * 简单版本：使用回溯算法求解0-1背包问题
 */
public static class _39_KnapsackProblem_Simple {
    // 回溯算法实现。注意:我把输入的变量都定义成了成员变量。
    private int maxW = Integer.MIN_VALUE; // 结果放到maxW中
    private int[] weight = new int[]{6, 1, 1, 1, 3}; // 物品重量
    private int n = 5; // 物品个数
    private int w = 9; // 背包承受的最大重量
    private boolean[][] mem = new boolean[5][10]; // 备忘录，默认值false

    /**
     * 常规方法：存在冗余计算
     *
     * @param i
     * @param cw
     */
    public void f(int i, int cw) { // 调用f(0, 0)
        if (cw == w || i == n) { // cw==w表示装满了，i==n表示物品都考察完了

            if (cw > maxW) maxW = cw;
            return;
        }

        f(i + 1, cw); // 选择不装第i个物品
        if (cw + weight[i] <= w) {
            f(i + 1, cw + weight[i]); // 选择装第i个物品
        }

    }

    /**
     * 优化版本：使用数组存储临时值
     *
     * @param i
     * @param cw
     */
    public void f2(int i, int cw) { // 调用f(0, 0)
        if (cw == w || i == n) { // cw==w表示装满了，i==n表示物品都考察完了
            if (cw > maxW) maxW = cw;
            return;
        }
        if (mem[i][cw]) return; // 重复状态
        mem[i][cw] = true; // 记录(i, cw)这个状态
        f2(i + 1, cw); // 选择不装第i个物品
        if (cw + weight[i] <= w) {
            f2(i + 1, cw + weight[i]); // 选择装第i个物品

        }
    }
}

图解

优化：递归存在重复计算，我们可以存储一个备忘录来记录那些问题已经计算过了。避免冗余计算。

总结：优化后的方法，执行效率跟动态规划差不多了。

动态规划思想

分析：物品的重量分别为2，2，4，6，3

我们把整个求解过程分为n个阶段，每个阶段会决策一个物品是否放到背包中。每个物品决策(放入或者不放入背包)完之后，背包中的物品的重量会有多种情况，也就是说，会达到多种不同的状态，对应到递归树中，就是有很多不同的节点。
我们把每一层重复的状态(节点)合并，只记录不同的状态，然后基于上一层的状态集合，来推导下一层的状态集合。我们可以通过合并每一层重复的状态，这样就保证每一层不同状态的个数都不会超过w个(w表示背包的承载重量)，也就是例子中的9。于是，我们就成功避免了每层状态个数的指数级增⻓。

实现：

我们用一个二维数组states[n][w+1]，来记录每层可以达到的不同状态。
1. 第0个(下标从0开始编号)物品的重量是2，要么装入背包，要么不装入背包，决策完之后，会对应背包的两种状态，背包中物品的总重量是0或者2。我们用states[0][0]=true和states[0][2]=true来表示这两种状态。
2. 第1个物品的重量也是2，基于之前的背包状态，在这个物品决策完之后，不同的状态有3个，背包中物品总重量分别是 0(0+0)，2(0+2 or 2+0)，4(2+2)。我们用states[1][0]=true，states[1][2]=true，states[1][4]=true来表示这三种状态。
3. 以此类推，直到考察完所有的物品后，整个states状态数组就都计算好了。我把整个计算的过程画了出来，你可以看看。图中 0表示false，1表示true。我们只需要在最后一层，找一个值为true的最接近w(这里是9)的值，就是背包中物品总重量的最大值。
图解

代码实现

/**
 * weight:物品重量，n:物品个数，w:背包可承载重量
 *
 * @param weight
 * @param n
 * @param w
 * @return
 */
public int knapsack(int[] weight, int n, int w) {
    boolean[][] states = new boolean[n][w + 1]; // 默认值false
    states[0][0] = true; // 第一行的数据要特殊处理，可以利用哨兵优化
    states[0][weight[0]] = true;
    for (int i = 1; i < n; ++i) {// 动态规划状态转移
        for (int j = 0; j <= w; ++j) {// 不把第i个物品放入背包
            if (states[i - 1][j] == true) states[i][j] = states[i - 1][j];
        }
        for (int j = 0; j <= w - weight[i]; ++j) {//把第i个物品放入背包
            if (states[i - 1][j] == true) states[i][j + weight[i]] = true;
        }
    }
    for (int i = w; i >= 0; --i) {// 输出结果
        if (states[n - 1][i] == true) return i;
    }
    return 0;
}

总结：这就是一种用动态规划解决问题的思路。我们把问题分解为多个阶段，每个阶段对应一个决策。我们记录每一个阶段可达的状态集合(去掉重复的)，然后通过当前阶段的状态集合，来推导下一个阶段的状态集合，动态地往前推进。

时间复杂度：O(n*w)。n表示物品个数，w表示背包可以承载的总重量。比回溯算法解决0-1背包问题指数级别2^n的性能要高太多了。

代码分析：我们使用了一个二维的数组来存储状态，所以有时候我们会讲动态规划是一种空间换时间的思路。所以这里的二维数组也可以使用一维数组来表示

0-1背包问题升级版

场景：我们现在引入物品价值这一变量。对于一组不同重量、不同价值、不可分割的物品，我们选择将某些物品装入背包，在满足背包最大重量限制的前提下，背包中可装入物品的总价值最大是多少呢?

回溯算法思想

图解：

分析：

在递归树中，有几个节点的i和cw是完全相同的，比如f(2,2,4)和f(2,2,3)。在背包中物品总重量一样的情况下，f(2,2,4)这种状态对应的物品总价值更大，我们可以舍弃f(2,2,3)这种状态，只需要沿着f(2,2,4)这条决策路线继续往下决策就可以。
如果用回溯算法，这个问题就没法再用“备忘录”解决了。

代码实现：

/**
 * 使用回溯算法求解0-1背包升级问题
 *
 * @param i
 * @param cw
 * @param cv
 */
public void f(int i, int cw, int cv) { // 调用f(0, 0, 0)
    if (cw == w || i == n) { // cw==w表示装满了,i==n表示物品都考察完了
        if (cv > maxV) maxV = cv;
        return;
    }
    f(i + 1, cw, cv); // 选择不装第i个物品
    if (cw + weight[i] <= w) {

        f(i + 1, cw + weight[i], cv + value[i]); // 选择装第i个物品
    }
}

动态规划思想

分析：

我们还是把整个求解过程分为n个阶段，每个阶段会决策一个物品是否放到背包中。每个阶段决策完之后，背包中的物品的总重量以及总价值，会有多种情况，也就是会达到多种不同的状态。
我们用一个二维数组states[n][w+1]，来记录每层可以达到的不同状态。不过这里数组存储的值不再是boolean类型的了，而是当前状态对应的最大总价值。我们把每一层中(i, cw)重复的状态(节点)合并，只记录cv值最大的那个状态，然后基于这些状态来推导下一层的状态。

代码实现：

/**
 * 动态规划求解0-1背包升级问题
 *
 * @param weight
 * @param value
 * @param n
 * @param w
 * @return
 */
public int knapsack3(int[] weight, int[] value, int n, int w) {
    int[][] states = new int[n][w + 1];
    for (int i = 0; i < n; ++i) {// 初始化states
        for (int j = 0; j < w + 1; ++j) {
            states[i][j] = -1;
        }
    }
    states[0][0] = 0;
    states[0][weight[0]] = value[0];
    for (int i = 1; i < n; ++i) { //动态规划，状态转移
        for (int j = 0; j <= w; ++j) {// 不选择第i个物品
            if (states[i - 1][j] >= 0) states[i][j] = states[i - 1][j];
        }
        for (int j = 0; j <= w - weight[i]; ++j) { // 选择第i个物品
            if (states[i - 1][j] >= 0) {
                int v = states[i - 1][j] + value[i];
                if (v > states[i][j + weight[i]]) {
                    states[i][j + weight[i]] = v;
                }
            }
        }
    }

    // 找出最大值
    int maxvalue = -1;
    for (int j = 0; j <= w; ++j) {
        if (states[n - 1][j] > maxvalue) maxvalue = states[n - 1][j];
    }
    return maxvalue;
}

时间复杂度分析：O(n*w)，同理也可以优化为一维数组。

问题解答

问题：双11有满200减50的活动，假设购物车有n个(n>100)想要买的商品，希望从里面选几个，在凑够满减条件的前提下，让选出来的商品价格总和最大程度地接近满减条件(200元) 。
1. 方式一（回溯算法思想）：对于这个问题，你当然可以利用回溯算法，穷举所有的排列组合，看大于等于200并且最接近200的组合是哪一个?但是，这样效率太低了点，时间复杂度非常高，是指数级的。
2. 方式二（动态规划）：跟第一个例子0-1背包问题很像，我们这里需要把”重量”替换为”价格”，二维数组states[n][x],那这里的x的值是多少呢？
  - 0-1背包问题中，我们找的是小于等于w的最大值，x就是背包的最大承载重量w+1。
  - 在购物问题中，我们的理论值是大于等于200（满减条件）值中最小值的。但是从实际问题出发，200块很容易就满足了，所以我们设置为1000+1
  - 在确定了x的价格维度之后，我们还需要在动态规划之后，把选中的商品都筛选出来。

代码实现：

/**
 * 描述:
 * 使用动态规划来解决双11凑单问题
 *
 * @author Noah
 * @create 2019-11-27 08:12
 */
public class _40_11_11 {

    public static void main(String[] args) {

        _40_11_11 app = new _40_11_11();
        //int[] items = new int[]{150, 100, 300, 400, 800, 50, 10, 30, 20};
        int[] items = new int[]{150, 100, 300, 400, 800};
        app.double11advance(items, items.length, 200);

    }

    /**
     * items商品价格，n商品个数, w表示满减条件，比如200
     *
     * @param items
     * @param n
     * @param w
     */
    public void double11advance(int[] items, int n, int w) {
        boolean[][] states = new boolean[n][3 * w + 1];//超过3倍就没有薅羊毛的价值了
        states[0][0] = true; // 第一行的数据要特殊处理
        states[0][items[0]] = true;
        for (int i = 1; i < n; ++i) {// 动态规划
            for (int j = 0; j <= 3 * w; ++j) {// 不购买第i个商品
                if (states[i - 1][j] == true) states[i][j] = states[i - 1][j];
            }
            for (int j = 0; j <= 3 * w - items[i]; ++j) {//购买第i个商品
                if (states[i - 1][j] == true) states[i][j + items[i]] = true;
            }
        }
        int j;
        for (j = w; j < 3 * w + 1; ++j) {
            if (states[n - 1][j] == true) break; // 输出结果大于等于w的最小值
        }
        if (j == -1) return; // 没有可行解
        for (int i = n - 1; i >= 1; --i) { // i表示二维数组中的行，j表示列
            if (j - items[i] >= 0 && states[i - 1][j - items[i]] == true) {
                System.out.print(items[i] + " "); // 购买这个商品
                j = j - items[i];
            }  //else 没有购买这个商品，j不变。
        }
        if (j != 0) System.out.print(items[0]);
    }
}

代码分析：
1. 代码的前半部分跟0-1背包问题没有什么不同，我们着重看后半部分，看它是如何打印出选择购买哪些商品的。
2. 状态(i, j)只有可能从(i-1, j)或者(i-1, j-value[i])两个状态推导过来。所以，我们就检查这两个状态是否是可达的，也就是states[i- 1][j]或者states[i-1][j-value[i]]是否是true。
3. 如果states[i-1][j]可达，就说明我们没有选择购买第i个商品，如果states[i-1][j-value[i]]可达，那就说明我们选择了购买第i个商品。我们从中选择一个可达的状态(如果两个都可达，就随意选择一个)，然后，继续迭代地考察其他商品是否有选择购买。

总结

这篇的动态规划，没有讲太多的理论知识。只是展示两个非常经典的动态规划例子，我们必须要深刻理解上面的两个例子，基本上动态规划算是入门一半了。

从上面的例子可以发现，使用动态规划来解决的问题，都可以使用回溯算法思想来解决。不过回溯算法的时间复杂度是指数级别的。而动态规划算法，在执行效率提高非常显著，但是这是在提高了空间复杂度（二维数组），所以，很多时候我们会讲：动态规划算法是空间换时间的算法思想。

个人觉得，贪心、分治、回溯、动态规划，这四个算法思想有关的理论知识，大部分都是“后验性”的，也就是说，在解决问题的过程中，我们往往是先想到如何用某个算法思想解决问题，然后才用算法理论知识，去验证这个算法思想解决问题的正确性。所以，你大可不必过于急于寻求动态规划的理论知识。

讲动态规划理论:一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题

通过前面的两个例子，我们对动态规划有了初步的认识。接下来我们要学习的动态规划的理论知识，在学习完之后。

可以帮你解决这样几个问题:什么样的问题可以用动态规划解决? 解决动态规划问题的一般思考过程是什么样的?贪心、分治、回溯、动态规划这四种算法思想又有什么区别和联系?

“一个模型三个特征”理论讲解

什么问题适合用动态规划来解决？我总结为一个模型三个特征。

什么是”一个模型”？
- 一个模型：它指的是动态规划适合解决的问题的模型，也就是多阶段决策最优解模型。
- 我们一般是用动态规划来解决最优问题。而解决问题的过程，需要经历多个决策阶段。每个决策阶段都对应着一组状态。然后我们寻找一组决策序列，经过这组决策序列，能够产生最终期望求解的最优值。
什么是”三个特征”？
- 三个特征：它们分别是最优子结构、无后效性和重复子问题。
- 最优子结构
  - 最优子结构指的是，问题的最优解包含子问题的最优解。反过来说就是，我们可以通过子问题的最优解，推导出问题的最优解。
  - 如果我们把最优子结构，对应到我们前面定义的动态规划问题模型上，那我们也可以理解为，后面阶段的状态可以通过前面阶段的状态推导出来。
- 无后效性
  - 第一层含义是，在推导后面阶段的状态的时候，我们只关心前面阶段的状态值，不关心这个状态是怎么一步一步推导出来的。
  - 第二层含义是，某阶段状态一旦确定，就不受之后阶段的决策影响。
- 重复子问题
  - 不同的决策序列，到达某个相同的阶段时，可能会产生重复的状态。

实战：n*n矩阵求解最短路径

问题描述：我们有一个n乘以n的矩阵w[n][n]。矩阵存储的都是正整数。棋子起始位置在左上⻆，终止位置在右下⻆。我们将棋子从左上⻆移动到右下⻆。每次只能向右或者向下移动一位。从左上⻆到右下⻆，会有很多不同的路径可以走。我们把每条路径经过的数字加起来看作路径的⻓度。那从左上⻆移动到右下⻆的最短路径⻓度是多少呢?
图解：
分析：这个问题是如何满足动态规划的一个模型三个特征的。公式：min_dist(i, j) = w[i][j] + min(min_dist(i, j-1), min_dist(i-1, j))

回溯算法

图解：

分析：我们要画出递归树，以此来寻找重复子问题。在递归树中，一个状态(也就是一个节点)包含三个变量(i, j, dist)，其中i，j分别表示行和列，dist表示从起点到达(i, j)的路径⻓度。从图中，我们看出，尽管(i, j, dist)不存在重复的，但是(i, j)重复的有很多。对于(i, j)重复的节点，我们只需要选择dist最小的节点，继续递归求解，其他节点就可以舍弃了。

代码实现：

/**
 * 使用回溯算法思想：穷举（搜索）所有可能的路径
 * 调用方式:minDistBacktracing(0, 0, 0, w, n);
 *
 * @param i
 * @param j
 * @param dist
 * @param w
 * @param n
 */
public void minDistBT(int i, int j, int dist, int[][] w, int n) {
    // 到达了n-1, n-1这个位置了，这里看着有点奇怪哈，你自己举个例子看下
    if (i == n && j == n) {
        if (dist < minDist) minDist = dist;
        return;
    }
    if (i < n) { // 往下走，更新i=i+1, j=j
        minDistBT(i + 1, j, dist + w[i][j], w, n);
    }
    if (j < n) { // 往右走，更新i=i, j=j+1
        minDistBT(i, j + 1, dist + w[i][j], w, n);
    }
}

动态规划算法

图解：表中的行、列表示棋子所在的位置，表中的数值表示从起点到这个位置的最短路径。我们按照决策过程，通过不断状态递推演进，将状态表填好。

代码实现

/**
 * 使用动态规划思想：解决矩阵最短路径问题（状态转义表法）
 *
 * @param matrix
 * @param n
 * @return
 */
public int minDistDP(int[][] matrix, int n) {
    int[][] states = new int[n][n];
    int sum = 0;
    for (int j = 0; j < n; ++j) { // 初始化states的第一行数据
        sum += matrix[0][j];
        states[0][j] = sum;
    }
    sum = 0;
    for (int i = 0; i < n; ++i) { // 初始化states的第一列数据
        sum += matrix[i][0];
        states[i][0] = sum;
    }
    for (int i = 1; i < n; ++i) {
        for (int j = 1; j < n; ++j) {
            states[i][j] =
                    matrix[i][j] + Math.min(states[i][j - 1], states[i - 1][j]);
        }
    }
    return states[n - 1][n - 1];
}
  
  
private int[][] matrix = {{1, 3, 5, 9}, {2, 1, 3, 4}, {5, 2, 6, 7}, {6, 8, 4, 3}};
private int n = 4;
private int[][] mem = new int[4][4];
  
/**
 * 动态规划求解：矩阵最短路径（状态转义方程法）
 * <p>
 * 方程：min_dist(i, j) = w[i][j] + min(min_dist(i, j-1), min_dist(i-1, j))
 * <p>
 * 调用minDist(n-1, n-1);
 *
 * @param i
 * @param j
 * @return
 */
public int minDist(int i, int j) {
    if (i == 0 && j == 0) return matrix[0][0];
    if (mem[i][j] > 0) return mem[i][j];
    int minLeft = Integer.MAX_VALUE;
    if (j - 1 >= 0) {
        minLeft = minDist(i, j - 1);
    }
    int minUp = Integer.MAX_VALUE;
    if (i - 1 >= 0) {
        minUp = minDist(i - 1, j);
    }
    int currMinDist = matrix[i][j] + Math.min(minLeft, minUp);
    mem[i][j] = currMinDist;
    return currMinDist;
}

两种动态规划解题思路

前面讲了什么场景适合使用动态规划来解决，现在，我们再总结动态规划解题的思路，让你有章可循。

解决动态规划问题，一般有两种思路。我把它们分别叫作，状态转移表法和状态转移方程法。

不是每个问题都同时适合这两种解题思路。有的问题可能用第一种思路更清晰，而有的问题可能用第二种思路更清晰，所以，你要结合具体的题目来看，到底选择用哪种解题思路。

状态转义表法

一般能用动态规划解决的问题，都可以使用回溯算法的暴力搜索解决。所以，当我们拿到问题的时候，我们可以先用简单的回溯算法解决，然后定义状态，每个状态表示一个节点，然后对应画出递归树。从递归树中，我们很容易可以看出来，是否存在重复子问题，以及重复子问题是如何产生的。以此来寻找规律，看是否能用动态规划解决。
找到重复子问题之后，接下来，我们有两种处理思路，第一种是直接用回溯加“备忘录”的方法，来避免重复子问题。从执行效率上来讲，这跟动态规划的解决思路没有差别。第二种是使用动态规划的解决方法，状态转移表法。第一种思路，我就不讲了，你可以看看上一节的两个例子。我们重点来看状态转移表法是如何工作的。
我们先画出一个状态表。状态表一般都是二维的，所以你可以把它想象成二维数组。其中，每个状态包含三个变量，行、列、数组值。我们根据决策的先后过程，从前往后，根据递推关系，分阶段填充状态表中的每个状态。最后，我们将这个递推填表的过程，翻译成代码，就是动态规划代码了。如果是高维（>2）数组就不适合使用状态转义表法来解决了。

状态转义方程法

状态转移方程法有点类似递归的解题思路。我们需要分析，某个问题如何通过子问题来递归求解，也就是所谓的最优子结构。根据最优子结构，写出递归公式，也就是所谓的状态转移方程。有了状态转移方程，代码实现就非常简单了。一般情况下，我们有两种代码实现方法，一种是递归加“备忘录”，另一种是迭代递推。
状态转移方程是解决动态规划的关键。

四种算法思想比较分析

总结下四种算法：贪心、分治、回溯和动态规划区别和联系。

分类：那贪心、回溯、动态规划可以归为一类，而分治单独可以作为一类，因为它跟其他三个都不大一样。为什么这么说呢?前三个算法解决问题的模型，都可以抽象成我们今天讲的那个多阶段决策最优解模型，而分治算法解决的问题尽管大部分也是最优解问题，但是，大部分都不能抽象成多阶段决策模型。
回溯算法是个“万金油”。基本上能用的动态规划、贪心解决的问题，我们都可以用回溯算法解决。回溯算法相当于穷举搜索。穷举所有的情况，然后对比得到最优解。不过，回溯算法的时间复杂度非常高，是指数级别的，只能用来解决小规模数据的问题。对于大规模数据的问题，用回溯算法解决的执行效率就很低了。
尽管动态规划比回溯算法高效，但是，并不是所有问题，都可以用动态规划来解决。能用动态规划解决的问题，需要满足三个特征，最优子结构、无后效性和重复子问题。在重复子问题这一点上，动态规划和分治算法的区分非常明显。分治算法要求分割成的子问题，不能有重复子问题，而动态规划正好相反，动态规划之所以高效，就是因为回溯算法实现中存在大量的重复子问题。
贪心算法实际上是动态规划算法的一种特殊情况。它解决问题起来更加高效，代码实现也更加简洁。不过，它可以解决的问题也更加有限。它能解决的问题需要满足三个条件，最优子结构、无后效性和贪心选择性(这里我们不怎么强调重复子问题)。其中，最优子结构、无后效性跟动态规划中的无异。“贪心选择性”的意思是，通过局部最优的选择，能产生全局的最优选择。每一个阶段，我们都选择当前看起来最优的决策，所有阶段的决策完成之后，最终由这些局部最优解构成全局最优解。

总结

我首先讲了什么样的问题适合用动态规划解决。这些问题可以总结概括为“一个模型三个特征”。其中，“一个模型”指的是，问题可以抽象成分阶段决策最优解模型。“三个特征”指的是最优子节、无后效性和重复子问题。

然后，我讲了两种动态规划的解题思路。它们分别是状态转移表法和状态转移方程法。其中，状态转移表法解题思路大致可以概括为，回溯算法实现**-定义状态-画递归树-找重复子问题-画状态转移表-根据递推关系填表-将填表过程翻译成代码。状态转移方程法的大致思路可以概括为，找最优子结构-写状态转移方程-**将状态转移方程翻译成代码。

最后，我们对比了之前讲过的四种算法思想。贪心、回溯、动态规划可以解决的问题模型类似，都可以抽象成多阶段决策最优解模型。尽管分治算法也能解决最优问题，但是大部分问题的背景都不适合抽象成多阶段决策模型。

TODO:42-讲动态规划实战:如何实现搜索引擎中的拼写纠错功能 ——47讲向量空间：如何实现一个简单的音乐推荐系统

需要去完成的事情

讲B+树:MySQL数据库索引是如何实现的

问题：数据库索引是如何实现的呢？底层使用的是什么数据结构和算法呢？

思考的过程比结论更重要

解决问题的前提是定义清楚问题

如何定义清楚问题？除了对问题进行详细的调研，还有一个办法，那就是，通过对一些模糊的需求进行假设，来限定要解决的问题的范围。

功能需求：索引是怎么实现的？所以，这里我们假设要解决的问题，只包含这样两个常用的需求:

根据某个值查找数据，比如select * from user where id=1234;

根据区间值来查找某些数据，比如select * from user where id > 1234 and id < 2345

除了这些功能性需求之外，我们着重考虑性能方面的需求。性能方面的需求，我们主要考察时间和空间两方面，也就是执行效率和存储空间。

在执行效率方面，我们希望通过索引，查询数据的效率尽可能的高;在存储空间方面，我们希望索引不要消耗太多的内存空间。

尝试用学过的数据结构解决这个问题

问题的需求大致定义清楚了，我们现在回想一下，能否利用已经学习过的数据结构解决这个问题呢?支持快速查询、插入等操作的动态数据结构，我们已经学习过散列表、平衡二叉查找树、跳表。
1. 散列表：散列表的查询性能很好，时间复杂度O(1)。但是散列表不支持按照区间快速查找数据。不满足需求。
2. 平衡二叉查找树：平衡二叉查找树的查找性能也很高，时间复杂度O(logn)。而且，对树中序遍历，我们可以得到一个从小到大的有序数据序列。但是仍然无法查找区间的值。不满足需求。
3. 跳表：跳表是在链表之上加上多层所有构成的。它支持快速插入、查找、删除数据，对应时间复杂度为O(logn)。并且，跳表也支持按照区间快速地查找数据。
跳表是可以解决这个问题。实际上，数据库索引所用到的数据结构跟跳表非常相似，叫作B+树。不过，它是通过二叉查找树演化过来的，而非跳表。所以，接下来，我还再从二叉查找树讲起，看它是如何一步一步被改造成B+树的。

改造二叉查找树来解决这个问题

为了解决二叉查找树可以满足按照区间来查找数据，我们吧二叉查找树这样更改：树中的节点不存储数据本身，而只是作为索引。除此之外，我们把每个叶子节点串在一条链表上，链表中的数据是从小到大有序的。经过改造之后的二叉树，就像图中这样，看起来是不是很像跳表呢?

改造之后，如果我们要求某个区间的数据。我们只需要拿区间的起始值，在树中进行查找，当查找到某个叶子节点之后，我们再顺着链表往后遍历，直到链表中的结点数据值大于区间的终止值为止。所有遍历到的数据，就是符合区间值的所有数据。

B+树讲解

B+树演进

经过我们改造的二叉查找树满足按照区间查找，如果我们把索引存在内存中，在内存中访问速度很快，查询效率非常高。但是占用的内存会非常大。

假设我们的一张表中有1亿数据给建立索引，那二叉查找树树当中大约会有1亿个节点，假设一个节点是16字节，那这张表的这个索引占用的内存是1G。如果有这样的10张表就使用了10G的内存空间。那如何解决这个问题呢？

我们可以借助时间换空间的思路，把索引存储在硬盘中，而非内存中。我们都知道，硬盘是一个非常慢速的存储设备。通常内存的访问速度是纳秒级别的，而磁盘访问的速度是毫秒级别的。读取同样大小的数据，从磁盘中读取花费的时间，是从内存中读取所花费时间的上万倍，甚至几十万倍。

二叉查找树，经过改造之后，支持区间查找的功能就实现了。不过，为了节省内存，如果把树存储在硬盘中，那么每个节点的读取(或者访问)，都对应一次磁盘IO操作。树的高度就等于每次查询数据时磁盘IO操作的次数。

我们前面讲到，比起内存读写操作，磁盘IO操作非常耗时，所以我们优化的重点就是尽量减少磁盘IO操作，也就是，尽量降低树的高度。那如何降低树的高度呢?

我们来看下，如果我们把索引构建成m叉树，高度是不是比二叉树要小呢?如图所示，给16个数据构建二叉树索引，树的高度是4，查找一个数据，就需要4个磁盘IO操作(如果根节点存储在内存中，其他结点存储在磁盘中)，如果对16个数据构建五叉树索引，那高度只有2，查找一个数据，对应只需要2次磁盘操作。如果m叉树中的m是100，那对一亿个数据构建索引，树的高度也只是3，最多只要3次磁盘IO就能获取到数据。磁盘IO变少了，查找数据的效率也就提高了。

B+树实现

/**
 * 描述:
 * b+树实现：改进版本的二叉查找树
 * <p>
 * 如果我们将m叉树实现B+树索引，用代码实现出来，就是下面这个样子(假设我们给int类型的数据库字段添加索引，所以代 码中的keywords是int类型的):
 *
 * @author Noah
 * @create 2019-11-28 09:09
 */
public class _48_BPlus_Tree {

    /**
     * 这是B+树非叶子节点的定义。
     * <p>
     * 假设keywords=[3, 5, 8, 10]
     * 4个键值将数据分为5个区间:(-INF,3), [3,5), [5,8), [8,10), [10,INF)
     * 5个区间分别对应:children[0]...children[4]
     * <p>
     * m值是事先计算得到的，计算的依据是让所有信息的大小正好等于⻚的大小:
     * PAGE_SIZE = (m-1)*4[keywordss大小]+m*8[children大小]
     */
    public class BPlusTreeNode {
        public int m = 5; // 5叉树
        public int[] keywords = new int[m - 1]; // 键值，用来划分数据区间
        public BPlusTreeNode[] children = new BPlusTreeNode[m];//保存子节点指针
    }

    /**
     * 这是B+树中叶子节点的定义。
     * <p>
     * B+树中的叶子节点跟内部结点是不一样的,
     * 叶子节点存储的是值，而非区间。
     * 这个定义里，每个叶子节点存储3个数据行的键值及地址信息。
     * <p>
     * k值是事先计算得到的，计算的依据是让所有信息的大小正好等于⻚的大小:
     * PAGE_SIZE = k*4[keyw..大小]+k*8[dataAd..大小]+8[prev大小]+8[next大小]
     */
    public class BPlusTreeLeafNode {
        public int k = 3;
        public int[] keywords = new int[k]; // 数据的键值
        public long[] dataAddress = new long[k]; // 数据地址
        public BPlusTreeLeafNode prev; // 这个结点在链表中的前驱结点
        public BPlusTreeLeafNode next; // 这个结点在链表中的后继结点
    }
}

解释一波上面的代码：

对于相同个数的数据构建m叉树索引，m叉树中的m越大，那树的高度就越小，那m叉树中的m是不是越大越好呢?到底多大才最合适呢?

不管是内存中的数据，还是磁盘中的数据，操作系统都是按⻚(一⻚大小通常是4KB，这个值可以通过getconfig PAGE_SIZE 命令查看)来读取的，一次会读一⻚的数据。如果要读取的数据量超过一⻚的大小，就会触发多次IO操作。所以，我们在选择 m大小的时候，要尽量让每个节点的大小等于一个⻚的大小。读取一个节点，只需要一次磁盘IO操作。

图解B+树实现：

B+树的弊

尽管索引可以提高数据库的查询效率，但是索引有利也有弊，它让写入/更新数据的效率下降，这是为什么呢？

对于一个B+树来说，m值是根据⻚的大小事先计算好的，也就是说，每个节点最多只能有m个子节点。在往数据库中写入数据的过程中，这样就有可能使索引中某些节点的子节点个数超过m，这个节点的大小超过了一个⻚的大小，读取这样一个节点，就会导致多次磁盘IO操作。我们该如何解决这个问题呢?

实际上，处理思路并不复杂。我们只需要将这个节点分裂成两个节点。但是，节点分裂之后，其上层父节点的子节点个数就有可能超过m个。不过这也没关系，我们可以用同样的方法，将父节点也分裂成两个节点。这种级联反应会从下往上，一直影响到根节点。这个分裂过程，你可以结合着下面这个图一块看，会更容易理解(图中的B+树是一个三叉树。我们限定叶子节点中，数据的个数超过2个就分裂节点;非叶子节点中，子节点的个数超过3个就分裂节点)。

正是因为要时刻保证B+树索引是一个m叉树，所以，索引的存在会导致数据库写入的速度降低。实际上，不光写入数据会变慢，删除数据也会变慢。这是为什么呢?

我们可以设置一个阈值。在B+树中，这个阈值等于m/2。如果某个节点的子节点个数小于m/2，我们就将它跟相邻的兄弟节点合并。不过，合并之后结点的子节点个数有可能会超过m。针对这种情况，我们可以借助插入数据时候的处理方法，再分裂节点。

总结

今天我们梳理了B+树是如何实现索引的，底层依赖的数据结构是B+树。B+树通过存储在磁盘的多叉查找树结构，做到时间、空间的平衡，既保证了执行效率，又节省了内存。

上面是一步步介绍B+树的由来，比较零散。这里再总结一下B+树的特点。

m叉查找树=B+树，m是通过计算得到的，为了刚好一个节点存储的最大内存大小不超过”一页”的大小。
每个节点中子节点的个数不能超过m，也不能小于m/2
根节点的子节点个数可以不超过m/2，这是一个例外。
m叉树只存储索引，并不真正存储数据，有点类似跳表。
通过链表将叶子节点串联在一起，这样实现区间查找。
一般情况，根节点存储会被存储在内存中，其他节点存储在磁盘中。

除了B+树，你可能还听说过B树、B-树，我这里简单提一下。实际上，B-树就是B树，英文翻译都是B-Tree，这里的“-”并不是相对B+树中的“+”，而只是一个连接符。这个很容易误解，所以我强调下。

而B树实际上是低级版的B+树，或者说B+树是B树的改进版。B树跟B+树的不同点主要集中在这几个地方:

B+树中的节点不存储数据，只是索引，而B树中的节点存储数据。
B树中叶子节点并不需要链表来串联。
也就是说，B树只是一个每个节点的子节点个数不能小于m/2的m叉树。

TODO：49讲搜索：如何用A搜索算法实现游戏中的寻路功能

需要去完成的事情

讲索引：如何在海量数据中快速查找某个数据

我们在前面讲解了，Mysql的索引底层是依赖B+树这种数据结构。类似 Redis这样的Key-Value数据库中的索引，又是怎么实现的呢?底层依赖的又是什么数据结构呢?

为什么需要索引？

在软件开发中，业务纷繁复杂，功能千变万化，但是，万变不离其宗。如果抛开这些业务和功能的外壳，其实它们的本质都可以抽象为“对数据的存储和计算”。对应到数据结构和算法中，那“存储”需要的就是数据结构，“计算”需要的就是算法。

对于存储的需求，功能上无外乎增删改查。这其实并不复杂。但是，一旦存储的数据很多，那性能就成了这些系统要关注的重点。“如何节省存储空间、如何提高数据增删改查的执行效率”，这样的问题就成了设计的重点。而这些系统的实现，都离不开一个东⻄，那就是索引。不夸张地说，索引设计得好坏，直接决定了这些系统是否优秀。

索引这个概念，非常好理解。你可以类比书籍的目录来理解。如果没有目录，我们想要查找某个知识点的时候，就要一⻚一⻚翻。通过目录，我们就可以快速定位相关知识点的⻚数，查找的速度也会有质的提高。

索引的需求定义

对于系统设计需求，我们一般可以分为功能性需求和非功能性需求两个方面分析。

功能性需求

数据是格式化数据还是非格式化数据？
- 要构建索引的原始数据，类型有很多。我把它分为两类，一类是结构化数据，比如，MySQL中的数据;另一类是非结构化数据，比如搜索引擎中网⻚。对于非结构化数据，我们一般需要做预处理，提取出查询关键词，对关键词构建索引。
数据是静态数据还是动态数据？
- 如果原始数据是一组静态数据，也就是说，不会有数据的增加、删除、更新操作，所以，我们在构建索引的时候，只需要考虑查询效率就可以了。这样，索引的构建就相对简单些。不过，大部分情况下，我们都是对动态数据构建索引，也就是说，我们不仅要考虑到索引的查询效率，在原始数据更新的同时，我们还需要动态地更新索引。支持动态数据集合的索引，设计起来相对也要更加复杂些。
索引存储在内存还是硬盘中？
- 如果索引存储在内存中，那查询的速度肯定要比存储在磁盘中的高。但是，如果原始数据量很大的情况下，对应的索引可能也会很大。这个时候，因为内存有限，我们可能就不得不将索引存储在磁盘中了。实际上，还有第三种情况，那就是一部分存储在内存，一部分存储在磁盘，这样就可以兼顾内存消耗和查询效率。
单值查找还是区间查找？
- 所谓单值查找，也就是根据查询关键词等于某个值的数据。这种查询需求最常⻅。所谓区间查找，就是查找关键词处于某个区间值的所有数据。你可以类比MySQL数据库的查询需求，自己想象一下。实际上，不同的应用场景，查询的需求会多种多样。
单关键词查找还是多关键词组合查找？
- 比如，搜索引擎中构建的索引，既要支持一个关键词的查找，比如“数据结构”，也要支持组合关键词查找，比如“数据结构 AND 算法”。对于单关键词的查找，索引构建起来相对简单些。对于多关键词查询来说，要分多种情况。像MySQL这种结构化数据的查询需求，我们可以实现针对多个关键词的组合，建立索引;对于像搜索引擎这样的非结构数据的查询需求，我们可以针对单个关键词构建索引，然后通过集合操作，比如求并集、求交集等，计算出多个关键词组合的查询结果。
实际上，不同的场景，不同的原始数据，对于索引的需求也会千差万别。我这里只列举了一些比较有共性的需求。

非功能性需求

不管是存储在内存中还是磁盘中，索引对存储空间的消耗不能过大。
在考虑索引查询效率的同时，我们还要考虑索引的维护成本。

构建索引常用的数据结构有哪些

我刚刚从很宏观的⻆度，总结了在索引设计的过程中，需要考虑的一些共性因素。现在，我们就来看，对于不同需求的索引结构，底层一般使用哪种数据结构。

实际上，常用来构建索引的数据结构，就是我们之前讲过的几种支持动态数据集合的数据结构。比如，散列表、红黑树、跳表、B+树。除此之外，位图、布隆过滤器可以作为辅助索引，有序数组可以用来对静态数据构建索引。

散列表：crud的性能非常好，时间复杂度是O(1)。一些键值数据库，比如Redis、Memcache。存储在内存中。
红黑树：近似平衡二叉查找树，crud的时间复杂度是O(logn)。在Ext文件系统中，内存索引。
B+树：和红黑树比较的话，更加适合构建存储在磁盘中的索引。B+树是一个M叉树，所以，对相同个数的数据构建索引，B+树的高度要低于红黑树。当借助索引查询数据的时候，读取B+树索引，需要的磁盘IO次数非常更少。大部分关系型数据库的索引，都是使用B+树实现的。
跳表：crud的时间复杂度为O(logn)。我们通过灵活调整索引结点个数和数据个数之间的比例，可以很好地平衡索引对内存的消耗及其查询效率。Redis中的有序集合，就是用跳表来构建的。
布隆过滤器 ：对数据的判定有一定的判错率。但是我可以扬长避短。判定存在的数据，可能不存在，但是判定不存在数据，那就肯定不存在。
- 布隆过滤器最大的特点：占用内存非常少。
- 优化思路：在内存中构建一个布隆过滤器，当查询数据的时候，会先通过内存的布隆过滤器，如果布隆过滤器判断不存在，那不用到磁盘去读取数据了。

讲并行算法：如何利用并行处理提高算法的执行效率

算法的目的就是为了提高代码执行的效率，**当算法无法再继续优化的情况下，我们该如何来进一步提高执行效率呢?**我们今天就讲一种非常简单但又非常好用的优化方法，那就是并行计算。

如何借助并行计算的处理思想对算法进行改造?

并行排序

问题：假设我们要给大小为8GB的数据进行排序，并且，我们机器的内存可以一次性容纳这么多数据。对于排序来说，最常用的就是时间复杂度为O(nlogn)的三种排序算法，归并排序、快速排序、堆排序。从理论上讲，这个排序问题，已经很难再从算法层面优化了。而利用并行的处理思想，我们可以很轻松地将这个给8GB数据排序问题的执行效率提高很多倍。具体的实现思路有下面两种。

第一种是对归并排序并行化处理 ：我们可以将这8GB的数据划分成16个小的数据集合，每个集合包含500MB的数据。我们用 16个线程，并行地对这16个500MB的数据集合进行排序。这16个小集合分别排序完成之后，我们再将这16个有序集合合并。
第二种是对快速排序并行化处理 ：我们通过扫描一遍数据，找到数据所处的范围区间。我们把这个区间从小到大划分成16个小区间。我们将8GB的数据划分到对应的区间中。针对这16个小区间的数据，我们启动16个线程，并行地进行排序。等到16 个线程都执行结束之后，得到的数据就是有序数据了。

对比这两种处理思路，它们利用的都是分治的思想，对数据进行分片，然后并行处理。它们的区别在于，第一种处理思路是，先随意地对数据分片，排序之后再合并。第二种处理思路是，先对数据按照大小划分区间，然后再排序，排完序就不需要再处理了。这个跟归并和快排的区别如出一辙。

如果要排序的数据规模不是8GB，而是1TB，那问题的重点就不是算法的执行效率了，而是数据的读取效率。因为1TB的数据肯定是存在硬盘中，无法一次性读取到内存中，这样在排序的过程中，就会有频繁地磁盘数据的读取和写入。如何减少磁盘的IO操作，减少磁盘数据读取和写入的总量，就变成了优化的重点。

并行查找

散列表是一种非常适合快速查找的数据结构。下面的解决方案就是一致性哈希算法。

问题描述：如果我们是给动态数据构建索引，在数据不断加入的时候，散列表的装载因子就会越来越大。为了保证散列表性能不下降，我们就需要对散列表进行动态扩容。对如此大的散列表进行动态扩容，一方面比较耗时，另一方面比较消耗内存。比如，我们给一个2GB大小的散列表进行扩容，扩展到原来的1.5倍，也就是3GB大小。这个时候，实际存储在散列表中的数据只有不到 2GB，所以内存的利用率只有60%，有1GB的内存是空闲的。

解决方案：实际上，我们可以将数据随机分割成k份(比如16份)，每份中的数据只有原来的1/k，然后我们针对这k个小数据集合分别构建散列表。这样，散列表的维护成本就变低了。当某个小散列表的装载因子过大的时候，我们可以单独对这个散列表进行扩容，而其他散列表不需要进行扩容。

成果：还是刚才那个例子，假设现在有2GB的数据，我们放到16个散列表中，每个散列表中的数据大约是150MB。当某个散列表需要扩容的时候，我们只需要额外增加150*0.5=75MB的内存(假设还是扩容到原来的1.5倍)。不管从扩容的执行效率还是内存的利用率上，这种多个小散列表的处理方法，都要比大散列表高效。

当我们要查找某个数据的时候，我们只需要通过16个线程，并行地在这16个散列表中查找数据。这样的查找性能，比起一个大散列表的做法，也并不会下降，反倒有可能提高。

并行字符串匹配

我们前面学过，在文本中查找某个关键词这样一个功能，可以通过字符串匹配算法来实现。我们之前学过的字符串匹配算法有 KMP、BM、RK、BF等。当在一个不是很⻓的文本中查找关键词的时候，这些字符串匹配算法中的任何一个，都可以表现得非常高效。但是，如果我们处理的是超级大的文本，那处理的时间可能就会变得很⻓，那有没有办法加快匹配速度呢?

我们可以把大的文本，分割成k个小文本。假设k是16，我们就启动16个线程，并行地在这16个小文本中查找关键词，这样整个查找的性能就提高了16倍。16倍效率的提升，从理论的⻆度来说并不多。但是，对于真实的软件开发来说，这显然是一个非常可观的优化。

并行搜索

广度优先搜索算法，我们需要利用两个队列来完成扩展顶点的工作。

假设这两个队列分别是队列A和队列B。多线程并行处理队列A中的顶点，并将扩展得到的顶点存储在队列B中。等队列A中的顶点都扩展完成之后，队列A被清空，我们再并行地扩展队列B中的顶点，并将扩展出来的顶点存储在队列A。这样两个队列循环使用，就可以实现并行广度优先搜索算法。

讲算法实战（一）：剖析Redis常用数据类型对应的数据结构

在结束了我们的基础篇（数据结构）和高级篇（算法）之后，我们现在正式进入我们的实战篇。

看看开源项目、经典系统是如何使用数据结构和算法的。

问题：经典数据库Redis中的常用数据类型，底层都是用哪种数据结构实现的?

Redis数据库介绍

Redis是一种键值（Key-Value）数据库，也被称为非关系型数据库。具有下面的特点：

由于Redis只包含键和值，只能通过”键”来查询”值”。正是因为这样简单的存储结构，让Redis的读写效率很高。
Redis是内存数据库，效率高。也可以将内存的的数据落盘到磁盘。
Redis的键的数据类型是字符串，但是值的数据类型有：字符串、列表、字典、集合、有序集合。

字符串

省略

列表（list）

列表这种数据类型支持存储一组数据。有两种实现方法，一种是压缩列表，另外一种是双向循环列表。

当列表中存储的数据量比较小的时候，列表采用压缩列表的方式实现。具体满足下面两个条件

列表中保存的单个数据小于64字节
列表中数据个数少于512个

压缩列表

压缩列表不是基础数据结构，而是redis自己设计的一种数据存储结构。它有点儿类似数组，通过一片连续的内存空间，来存储数据。不过，它跟数组不同的一点是，它允许存储的数据大小/类型不同。

如何理解”压缩”二字？

压缩：直观的反应就是这种存储结构节省内存。压缩列表和数组存储的思路不同，数组要求每个元素的大小类型相同，那数组就会取最大元素的长度作为每个元素的长度，假设最长的是20字节，但是大多数元素才4字节。就浪费了很多存储空间。而压缩列表并不这样要求。
压缩列表这种存储结构，一方面比较节省内存，另一方面可以支持不同类型数据的存储。而且，因为数据存储在一片连续的内存空间，通过键来获取值为列表类型的数据，读取的效率也非常高。

当列表中存储的数据量比较大的时候，也就是刚才那两个条件不满足的时候，列表就要通过双向循环链表实现了。

参考C语言的列表中。

// 以下是C语言代码，因为Redis是用C语言实现的。 
typedef struct listnode {
	struct listNode *prev; 
	struct listNode *next; 
	void *value;
} listNode;

typedef struct list { 
	listNode *head; 
	listNode *tail; 
	unsigned long len; 
	// ....省略其他定义
} list;

字典（hash）

字典类型用来存储一组数据对，每个数据对又包含键值两部分。字典类型也有两种实现方式。一种是压缩列表，另一种是散列表。

Redis使用压缩列表实现字典，需要满足以下两个条件：

字典中保存的键和值的大小都要小于64字节。
字典中键值对的个数小于512个。

如果不能满足上面两个条件的时候，Redis就使用散列表来实现字典类型。Redis使用MurmurHash2这种运行速度快、随机性好的哈希算法作为哈希函数。对于哈希冲突问题，Redis使用链表法来解决。除此之外，Redis还支持散列表的动态扩容、缩容。

当数据动态增加之后，散列表的装载因子会不停地变大。为了避免散列表性能的下降，当装载因子大于1的时候，Redis会触发扩容，将散列表扩大为原来大小的2倍左右。

当数据动态减少之后，为了节省内存，当装载因子小于0.1的时候，Redis就会触发缩容，缩小为字典中数据个数的大约2倍大小。

前面我们提到过，扩容或者缩容要做大量的数据搬迁和哈希值重新计算，比较耗时，Redis使用的机制就是我们前面讲过的渐进式扩容缩容策略，将数据的搬移分批完成，避免大量数据一次性搬移导致服务停顿。

集合（set）

集合这种数据类型用来存储一组不重复的数据。这种数据类型也有两种实现方法，一种是基于有序数组，另一种是基于散列表。

Redis的集合使用有序数组存储的两个条件

存储的数据都是整数。
存储的数据元素个数不超过512个。

有序集合（sortedSet）

有序集合是基于跳表的实现，它用来存储一组数据，并且每个数据都有附带一个得分。通过得分的大小，我们将数据组织成跳表这样的数据结构，以支持快速地按照得分值、得分区间获取数据。

当数据量比较小时，有序集合的实现方式还有压缩列表，需要满足下面两个条件

所有数据的大小都小于64字节。
元素个数要小于128个。

数据结构持久化

尽管Redis经常会被用作内存数据库，但是，它也支持数据落盘，也就是将内存中的数据存储到硬盘中。这样，当机器断电的时候，存储在Redis中的数据也不会丢失。在机器重新启动之后，Redis只需要再将存储在硬盘中的数据，重新读取到内存，就可以继续工作了。

如何把内存的数据落盘到数据库。实际上，Redis遇到的这个问题并不特殊，很多场景中都会遇到。我们把它叫作数据结构的持久化问题，或者对象的持久化问题。这里的“持久化”，你可以笼统地可以理解为“存储到磁盘”。

把数据结构持久化到硬盘，主要有两种解决思路。

第一种是清除原有的存储结构，只将数据存储到磁盘中。当我们需要从磁盘还原数据到内存的时候，再重新将数据组织成原来的数据结构。实际上，Redis采用的就是这种持久化思路。但是耗时。
第二种方式是保留原来的存储格式，将数据按照原有的格式存储在磁盘中。我们拿散列表这样的数据结构来举例。我们可以将散列表的大小、每个数据被散列到的槽的编号等信息，都保存在磁盘中。有了这些信息，我们从磁盘中将数据还原到内存中的时候，就可以避免重新计算哈希值。

总结

Redis常用数据类型底层依赖的数据结构，总结下这五大类：压缩列表（特殊数组）、有序数组、链表、散列表、跳表。