刘浒的个人博客

二分查找

二分查找可以实现 O(logn) 的时间复杂度，直观一点说，2 的 32 次方，大概 42 亿，最多需要比较 32 次就可以查找到数据。二分查找的原理就是，每次都将数据一分为二，通过被查找元素和中间的元素对比，判定下次查找是在中点的左边还是右边，即将待查找的区间缩小为之前的一半，直到找到要查找的元素。

使用二分查找的约束条件

• 依赖数组
  • 二分查找需要按照下标随机访问首、尾、中间的元素所以需要数组，如果基于链表实现，时间复杂度会从 O(logn) 退化成 O(n) 的
  • 因为是基于数组的，所以内存空间是连续的，大数据量的情况下可能会没有那么大连续内存
• 数据是有序的
  • 数据必须是有序的，如果数据没有序，首先需要先排序
  • 适用于查多改少的场景，因为要维护数据的有序性，插入、删除操作的复杂度会很高

代码模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14

public int binarySearch(int[] array, int target) {
    int left = 0, right = array.length - 1, mid;
    while (left <= right) {
        mid = (right - left) / 2 + left;
        if (array[mid] == target) {
            return mid;
        } else if (array[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

变体问题

• 有序数据集合中存在重复的数据，找到 第一个 / 最后一个 等于给定值的数据
• 搜索旋转排序数组

总结

本周的学习内容还包含 DFS、BFS 这个两个已经老生常谈的算法了。我们之前在练习二叉树的前、中、后序遍历的时候就是深度遍历，全排列、组合、子集、生成括号等回溯算法解决问题的时候也是深度优先遍历。练习二叉树层序遍历、全排列、岛屿数量可以用广度优先解决，有时候用广度优先能解决的问题用深度优先也可以解决，因为在深度优先遍历的时候，我们是知道遍历的深度 level 的。通常情况下，用迭代法解决深度优先遍历会用到 栈 ，因为栈可以方便我们回溯到上个节点继续遍历。迭代法解决广度优先遍历会用到 队列，我们将每一层的节点入队，并遍历 poll 出当前层的所有节点，依次处理，如果处理的当前层的节点还有下层节点，再次入队，往复处理直到队列为空。

关于贪心算法，打算在下下周学完动态规划一起总结，这个是继 分治 、回溯 后的最后两个算法思想。全部学完后，可以比较一下它们的异同，解决问题的适用范围。

二分查找可以实现 O(logn) 的时间复杂度，但是这个是有前提的。首要需要使用数组保持数据，即可随机访问、内存连续的；其次数据要是有序的，所以插入、删除数据时，为了保持有序需要付出额外的代价，或者说需要对数据进行排序，也就是说二分查找比较适查多写少的场景。最后要理解记忆二分查找的代码模板，能够用二分查找解决一些变体情况。

递归

递归，去的过程叫“递”，回的过程叫“归”。能够用递归解决的问题都需要满足如下几个条件：

• 存在递归终止条件
• 一个问题可以分解为多个子问题
• 问题和子问题，除了处了的数据规模不同，解决思路完全相同

我们需要找到将大问题分解为小问题的规律，并且基于此写抽象成一个递推公式，这个过程要注意，不要试图用人脑去分解递归的每个步骤，只要考虑当前层的逻辑。

使用递归还要注意重复计算问题，可以使用字典表缓存已经计算的结果。比方说爬楼梯问题暴力递归的时间复杂度是 O(2^n) ，在使用缓存之后时间复杂度就是 O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

/**
 * 递归代码模板
 **/
public void recur(int level, int param) {
    // 终结者 
    if (level > MAX_LEVEL) {
        // process result
        return; 
    }

    // 当前层逻辑
    process(level, param);

    // 下一层
    recur(level + 1, newParam);

    // 重置当前状态
}

分治

分治就是“分而治之”，将原问题划分成 n 个规模较小而结构与原问题相似的子问题，递归地解决这些子问题，然后再合并其结果，就得到原问题的解。用分治思想解决问题需要具有如下条件：

• 原问题与分解成的小问题具有相同的模式

• 原问题分解成的子问题可以独立求解，子问题之间没有相关性不会相互影响

• 具有分解终止条件，也就是说，当问题足够小时，可以直接求解

• 可以将子问题合并成原问题，但合并操作的复杂度不能太高，否则算法总体复杂度无法减小分

分治思想的代码包括 3 个步骤，分解、解决、合并：

• 分解：将原问题分解为一系列子问题

• 解决：递归地求解各个子问题，若子问题足够小，则直接求解

• 合并：将子问题的结果合并成原问题的解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

/**
 * 分治代码模板
 * 求多数元素
 **/
private int majorityElementRec(int[] nums, int low, int high) {
    // Step1: 最小子问题, 可直接得出结果, 也是递归终止条件
    // 这里就是将数组分解成只有一个元素
    if (low == high) {
        return nums[low];
    }

    // Step2: 准备数据
    // 这里将数据一切为二
    int mid = (high - low) / 2 + low;

    // Step3: 问题分解并求出子问题
    // 这里是分别求出左多数和右多数
    int left = majorityElementRec(nums, low, mid);
    int right = majorityElementRec(nums, mid + 1, high);

    // Step4: 合并结果, 得出最终结果
    // 这里是返回左右两边数量最多的数
    if (left == right) {
        return left;
    }
    int leftCount = countInRange(nums, left, low, high);
    int rightCount = countInRange(nums, right, low, high);
    return leftCount > rightCount ? left : right;
  
    // Step5: 恢复状态
}

回溯

回溯就是采用试错的思想，从一组可能的解中，选择出一个满足要求的解。

• 穷举所有的解，找到满足要求的解
  • 通过将问题分解为多个阶段（步骤），来穷举所有的可能解
  • 通过尝试发现当前的阶段的答案不能得到正确的解，将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的解
• 利用剪枝操作，排除不需要穷举的情况，从而提高效率

总结

递归是解决问题一种手段属于编程技巧，而分治、回溯、贪心算法、动态规划属于算法思想。他们的关键是都是要找到问题的重复性。

分治思想的核心就是分而治之。在工程实践中 MapRedue 的本质就是分治，比方说 Spark 解决单机节点性能问题，将任务拆分到多个机器上处理，子任务之间互不干扰独立计算，最后再将合并结果。

回溯相当于穷举所有的情况，然后对比得到最优解。回溯算法的时间复杂度非常高，是指数级别。可以利用剪枝操作，排除不需要的分支，从而提高效率。

本周的算法思想并不难理解，关键是解决问题的时候能够找出问题的重复性，并且能够分解出子问题。“思想”总是高度抽象，想要灵活运用还是要多多练习这类的题目。

哈希表

哈希表的本质就用数组支持按照下标随机访问的特性，实现查找、删除、插入数据的时间复杂度为 O(1) 。哈希函数就是将 Key 转换为数组下标，将数据存放到指定位置。

而 哈希函数的本质就是取余操作，能将任何 Key，转换为有限范围内的一个数值。比方说任意大的正整数对 5 取余那么结果就是在 [0, 4] 。同理著名的 MD5 哈希函数，对任意长度的输入，其输出都是 128 bit，即 16 字节。

JDK 中 HashMap 将 Key 映射到哈希表数组下标方法是 tab[i = (n - 1) & hash] ，其实就是 tab[i = hash % n] ，tab 就存放数据的数组 table ，hash = key.hashCode() ^ (key.hashCode() >>> 16) 就 Key 的哈希值，n 就是哈希表的数组长度，翻译过来就是将 key 的哈希值对数组长度 - 1进行取余，结果作为数组下标存放数据。

由于数组的存储空间有限，很容易产生哈希碰撞，即不同的 Key 哈希出的数据下标是一样的，如果直接将数据存入数组中，会导致数据存储丢失。HashMap 中将数组称作为 bucket array（桶数组）， 每个桶都会对应一条链表，将哈希值相同的元素都放到相同桶对应的链表中，来解决 Hash 碰撞的问题。

哈希表存放数据的位置完全是根据哈希函数的计算来的，所以数据的存放是无序的。即使在 LinkedHashMap 中通过双向链表，实现插入的顺序、或访问的 LRU， 但是还是无法做到对数据的排序，直观一点说就是无法直接获取 “> n” 的数据。

二叉树

树是在数组或链表的基础上赋予了节点位置信息，所谓的升维思想。

几种特殊的二叉树：

• 在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值，这就是二叉搜索树；

• 叶子节点全都在最底层，除了叶子节点之外，每个节点都有左右两个子节点，这就是满二叉树；

• 如果满二叉树，叶子节点虽然没有排满，但是叶子节点都靠左排列，这就是完全二叉树；

• 约束完全二叉树每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值，这就是堆。

二叉树的遍历

二叉树的遍历分为前序遍历、中序遍历、后序遍历这些都属于深度优先（DFS），层次遍历属于广度优先（BFS）。在 LeetCode 上这几种遍历题目都有，树的遍历递归写法最为清晰明了，栈的写法比较容易写废，我刷了 3 遍，才写熟练。为了方便理解，我把几种遍历的栈图画出来了，方便理解。

前序遍历

中序遍历

后序遍历

堆

堆是一种特殊的二叉树 - 完全二叉树。在上周的课程，课后作业分析 PriorityQueue 其实就带着学习了堆的特性。以小顶堆为例子，查找最小是 O(1)、删除最小是 O(logn)，插入是 O(logn) 或是 O(1)。在堆中插入、删除数据为了维护最小元素在堆顶，分别涉及上浮、下沉的元素交换操作。

堆的应用场景有优先级队列，比方说 JDK 中的 PriorityQueue 。利用优先级队列我们可以解决 K 个有序数列合并 问题，将数列全部加入堆中，再依次取出即可。如果是将 K 个小文件合并成一个大文件，且内存中无法存放全部结果，可以依次从 K 个文件读取并删除第一个元素并放入堆中，然后取出堆顶的元素，放入合并文件中，再找到刚才堆顶元素对应的文件，读取并删除下一个元素，放入堆中，直到堆中无任何元素，合并任务就完成了。优先级队列还有个场景就是 延时/定时任务队列 ，我们可以维护一个小顶堆，将到期时间早的放在堆顶，定时检查堆顶元素就可以知道整个队列有没有任务到期，避免了对整个队列的轮询检查，提高了性能。

堆还常用于解决 Top K 问题，根据不同的场景用大顶堆或小顶堆，并保证堆的大小为 K，Top K 就是堆中所有的元素。

总结

这两周的学习，发现数据的存储结构只有两种：数组、链表，他们就是构成计算机数据结构的 “基本粒子”，其他的数据结构只是在其基础上演进。栈、队列、哈希表、树、图底层实现都是数组或链表，或者两者都可以实现。

升维的本质就是给数据的位置增加特殊的位置含义。比方说，树用数组存放，当根的数组下标是 i (i > 0) ，那么左孩子的下标就是 i * 2，右孩子的下标就是 i * 2 + 1 。

哈希表已经能做到对数据的查找、删除、插入 O(1) 的时间复杂度了，但是数据存储是无序的，不支持有序输出。如果使用二叉搜索树，我们只需要中序遍历，就是序输出了。

当向二叉搜索树有序插入一堆数据时候，二叉搜索树就会显得极度不平衡，退化成了链表，查找从 O(logn) 退化为 O(n)，所以又有了平衡二叉查找树 - 红黑树，它能够始终保持在 O(logn) 。

二叉搜索树和堆又有什么关系呢？我们通过对二叉搜索树的中序列遍历可以得到一个有序序列，堆可以通过不断的从堆顶 poll 数据得到一个有序序列，这就是的堆排序；二叉搜索树会有退化不平衡的现象，而堆却不会；二叉搜索树获取最大或最小值都是 O(logn) ，但堆需要根据是大顶堆还是小顶堆才能获取最大值、还是最小值并且时间复杂是 O(1) 。

本周的时间实在是不够用的，关于堆、图的题目都还没有练习，下周的课程又开始了，要再加加油了～～