刘浒的个人博客

本周主要学习了一维数据结构，这里总结一下每种数据结构它的特性。

数组

数组将固定数量的、数据结构相同的数据存储在一段连续的内存空间上。为什么会有这些限定条件呢？

因为有了这些限定条件，就可以推导出数组的内存地址公式 a[k]_address = base_address + k * type_size ， 这样我们就可以根据数组下标随机访问数组的任意元素了。

那么想想看下面的 Java 代码数组是如何寻址的呢？

1
2
3
4

Object[] items = new Object[10];
items[0] = Arrays.asList("1", "2");
items[1] = "123";
items[2] = 123;

另外数组的随机访问和数据查找是两回事。数组随机访问的时间复杂度 O(1)，但查找并不是 ，比如遍历数组查找时间复杂度就是 O(n)，对排列好的数组用二分查找就是 O(logn) 。数组这个随机访问的特性非常重要，比如后面我们要学习的 Hash 表，就充分利用了这种特性。

链表

链表在数组的基础上解放了申请连续的内存空间的限制。单链表定义，数据 + 下个 Node 的地址构成一个 Node 的方式，使得数据逻辑上连续，形成链式结构。

以单链表举例，这样带来的弊端是，我们必须知道上个节点的，才能访问到下个节点，也就是说丧失了随机访问的能力，我们必须从头遍历链表，访问数据的时间复杂度为 O(n) 。好处是添加、删除数据没有数据搬移的操作，时间复杂的都 O(1)。 但是我们一般操作数据都是先查找数据，再进行操作，这个就 O(n) 的时间复杂度了。而且单链表操作根复杂，如果我们已知要删除某个节点，为了保证链表的连续性，必须还要知道链表的前驱节点，所以要遍历一次链表才知道。为了解决这样的问题，我们定义双向链表的节点是， 上个 Node 的地址 + 数据 + 下个 Node 的地址，这样我们的节点天然知道前驱、后继的节点，在已知操作节点的时候，插入新节点、删除该节点时间的复杂度就为 O(1) 了。 JDK 中 LinkedList 就是用双向链表实现的，我想也是利用空间换时间的思想，实现操作的高效吧。

跳表

跳表其实就是在链表的基础上加 N 阶索引，目的是为了降低链表查找数据的时间复杂度，由 O(n) 降级到 O(logn) 。其实跳表就是为了解决链表因为没有数组的随机访问特性，无法支持二分查找，使用空间换时间的思想，为链表添加 N 阶索引，使得链表支持二分查找。

跳表因为它原理简单、实现比红黑树更容易，插入、删除、搜索时间复杂度都是 O(logn) 。所以 Redis、LevelDB 都是用了跳表作为数据结构。

栈

栈是一个操作受限的一维数据结构，可以用数组实现、也可以用链表实现，只要保证只能在数据的一端操作，保证 LIFO 特性就可以了。入栈、出栈时间复杂度都是 O(1)。

这主要说说应用，他们都符合后进先出的场景：

• 函数调用
• 括号匹配
• 浏览器前进后退功能

队列

是一个操作受限的一维数据结构，可以用数组实现、也可以用链表实现，保证只能在数据的一端插入数据，另一段读取并删除数据，保证 FIFO 特性。

用数组实现队列的时候，要维护 head 和 tail 在数据中的索引位置，当多次入队、出队之后，head 和 tail 都会持续往后移动，当 tail 移动到最后，即使数组有空间，也无法添加数据了。为了解决这样的问题，我们在入队的时候要检查队列是否是真的满了，如果未满则要进行数据搬移。

在 JDK 源码中 ArrayDeque 处理队列满的实现，也进行了数据的搬移：

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

private void doubleCapacity() {
    assert head == tail;
    int p = head;
    int n = elements.length;
    int r = n - p; // number of elements to the right of p
    int newCapacity = n << 1;
    if (newCapacity < 0)
        throw new IllegalStateException("Sorry, deque too big");
    Object[] a = new Object[newCapacity];
    System.arraycopy(elements, p, a, 0, r);
    System.arraycopy(elements, 0, a, r, p);
    elements = a;
    head = 0;
    tail = n;
}

JDK PriorityQueue 源码分析

根据 PriorityQueue 类注释可以发现，优先队列是用堆，也就是完全二叉树（基于数组存储）实现的，在入队和出队（删除）都要维护小顶堆的性质，保证队列是有序的。

其实源码中最难理解的就是如何维护小顶堆的部分。我这里以从出队 poll 数据为例：

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

public E poll() {
    if (size == 0)
        return null;
    int s = --size; // 占用空间-1
    modCount++; // 修改次数 +1，防止并发操作
    E result = (E) queue[0]; // 取出堆顶数据，这就是 poll 出的数据，因为添加、删除数据时遵守了小顶堆原则
    E x = (E) queue[s]; // 获取堆最后的数据
    queue[s] = null; // 堆底数据置为null, 因为 queue[s] 先要放到堆顶，然后根据比较器自顶向下 siftDown 交换来保证小顶堆原则
    if (s != 0)
        siftDown(0, x);
    return result;
}

