讨论/求职面试/【春招学习计划】周常总结 Week3/
【春招学习计划】周常总结 Week3

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

往期链接

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

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

问题汇总

LC1438 可以用 PriorityQueue 吗?不提及是有啥弊端吗?

可以,不过优先队列需要支持「删除指定元素」的功能才能实现左端点右移的功能。
另外,使用带延迟删除二叉堆实现的优先队列解决本题,时间复杂度会达到 O(nlogn)O(n\log n), 相较而言,单调队列使用的双端队列时间复杂度为 O(n)O(n), 明显更优。

LC888 sumA - sumB 这个结果万一是奇数是不是答案就不准确了?

题目中已有 保证答案存在。 的字样。如果结果为奇数,那么就不存在可行的解。因此不需要考虑此种情况。

LC888 这个直接 sum()int 不会超出范围吗。。

int i = 0; int j = 0; int s = 0; 
while(i<A.length||j<B.length){ 
    if(j==B.length||(s<=0&&i!=A.length)){ 
        s+=A[i]; i++; continue; 
    } 
    s-=B[j]; j++; 
}

题目的数据范围中,单个数组元素上限 1e5, 数组元素数量上限 1e4, 因此和不会超过 1e9. 而 int 一般而言上界是 2**31-1 是大于 1e9 的。

LC424 直接返回 right - left 也过了……不知道是哪里会出问题

因为按照题解的写法(if 保证左窗口一次至多右移一格),滑动窗口只会增大不会缩小,因此直接返回也是没有问题的。事实上另一篇题解也是这么写的。

LC480 Python 暴力解法居然不超时?永远的神

因为 Pythonbisect.insort 很快,虽然理论时间复杂度是 O(n)O(n). source

事实上,在 LC1649题解评论区也有人提到过类似的原理。(Credit to @zerotrac2 and @newhar)

Python 不公平的点在于, 虽然它语言解释运行很慢, 但一些底层库 ( list 等) 却基本都是用 CC++ 实现的, 所以快一些(相对于不用库,直接类c数组操作而言),但是 Python 时限又高(8-10s), 所以总体来说相当于用 C++ 写了个暴力又放宽了时间限制,成就了暴力的奇迹。

P.S. [x:x] = [v] 确实要比 insert 要快,因为 [x:x] = [v] 的底层实现调用 memmove 库函数来搬运插入之后的元素,而 insert 采用 for 循环搬运元素,参考 list 源码

LC480 有点不理解,如果优先队列中有需要延迟删除的数,那么此时堆顶中的数还是中位数吗?为啥多出了数之后中间还是中位数啊?

  1. 堆顶元素必定有效
  2. 两个堆的元素数目不包含延迟删除的元素

上述两点保证了一定是中位数。

LC480 JavaPriorityQueue 不是自带 remove(Object o) 删除任意元素的方法吗?为什么还要写延迟删除呢?

