讨论/技术交流/分享|【春招学习计划】周常总结 Week1/
分享|【春招学习计划】周常总结 Week1

写在前面

什么是春招学习计划?

各位小伙伴们好,我是负责春招学习计划第一周(2021.01.18 - 2021.01.24)的 Leetor. 本篇总结计划分为三个部分,第一个部分是关于「每日阅读计划」的问题汇总和一些学习建议;第二个部分是关于「每日一题打卡」的问题汇总;考虑到本周本月的每日一题大部分为并查集相关的题目,因此打算在第三部分写一些个人对于并查集的总结与理解。

每日阅读计划:数组

本周(2021.01.18 - 2021.01.24)每日阅读计划的主题是「数组」,主要内容包括:时间与空间复杂度分析、数组与动态数组、二维数组、二分查找。

问题汇总

数组无序的情况下还需要用二分查找吗?

此类情况如果要用二分查找必须要对数组排序。而算法的选取需要看整体时间复杂度,如果只是单次查找的话,线性搜索会优于排序后二分查找,而如果多次查找,排序后二分的时间复杂度可能会优于线性搜索。

二分查找中的三个模板有什么用?

举例而言:

  1. 在严格递增有序数组中寻找某个数
  2. 在有序数组中寻找某个数第一次出现的位置(或者在有序数组中寻找第一个大于等于某个数的位置)
  3. 已知有一个先严格递增后严格递减的数组,找数组最大值的位置

学习建议

  • 时间和空间复杂度

    时间和空间复杂度是算法中很重要的概念,同时在面试中也会经常要求分析代码的时空复杂度。一种常见的学习方法是在做每一道题时思考完/写完算法后大致分析一下自己代码的时空复杂度。

    同时常见 OJ 平台的题目(包括但不限于 LeetCode 的周赛题和新题)一般都会附带数据范围,为了避免超时(TLE),在做题时也要养成通过数据范围估测可允许的最大时间与空间复杂度量级,进而选择对应的可用算法的习惯。

    在估算时,一般可以按照以下的原则:

    • 大部分平台 C++/Java1s 内的操作次数大约为 10^7 - 10^8, Python 由于相对较慢,大约为 10^6 - 10^7, 而大部分 OJ 平台的时限都在 1s - 10s 左右。

    • 举例而言,n <= 16 一般对应 O(2n)O(2^n) 甚至 O(3n)O(3^n) 的算法; n <= 1000 一般对应 O(n2)O(n^2) 级别的算法; n <= 10^5 一般对应 O(n)O(n) 或者 O(nlogn)O(n\log n) 数量级的算法。

    另外,在熟悉基础内容之上,对于一些高级的记号表示和计算技巧(例如主定理等),可以阅读《算法导论》的相关章节(第 3 / 4 章)。

  • 动态数组

    关于动态数组的内容在很多程序语言和数据结构与算法教材中都有涉及(例如《算法4》的 1.3 节)。如果对于动态增长缩短的细节依旧不熟悉,建议手动实现一遍并测试。

  • 二分查找

    二分查找作为很基本很重要的一个算法,一般会贯穿算法学习者的大半个生涯。同时,二分查找爆炸的细节(例如是否取等号,是否减 1)也成为了很多人头痛的对象。在 LeetBook 区和很多相关问题的题解区都有很多优秀的介绍文章,建议在阅读是选择思路明确、讲解清晰、代码可读性强的(比如说 LC35 题解),而不是单纯扔模板然后讲一些玄之又玄的废话(此处应有狗头)的题解。

    一般而言,直接用到二分查找的题目会有以下几种情况:寻找某个数值、寻找第一个大于等于某个数值的位置(左边界)以及寻找最后一个小于等于某数值的位置(右边界)。

    另外,个人认为,二分查找有一个或者多个固定的模板固然重要,但是模板是建立在在自己有深刻且全面的理解的基础上的,盲目背诵或者套用模板容易在某些时刻走本可避免的弯路。理解的重点包括但不限于:单调性(什么时候可以用),不同情况下搜索区间的变化,循环的终止条件

    在确保有清晰理解的基础上,可以寻找一些优秀的模板进行参考。个人而言最推荐的是语言的标准库。标准库作为大部分使用者会使用到的内容,其代码一般而言会清晰且高效。并且对于上述三类问题,一般都有对应的解决方案。举例而言:

    • C++std::binary_search, std::lower_bound, std::upper_bound. link1 link2 link3

    • Pythonbisect.bisect, bisect.bisect_left, bisect.bisect_right. link

    在理解算法本身的基础上理解对应标准库函数及其代码,不仅有助于加深对于算法的理解和应用,更有助于对于标准库的运用(偷懒)。