siftDown 来维护小顶堆原则

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

private void siftDownUsingComparator(int k, E x) { // k 传的是0, 也就是堆顶
    int half = size >>> 1;
    while (k < half) { // k 就是父节点
        int child = (k << 1) + 1;  // 获取左孩子节点，等价 child = k * 2 + 1
        // 假设左孩子是最小的
        Object c = queue[child];
        int right = child + 1;
        // 比较左右孩子的值，将最小的赋值给 c
        if (right < size &&
            comparator.compare((E) c, (E) queue[right]) > 0)
            c = queue[child = right];
        // c 和交换的数据 x 对比，直到 c >= x 的值
        if (comparator.compare(x, (E) c) <= 0)
            break;
        queue[k] = c; // 原来的父节点作为孩子节点 
        k = child;  //  孩子节点作为父节点（和上面一行一起看，也就是孩子节点和父节点交换）
    }
    queue[k] = x;
}

总结

没有完美的数据结构，每种数据结构优势和缺点并存，就像 CAP 理论不可能三角一样。

数据结构本身也可以通过升维、空间换时间、限制操作的思想进化为另一种数据结构：

• 通过对数组或链表的限制操作实现栈、队列；
• 跳表利用空间换时间的思想实现链表的二分查找；
• 数组通过升维的思想实现完全二叉树；
• Hash 表通过数组的特性实现 O(1) 的访问时间复杂度。

我们在解决问题的时候要充分利用这些思想、数据结构的特性去解决特定问题。

感觉本周的学习压力还是很大的，基础知识的整理学习，手动实现链表、队列（基于数组、链表）的基本操作，刷题耗费的时间最多，先是自己思考用暴力法解题，又学习不同思路，学习最优解。虽然端午节有不少整块的时间可以学习，但是时间还是不够用的，后面的课程压力很大。

在《极客大学》报名了覃超老师的 《算法训练营》，主要是想倒逼自己一下，花费10周的时间，把算法和数据结构搞定，而且还能获得大厂内推的机会，觉得还是很值得的。
其实很早之前就买了王争老师的《数据结构与算法之美》的专栏，不过在我买的时候课程也早就完结，我跟着课程顺序学习了30多节课，没有坚持下去。课程本身确实很费神，再加上极客时间出新课的速度太快了，而且好些都是非常感兴趣的，于是就放下这个学其他的了。只是中途在系统学习 Mysql 索引相关知识的时候，又回来把二叉树、二叉搜索树、B+ 树的章节跳着学习了一下。现在买的专栏要有 30 个了，一半都没有学完，真的快要变成屯课的了。

学习安排

总体计划是跟着《算法训练营》的课程来安排，并根据 OKR 的模板来制定：

• 底线要求：

  1. 《算法训练营》会提前放出下一周的学习内容，我需要在提前将下周的知识点、算法题拆成任务放到 Trello-算法训练营 上。目的是为了方便跟踪学习情况，尤其是算法题，需要反复练习、间隔练习，利用好 Trello 对任务有定时提醒功能。

  2. 每节课的课程学完后，在 “语雀” 上输出学习笔记；并将需要记忆的内容提炼出概要，输出成一个记忆手册，最好是一页纸，打印出来方便日常随身复习。

  3. 完成 2 道课后留下的算法题目

     • 理解每种不同解的算法思路，分析时空复杂度
     • 每种解法自己能够独立写出

  4. 训练营要求，每周输出学习总结，作为 Blog 文章发布

• 达标要求（在底线要求基础上）

  1. 结合《数据结构与算法之美》对应的章节内容一起学习，输出每节课的学习笔记
  2. 完成 5 道课后留下的算法题目，解题要在方法注释上加上时空复杂度
  3. 阅读、学习别人优雅的代码，并且自己的代码进行优化
  4. 每周在 Trello 上回顾本周所有完成的题目
  5. 对于有深刻启发的解题思路输出文章

• 挑战要求（在达标要求基础上）

  1. 完成 7 道或以上课后留下的算法题目

  2. 在期中考试之后，对所学过的解题思想进行一次全盘的 review ，输出文章

刷题注意事项

• 刷题不要死磕到底，不要追求数量
• 追求最优解，学习多种解题思路，学习优雅的代码，改进自己的代码
  • 一定要去 LeetCode 国际站学习高分题解
  • 对自己的代码进行 review
• 题目至少练习 5 遍

最后要特别感谢我的助教 罗祥老师 帮助我 review 了一下学习计划，之前太过注重刷题数量了，而且很可能完成不了，打击学习信心。现在调整了一下，最重要的是好好落实下去，未来的这 10 周学习压力还是很大的。

笔记摘录

连续重复阅读的问题有哪些

• 短期内可以记住，时间长了遗忘会很多
• 容易让人产生已经掌握知识的错觉，容易高估自己的水平，需要有间隔的自测

学习时 “条件刺激” 自己的方式有哪些