JavaPriorityQueueremove(Object o) 方法的时间复杂度是 O(n)O(n) (虽然删除的复杂度是 O(logn)O(logn) , 但在二叉堆中搜索指定元素的复杂度是线性的)而不是 O(logn)O(logn), 在数据范围较大的情况下很可能无法通过。(为什么?link

LC1208 这里为什么要求连续?

对于数组和字符串而言:子串/子数组 (substring/subarray) 是连续的;子序列 (subsequence) 不要求连续,但需要保持在原数组/字符串的顺序。在做题时务必要注意区分。严格定义参见 OI-Wiki.

LC1423 为什么我用递归/记忆化搜索/动态规划做超时了?

本题 nn 的数据范围最大为 10510^5, 使用平方级别或者时间复杂度更高的算法显然无法通过。希望读者在做题时养成通过数据范围判断可用的时间复杂度的习惯。more.

学习建议

双指针

注:关于「双指针」和「滑动窗口」的定义问题,存在一定的争议,本文采用此文的说法(「双指针」是一种解题技巧,「滑动窗口」是一类问题的形式)。

在 LeetCode 平台上,有很多优秀的相关题目、题解和学习资料,在此就不赘述了,希望各位读者可以主动寻找探究、独立思考分辨。

虽然双指针的使用方法十分复杂,有同向和反向,有各种附加技巧,但是万变不离其宗。

请务必在学习和做题的过程中理解一句话:

双指针是二分查找的单调性优化。

为什么?

附一些不错的学习材料和方式供参考:

  • ITMO Academy: pilot course - Two Pointers Method CF EDU

    Codeforces 平台的教学课程最新推出的一个章节,虽然定位是竞赛课程,但是对新手友好。同时也附有从易到难的练习题目供巩固,且因为 Judge 有语言时间补正,因此对于 Python 选手相对友好。

关于 LC480 滑动窗口中位数 的一点延伸和个人总结

本部分摘编自题解

首先总结几种常见的(与语言特性无关)的解法和对应的最坏情况时间复杂度,时间复杂度从高到低。(带*的超出了面试范围,请酌情食用)

为了方便以及统一记号,我们记数组长度为 nn, 记滑动窗口长度为 k (<n)k\ (< n).

  • 每滑动一次均排序计算中位数: 滑动次数为 nkn-k, 每次排序时间复杂度为 O(klogk)O(k\log k), 因而总时间复杂度为 O((nk)klogk)=O(nklogk)O((n - k)klog k) = O(nk\log k).

  • 每滑动一次均线性选择计算中位数:滑动次数为 nkn-k, 每次线性选择(类似快排,忘记了?看这里)时间复杂度为 O(k)O(k), 因而总时间复杂度为 O((nk)k)=O(nk)O((n - k)k) = O(nk).

  • 用单数组来维护有序结构,每次二分插入与删除:滑动次数为 nkn-k, 每次二分查找时间复杂度为 O(logk)O(\log k), 数组插入删除任意元素时间复杂度为 O(k)O(k), 因而总时间复杂度为 O((nk)k)=O(nk)O((n - k)k) = O(nk).

  • *转化为静态区间第 k 小问题,离散化后用线段树/可持久化线段树(主席树)求解,时间复杂度为 O((nk)logn)=O(nlogn)O((n - k)\log n) = O(n\log n). link1 link2

  • 带有「删除指定元素」的双堆:滑动次数为 nkn-k, 堆的大小为 O(k)O(k), 每次插入元素复杂度为 O(logk)O(\log k), 每次保持平衡操作(弹出堆顶插入另一堆)复杂度为 O(logk)O(\log k), 每次删除指定元素复杂度为 O(k)O(k) (想想为什么?),因而总时间复杂度为 O((nk)k)=O(nk)O((n - k)k) = O(nk).

    • 事实上,通过一些额外的操作,可以降低「删除指定元素」操作的时间复杂度,使其不再成为瓶颈,进而使得总时间复杂度为 O(nlogk)O(n\log k). 读者可以思考一下如何实现。
  • 带有「延迟/惰性删除」的双堆:滑动次数为 nkn-k, 由于「延迟/惰性删除」,堆的大小最大可能为为 O(n)O(n), 每次插入元素复杂度为 O(logn)O(\log n), 每次保持平衡操作(弹出堆顶插入另一堆 + 若堆顶需要删除则删除)复杂度为 O(logn)O(\log n), 因而总时间复杂度为 O((nk)logn)=O(nlogn)O((n - k)\log n) = O(n\log n).

  • 用双平衡树代替双堆:滑动次数为 nkn-k, 对于平衡树,由于不存在「延迟/惰性删除」造成的额外大小增加,因此平衡树的大小为 O(k)O(k), 平衡树增删操作复杂度均为 O(logk)O(\log k), 因而总时间复杂度为 O((nk)logk)=O(nlogk)O((n - k)\log k) = O(n\log k).

显然,最后一种解法在时间复杂度上最优,但由于并不是所有语言都包含平衡树的标准库,且平衡树的手动实现过于复杂,不在绝大多数面试考察范围内,因此,官方题解选择了最坏时间复杂度稍逊的倒数第二种解法。

PS: 对数时间删除指定元素的二叉堆是可以做到的,仅需要手动建立并维护元素和堆中索引的双向映射,便可以使单次「找到指定元素」的复杂度降低至 O(1)O(1), 进而使得「删除指定元素」操作的时间复杂度为 O(k)O(k), 与平衡树一致。但是一般编程语言中的优先队列/二叉堆均不支持此操作,因此需要手动实现二叉堆。同时,建立维护索引的操作虽然代码量较少,但是会增加一定的调试难度,一般情况还是建议使用平衡树代替。(感谢 @OTTFF 指出)

其次说一下常见的使用各种语言特性的解法及其时间复杂度。囿于作者水平和篇幅,仅举数例,并不能包含所有语言及所有情况。

  • (C++) 单 multiset , 每次ss.begin() 更新 (包括但不限于 std::advance() )中位数迭代器(此处时间复杂度为 O(k)O(k) ),总时间复杂度为 O(nk)O(nk).

  • (C++) 单 multiset , 手动维护中间位置的迭代器,每次至多移动一步(此处诸多细节从略),总时间复杂度为 O(nlogk)O(n\log k), 与最优解一致。

  • (C++) 使用 pb_ds 库的 tree 数据结构(红黑树实现), 使用 find_by_order() 方法维护中位数,总时间复杂度为 O(nlogk)O(n\log k), 与最优解一致。 link.

  • (Java) 双 PriorityQueue , 使用 remove(Object o) 方法(此处时间复杂度见前文)而非延迟删除,总时间复杂度为 O(nk)O(nk).

  • (Python) 单 SortedList, 采用下标访问中位数,总时间复杂度可以认为 O(nlogk)O(n\log k), 与最优解一致。

PS1: 很多人使用了 Pythonbisect.insort() 或者 [x:x] = [v], 此处操作复杂度依旧应当视为线性,但由于硬件和软件的因素(参见前文),其实际运行时间可能并不逊于 SortedList,因而在 LeetCode 的评测系统下有能力作为一种合理的过题方案。但是,在可能出现的复杂度分析场合(尤其是面试),依旧要注意。

PS2: 使用有序数据结构(可以对数时间进行某些操作)时,需要注意某些看似简化思考和代码量的操作可能会不必要地增加时间复杂度,从而降低对应数据结构选取的意义。

关于语言环境

在每日一题的题解下面,经常有同学问为什么题解用了某某库之类的问题。实际上,在代码编辑界面是有对应的语言环境介绍的。

怎么进去呢?

如图所示

如图所示,点击左边的 info 标志即可。

然后

然后就是这样。

事实上,在帮助中心有专门的页面介绍此内容。不过,国区的页面更新速度较慢,如需浏览,可以参见国际区的相关页面

简单介绍 Pythonsortedcontainers

众所周知, Python 没有平衡树的标准库,而手撸出这样一个数据结构又并不简单。因此, LeetCode 的环境中引入了可以对标的 sortedcontainers 库。

这个库的底层实现是什么呢?

看这里。 其底层实现类似 B+ 树,利用的原理是 PythonListbisect.insort 很快(因为硬件和软件层面的优化)。

这个库里有哪些类?

这个库支持什么操作?

常用的 CRUD 操作基本都支持,并且复杂度和平衡树的时间复杂度基本一致。详见文档

具体要怎么用呢?

去看 API 啊((((

简单介绍几个常用的操作(以 SortedList 为例):

  • __init__(iterable = None, key = None) 初始化,支持自定义初始迭代器和比较器。时间复杂度 O(nlogn)O(n\log n).

  • __contains__(value) ss.__contains__(value) == value in ss 判断是否存在。时间复杂度 O(1)O(1).

  • __len__() ss.__len()__ == len(ss) 返回长度。

  • add(value) 加入元素。时间复杂度大致 O(logn)O(\log n).

  • remove(value) / discard(value) 删除单个值对应的元素。注意 remove 不存在的元素会报错。时间复杂度大致 O(logn)O(\log n).

  • __getitem__(index) ss.__getitem__(index) == ss[index] 按下标访问,支持切片操作。时间复杂度大致 O(logn)O(\log n).

  • __delitem__(index) ss.__delitem__(index) == del ss[index] 删除下标对应的元素,支持切片操作,下标不存在会报错。时间复杂度大致 O(logn)O(\log n).

  • pop(index = -1) 删除下标对应的元素,下标不存在会报错。时间复杂度大致 O(logn)O(\log n).

  • bisect_left(value) / bisect_right(value) 二分查找下标,与 bisect 库对应的方法基本一致。时间复杂度大致 O(logn)O(\log n).

仅举几例,其余详见 API.

31
共 8 个回复

学长好厉害!

2

学长好厉害!

2

学长好厉害

1

学到了

1

棒棒哒🙋‍♀️

1

文中描述自己手动建立维护堆,建立双向映射时 使得「删除指定元素」操作的时间复杂度为 O(k),与平衡树一致 此时间复杂度应为O(logk)

感谢lz,学到很多。

学长好厉害!

大彻大悟