每日一题问题汇总

LC1489 伪关键边是不是这样理解的: 我们先找到一个最小生成树,他的权值是 value ,然后我们枚举每一条边 e, 假设 e 是最小生成树的一条边,然后如果求出的最小生成树的权值是 vv==value 说明 e 是伪关键边。 那么是不是我们一开始求出的最小生成树的每一条边都是伪关键边。 然后在伪关键边中找出关键边。

这样的方法也是可以的,不过在表达上要注意,这里的「关键边」和「伪关键边」不是包含关系而是互斥的。

首先「需要注意的是,关键边也满足伪关键边对应的性质。」, 那么伪关键边对应的性质,亦即「如果此边在 Kruskal 算法执行前预先加入,那么生成的树总权值与最小生成树的权值相等」,是关键边的必要条件。

因此我们可以有两种办法来判断:

  1. 先找出所有关键边,在此之外找到所有伪关键边。
  2. 找到所有满足伪关键边前述性质的边,再区分是关键边还是伪关键边。

两者在时间复杂度上没有区别。

LC1584 为什么不用 prim 呢? prim 算法时间复杂度是 O(E+VlogV)O(E+VlogV) ,在本题中就是 O(n2)O(n^2)了。就是需要加个堆优化,还是挺麻烦的。

O(E+VlogV)O(E+VlogV) 需要斐波那契堆,二叉堆的时间复杂度是 O(ElogV+VlogV)O(ElogV+VlogV) (参见《算法导论》23.2)

LC1584 请问第一个解法中 self.rank 这个数组的作用是什么?

表示当前点及其子树的大小,用来实现并查集的「按秩合并」(小树合并在大树下以降低时间复杂度)。

并查集:从入门到入坟

考虑到本月的每日一题已经并将(别问我怎么知道的)多次涉及并查集知识点,因此打算把并查集的一些总结和理解作为本文的最后一部分。

本部分打算用问答的形式来写,囿于篇幅,很多内容不能详述,我会给出对应的参考链接,有兴趣的可以深入阅读。

并查集是什么鸭?

并查集 (Disjoint-set data structure / union–find data structure / merge–find set) 是一种树形的数据结构,顾名思义,它用于处理一些不交集的合并查询问题。 它支持两种操作:

  • 查找 ( Find ) :确定某个元素处于哪个子集;

  • 合并 ( Union ) :将两个子集合并成一个集合。

参考链接: OI-wiki, Wikipedia, CF EDU.

题解区常见的「路径压缩」和「按秩合并」是什么意思啊?有什么用?

两者都是为了优化 FindUnion 的时间复杂度而提出的优化算法。

  • 「路径压缩」:在并查集中查找代表元素时,会将经过的所有元素「直接」连接到代表元素,也就是将连通分量「压扁」。

  • 「按秩合并」:在并查集中合并两个连通分量时,将「秩」小的连通分量合并到「秩」大的连通分量上面。这里「秩」可以定义为连通分量的大小(包含的节点数量),或者连通分量的高度(连通分量是树的结构,因此可以定义高度。不过在「路径压缩」优化的基础上,这个高度会不断减小,但我们不用去时刻维护它,这样也可以达到最优的时间复杂度是已经被证明的了)。