• 将要点转换为问题
• 试图自己回答这些问题
• 用自己的话归纳要点
• 将新知识和已知联系起来
• 多找找课外例子
• 不停的问自己核心概念是什么，规则是什么，支撑概念的细节是什么

盲目努力学习的误区

• 不知道自己的薄弱点在哪里，不知道在哪里需要花更多的精力
• 喜欢用让自己错误认为自己已掌握的学习方法

如何看待考试

• 考试是一种学习工具，用于检测校正已学的知识

学习者的最好习惯是什么

• 进行有规律的自测，重新校准自己知道什么，不知道什么

自测的注意事项

• 间隔练习，这样可以改善记忆，因为延时后再检索知识需要花费更大的力气
• 穿插不同但相关的科目或技能练习
• 在学习别人的解决方案前，优先自己先尝试解决问题
• 从不同类型的问题中提取基本原理或规则
• 多样化练习
• 反思以及细化

两次间隔练习至少需要多久

• 1天或一次睡眠后再次练习效果会很好

穿插练习的好处

• 穿插练习两样或多样也是一种间隔
• 穿插练习有助于发展人们辨识不同问题的能力

穿插练习的注意事项

• 不能完成一个科目的全部内容，在跳到下一个科目。

多样化练习的好处

• 多样化练习会使用到大脑的不同区域
• 会需要耗费更多的脑力，或让大脑编成灵活的表征，适用范围更广

多样化练习的注意事项

• 过分强调多样化，可能导致忽视对基础知识重复检索的练习

学习知识时必要的练习有哪些

• 检索练习，间隔练习，穿插练习，生成训练，细化
• 这些练习会放慢学习进程，但是可以换来更牢固、更准确、更持久的学习效果

如何实践间隔练习

• 进行周期性间隔练习，每日回顾当天内容、每日复习昨天内容
• 每周复习总结
• 每月复习总结
• 复习总结时在大脑里预先回忆大纲，再回忆细节

如何有好的记忆效果

• 在检索时让自己付出更大的认知努力

低难度、集中式学习的危害

• 容易使大脑将学到的东西编织为简单、直白的心理表征，导致无法灵活运用
• 需要多样化、高难度耗费脑力的学习才会是大脑将知识编织为灵活的表征，适用范围会更广

练习的普适性原则

• 检索、间隔、穿插、多样化、反思以及细化

学习误区

• 解决问题好过记忆问题的答案，尝试解决问题但得到了错误的答案，好过不去尝试
• 用自己的话总结，比直接抄写要好
• 反复阅读笔记，不如进行自测

如何进行反思

• 课程的核心内容是什么
• 有哪些相关的例子
• 如何把这些内容和我的已有知识联系起来
• 自己哪些地方可以提高
• 进一步精通还需要做什么
• 下一次用什么方法可以获得更好的总结（用脑图抽象）

生成性学习是指什么

• 在没有教导的情况下尝试解决问题的过程，即先生成答案而不是回忆答案，生成就是试错

动态测验的步骤

• 进行某种类型的测验，可以是一段经历也可以是一次笔试，目的是为了了解自己的知识或技能有哪些欠缺
• 运用反思、练习、间隔练习提高自己的能力
• 再次测验自己，留意有哪些需要改善的地方，同时特别注意哪些地方还要下功夫

什么叫做心智模型

• 提取知识的核心观点，构建完整的心理框架，这框架叫做心智模型

建立心智模型的好处

• 你的学习成果会非常稳固
• 你可能会发现模型有缺损的地方，在治理缺损的时候，你可能会有创新的想法出现

脑图

• 问题 - 概念 - 支持概念的细节

校准的作用

• 校准作为可观的工具消除假象，调整判断可以更真实的反映自己

好的学习习惯列表

• 课前一定要阅读资料
• 在阅读的时候预想考试会出什么题目，如何解答
• 在课上心里回答这些问题，来测验阅读内容的记忆成果
• 在笔记中标粗术语和定义，确保能够理解
• 将课堂内容组织成一份自己的学习指南
• 将负责、重要的概念贴在床头，不时自测
• 将复习和自测练习的时间隔开

实践指南

学习前做到

• 预想考试会有什么问题并尝试解答

学习中做到

• 避免连续重复阅读
• 将要点转换为问题
• 在学习别人的解决方案前，优先自己先尝试解决问题
• 用自己的话归纳要点
• 将新知识和已知联系起来
• 多找找课外例子
• 不停的问自己核心概念是什么，规则是什么，支撑概念的细节是什么
• 多样化练习，穿插不同但相关的科目或技能练习

学习后做到

• 总结课程的核心内容是什么，回忆有哪些相关的例子
• 如何把这些内容和我的已有知识联系起来
• 自己哪些地方可以提高，进一步精通还需要做什么
• 下一次用什么方法可以获得更好的总结（用脑图抽象）
• 进行周期性间隔练习，每日回顾当天内容、每日复习昨天内容，每月、每周复习总结
• 复习总结时在大脑里预先回忆大纲，再回忆细节，进行反思和细化
• 进行检测校正，消灭假象，真实的反映自己现状