讨论/技术交流/【春招学习计划】周常总结 Week5/
【春招学习计划】周常总结 Week5

各位小伙伴们好,我是负责春招学习计划第五周(2021.02.15 - 2021.02.21)的 Leetor. 本周学习计划主要学习内容为哈希表和链表,每日一题主要学习内容为双指针与滑动窗口。

春节假期已经结束,春招也即将大面积开始,希望各位小伙伴努力提升自己,多从各种渠道获取有用的信息,从而在春招中取得满意的 offer ~

往期链接

  • Week 1 主要内容:数组、二分查找、并查集。

  • Week 2 主要内容:数组、字符串、KMP 和字典树。

  • Week 3 主要内容:双指针、滑动窗口。

  • Week 4 主要内容:栈、队列。

学习建议

关于双指针和滑动窗口的相关内容可以移步Week 3.

链表

链表是一种通过指针来连接元素的线性数据结构。作为国内常见数据结构教材的第一章正式内容,链表可以说是一个很基础且很常见的数据结构。同时,链表也是二叉树等其他常见数据结构的基础。因此,掌握链表的用途、操作与实现(包括双向链表和循环链表)也是很重要的一件事。

Leetcode 上的链表题目大概有 50 道左右(本文写作时对应标签的题目数为 57)。如果没有系统学习过数据结构,同时又有一定的空余时间,十分建议将该标签的题目全部做完。同时也要注意在做的时候总结链表题目的常见操作和常见技巧。

Leetcode 针对链表也有对应的 Leetbook 可供阅读。link. 在做题时结合文字教程或者相关教材也是相当不错的选择。同时,读者也可以根据 Leetbook 的目录和内容来回忆/检验自己的掌握程度。

同时在做题时也要注意和其他的线性数据结构(数组、栈、队列等)进行对比,比较常见操作的时间复杂度,从而可以在做题时养成更好地选择数据结构的习惯。

下文列出一些常见的知识点,很可能涵盖不全,仅供参考。

  • 定义(链表节点)/(从数组或者字符串)生成/输出链表

  • 操作:反转链表/删除添加指定元素/排序/合并/分割

  • 变种:双向链表/循环链表

  • 常见技巧:哨兵节点(虚拟头尾节点)/快慢指针

哈希表

哈希表是又称散列表,一种以 "key-value" 形式存储数据的数据结构。所谓以 "key-value" 形式存储数据,是指任意的 key 都唯一对应到内存中的某个位置。只需要输入查找的值 key,就可以快速地找到其对应的 value。可以把哈希表理解为一种高级的数组,这种数组的下标可以是很大的整数,浮点数,字符串甚至结构体。OI-wiki

同样,针对哈希表也有对应的 Leetbook 可供阅读。link.

另外,除了哈希表的常见应用之外(理想状态 O(1)O(1) 时间查询),设计哈希表(设计哈希函数/如何解决冲突等)也是面试常见的问题。前文的两个链接均有相关的介绍,同时常见的数据结构及算法教材(包括但不限于《算法-第4版》、《算法导论》)也会有一定的介绍,读者可以自行阅读。

PS: 有两个面试常见的缓存设计问题一般会应用到双向链表和哈希表组合的数据结构:

前缀和与差分

本周每日一题的部分题目运用到了相关技巧,该技巧也常见于算法题目中。因此在此处简要介绍一下两者。详细的介绍和例题可以参见 OI-wiki.

前缀和是一种重要的预处理,能大大降低查询的时间复杂度。可以简单理解为“数列的前 n 项的和”。通常对于不可变的序列,使用前缀和预处理可以将单次连续子序列和询问的时间复杂度优化到 O(1)O(1).

差分是一种和前缀和相对的策略,可以当做是求和的逆运算。它可以维护多次对序列的一个区间加上一个数,并在最后询问某一位的数或是多次询问某一位的数。注意修改操作一定要在查询操作之前。

前缀和的题目相对较多,因此暂不列举。仅列举一些可以运用差分方法解决的问题:

问题汇总

LC566 这里的映射 (i, j) -> i * n + j 为什么是用列数 n 而不是行数 m, 包括 i = x / nj = x % n.

因为这里的 (i, j) 表示 第 i 行第 j 列,每行有 n 个数,因此需要乘 n. 如果采用 第 i 列第 j 行的写法,那么需要乘行数 m.

LC995 diff 数组在一些情况下岂不是会有负值,负值代表了什么呢?

负值代表遍历到该数时,该数需要翻转对应的次数。不过数字的状态和操作构成模 2 的加法群,因此负值可以通过模 2 转化为非负值,也就是优化后的位运算解法。

LC995 怎么理解这句话呢? 通过累加差分数组可以得到当前位置需要翻转的次数,我们用变量 revCntrevCnt 来表示这一累加值。

累加值就是当前数的翻转次数。每一次翻转相当于翻转长度为 K 的子数组,为了简化每个数翻转次数的计算,可以记录该数翻转次数与前一次的差值,遍历时对于累加值加减即可。

LC995 怎么理解差分数组呢?

差分是一种和前缀和相对的策略,可以当做是求和的逆运算。它可以维护多次对序列的一个区间加上一个数,并在最后询问某一位的数或是多次询问某一位的数。注意修改操作一定要在查询操作之前。OI-wiki

举个例子,有很多人要乘坐某辆公交车,每个人会在某个站上车,在另一个站下车,如果想求出离开每个站时公交车的人数,最方便的就是维护一个差分数组,对于每个人而言,在上车点 +1, 在下车点 -1.

一些可以运用差分方法解决的问题有:

LC1004 这道题原来可以用二分查找做啊

是的,但是复杂度会更高。事实上,双指针就是针对二分查找的单调性优化。

LC697 这个初始下标 (nums[i])[1] 是什么时候被赋值的?

左边界是这个数第一次出现时被赋值的,在之后的遍历中不会被更改。

LC1438 这道题使用内置的平衡树解决不是很方便吗,为什么还要使用单调队列?

使用平衡树的时间复杂度为 O(nlogn)O(n\log n), 而使用两个单调队列的时间复杂度为 O(n)O(n), 很显然后者优于前者。同时,如果考虑自己实现的话,后者的代码量和思考量是前者的数倍。

另外,在本题中我们只需要获取连续区间(滑动窗口)内的最大最小值,整体维护一个有序结构也不是必要的。

类似的问题还有:

  • 无序数组第 k 大元素:排序方法 / 线性选择(快排的一部分)法 LC215.

  • 无序数组前 k 大元素:排序方法 / 二叉堆实现的优先队列 LC347.

读者可以在做题中自行体会。

8
共 7 个回复

太强了

1

厉害啊

2

前缀和差分的总结妙啊

1

打call 打call 🙋‍♂️

1

支持群友用爱发电

1

赞赞赞

1

差分妙啊~

1