以上摘编自 link.

上面提到的优化算法的时间复杂度是多少呢?

优化 平均时间复杂度 最坏时间复杂度
无优化 O(logn)O(\log n) O(n)O(n)
路径压缩 O(α(n))O(\alpha(n)) O(logn)O(\log n)
按秩合并 O(logn)O(\log n) O(logn)O(\log n)
路径压缩 + 按秩合并 O(α(n))O(\alpha(n)) O(α(n))O(\alpha(n))

LC547 的题解区有一篇 @zerotrac2 写的时间复杂度科普 link,上表摘录于此。里面对于两种常见优化的平均和最坏时间复杂度有详尽的介绍,同时也有相关的测试。

有哪些和并查集有关的算法啊?

求解最小生成树的 Kruskal 算法 是一种基于并查集的算法。

LeetCode 上有哪些并查集相关的题目呢?有没有推荐的做题路线?

善用 tag 功能。

相关的题目按照难度和具体内容可以分为以下几个部分(此处题目仅举几例,并不完全覆盖所有题目,包括可以强行天秀用并查集求解的题目):

请注意,某些题目可能涉及解法剧透,请谨慎食用。

  • 入门

    • LC547 省份数量(曾经的 朋友圈)
    • LC684 冗余连接
  • 上手

  • 入坟

    • LC1627 带阈值的图连通性
    • LC1697 检查边长度限制的路径是否存在
    • LC1632 矩阵转换后的秩
    • LC803 打砖块
  • 最终试炼

    • LC1724 检查边长度限制的路径是否存在 II
  • Kruskal 算法

    • LC1584 连接所有点的最小费用
    • LC1489 找到最小生成树里的关键边和伪关键边
    • LC1168 水资源分配优化
  • 带权并查集

    • LC990 等式方程的可满足性
    • LC399 除法求值

PS1: 很多题目中,并查集不一定是唯一(最优)方法。有相当一部分的题目可以通过 BFS/DFS 达到几乎一致的时间复杂度。

PS2:很多并查集的题目和图的相关知识有着很紧密的联系,建议学习时结合「图论」的相关内容和题目一起学习。

(可能会佛系更新,也可能咕咕咕)

有没有一键式 CV 的模板啊?

对方扔出了一本《提问的艺术》并离开了。)出门右转 OI-wiki 或者题解区。

顺便贴一份自用的并查集模板,实现了基本功能以及「路径压缩」和「按秩合并」优化。

# Union-Find with path compression and union with rank
class DSU:
    def __init__(self, n):
        self.count = [1] * n 
        self.parent = [_ for _ in range(n)]

    def find(self, i): # find root(i) and compress the path
        if self.parent[i] != i:
            self.parent[i] = self.find(self.parent[i])
        return self.parent[i]

    def union(self, i, j): # return True if already connected
        pi, pj = self.find(i), self.find(j)
        if pi != pj:
            if self.count[pi] < self.count[pj]:
                pi, pj = pj, pi
            self.parent[pj] = pi
            self.count[pi] += self.count[pj]
            return False
        return True

针对不同的问题,可以进行如下更改:

  • 元素不是整数:维护映射,或者将 self.parentself.count 改为 dict 并添加 self.add (添加元素)方法。

  • 带权并查集:添加 self.weight , 并修改对应的查找与合并方法。

  • 想去掉某种优化:直接改对应的方法即可。

有没有更炫酷一点的应用?

别卷了别卷了 可以看 OI-wiki 的 这个 链接。其中的 B 也就是 LC1724.

66
共 18 个回复

学长好厉害!

11

卷到了卷到了

4

按标签筛选题目(

2

学长好厉害

2

学长好厉害

2

学长好厉害!感谢分享

2

学长好厉害!

2

nb

1

群友太卷了

1

mark

1