Press "Enter" to skip to content

Posts published in “SP”

KMP Algorithm SP19

KMP Algorithm, KMP 字符串搜索算法

Time complexity: O(m+n)
Space complexity: O(m)

Implementation

C++

Python3

Applications

LeetCode 28. strStr()

C++

LeetCode 459. Repeated Substring Pattern

C++

1392. Longest Happy Prefix

C++

花花酱 Minimum Spanning Tree (MST) 最小生成树 SP18

Prim’s Algorithm

Time complexity: O(ElogV)
Space complexity: O(V+E)

C++

Python

Kruskal’s Algorithm

Time complexity: O(ElogV)
Space complexity: O(V+E)

C++

Python

LeetCode 进入千题时代该如何刷题?



题目列表:https://bit.ly/2E8yBHq

总结一下:

  • 大家的刷题经验都比我丰富,找到最适合自己的方法就好了
  • 200~300题刷2-3边,至少100+小时的投入
  • 同一类型题目一起刷,总结规律和差异
  • 多看别人的(优秀)代码
  • 完整的手写实现,不要copy代码,增强肌肉记忆(视频中没提到)
  • 培养代码风格



花花酱 Segment Tree 线段树 SP14

Segment tree is a balanced binary tree with O(logn) height given n input segments.
Segment tree supports fast range query O(logn + k), and update O(logn).
Building such a tree takes O(n) time if the input is an array of numbers.

Tree之所以大行其道就是因为其结构和人类组织结构非常接近。就拿公司来说好了,CEO统领全局(root),下面CTO,CFO等各自管理一个部门,每个部门下面又正好有好两个VP,每个VP下面又有两个director,每个director下面又有2个manager,每个manager下面又有2个底层员工(leaf),为什么是2?因为我们用二叉树啊~

故事还是要从LeetCode 307. Range Sum Query – Mutable说起。

题目大意是:给你一个数组,再给你一个范围,让你求这个范围内所有元素的和,其中元素的值是可变的,通过update(index, val)更新。 

nums = [1, 3, 5],
sumRange(0, 2) = 1+3+5 = 9
update(1, 2) => [1, 2, 5]
sumRange(0, 2) = 1 + 2 + 5 = 7

暴力求解就是扫描一下这个范围。

时间复杂度:Update O(1), Query O(n)。

如果数组元素不变的话(303题),我们可以使用动态规划求出前n个元素的和然后存在sums数组中。i到j所有元素的和等于0~j所有元素的和减去0~(i-1)所有元素的和,即:

sumRange(i, j) := sums[j] – sums[i – 1] if i > 0 else sums[j]

这样就可以把query的时间复杂度降低到O(1)。

但是这道题元素的值可变,那么就需要维护sums,虽然可以把query的时间复杂度降低到了O(1),但update的时间复杂度是O(n),并没有比暴力求解快。

这个时候就要请出我们今天的主人公Segment Tree了,可以做到

Update: O(logn),Query: O(logn+k)

其实Segment Tree的思想还是很好理解的,比我们之前讲过的Binary Indexed Tree要容易理解的多(回复 SP3 获取视频),但是代码量又是另外一回事情了…

回到一开始讲的公司组织结构上面,假设一个公司有200个底层员工,

最原始的信息(元素的值)只掌握在他们工手里,层层上报。每个manager把他所管理的人的元素值求和之后继续上报,直到CEO。CEO知道但仅知道0-199的和。

当你问CEO,5到199的和是多少?他手上只有0-199的和,一下子慌了,赶紧找来CTO,CFO说你们把5到199的和给报上来,CFO一看报表,心中暗喜:还好我负责的这个区间(100~199)已经计算过了,就直接把之前的总和上报了。CTO一看报表,自己负责0-99这个区间,只知道0-99的和,但5-99的和,还是问下面的人吧… 最后结果再一层层返回给CEO。

说到这里大家应该已经能想象Segment Tree是怎么工作了吧:

每个leaf负责一个元素的值

每个parent负责的范围是他的children所负责的范围的union,并把所有范围内的元素值相加。

同一层的节点没有overlap。

root存储的是所有元素的和。

所以一个SegmentTreeNode需要记录以下信息

start #起始范围
end #终止范围
mid #拆分点,通常是 (start + end) // 2
val #所有子元素的和
left #左子树
right #右子树

Update: 由于每次只更新一个元素的值,所以CEO知道这个员工是哪个人管的,派发下去就行了,然后把新的结果再返回回来。

T(n) = T(n/2) + 1 => O(logn)

Query: query的range可以是任意的,就有以下三种情况:

case 1: 这个range正好和我负责的range完全相同。比如sumQuery(CTO, 0, 99),这个时候CTO直接返回已经求解过的所有下属的和即可。

case 2: 这个range只由我其中一个下属负责。比如sumQuery(CEO, 0, 10),CEO知道0~10全部由CFO负责,那么他就直接返回sumQuery(CTO, 0, 10)。

case 3: 这个range覆盖了我的两个下属,那么我就需要调用2次。比如sumQuery(CEO, 80, 120),CEO知道0~99由CTO管,100~199由CFO管,所以他只需要返回:

sumQuery(CTO, 80, 99) + sumQuery(CFO, 100, 120)

由此可见sumQuery的时间复杂度是不确定的,运气好时O(1),运气不好时是O(logn+k),k是需要访问的节点的数量。

我做了一个实验,给定N,尝试所有的(i,j)组合,看sumQuery的最坏情况和平均情况,结果如下图:

Query需要访问到的节点数量的worst和average case。Worst case 大约访问 4*logn – 3 个节点,这个数字远远小于n。和n成对数关系。

虽然不像Binary Indexed Tree query是严格的O(logn),但Segment tree query的worst case增长的非常慢,可以说是对数级别的。当N是2^20的时候,worst case也“只需要”访问77个节点。

最后我们再来讲一下这棵树是怎么创建的,其实方法有很多种,一分为二是比较常规的一种做法。

CEO管200人,那么就找2个人(CTO,CFO各管100人。CTO管100人,再找2个VP各管50人,以此类推,直到manager管2个人,2个人都是底层员工(leaf),没有人管(双关)。

CEO = buildTree(0, 199)

CEO.left # CTO 负责0~99
CEO.right # CFO 负责100~199


Query: # of nodes visited: Average and worst are both ~O(logn)

Applications

LeetCode 307 Range Sum Query – Mutable

C++

Python3