线性结构 | Ziuch の Blog

type

status

date

slug

summary

0. 本节习题总览

双指针习题1： 1669. 合并两个链表

双指针习题2：21. 合并两个有序链表

循环 or 递归：206. 反转链表

快慢指针：19. 删除链表的倒数第 N 个结点

栈习题1：20. 有效的括号

栈习题2：682. 棒球比赛

单调栈习题1：739. 每日温度

单调栈+字典：496. 下一个更大元素 I

队列习题：剑指 Offer II 042. 最近请求次数

栈和队列综合习题：1700. 无法吃午餐的学生数量

单调队列习题：239. 滑动窗口最大值

优先队列习题：1046. 最后一块石头的重量

字符串哈希+二分：1044. 最长重复子串

KMP算法习题：28. 找出字符串中第一个匹配项的下标

1. 链表

💡

一般来说，我们会设置一个虚拟的头结点dummy，这样一来无论链表是否为空，我们在实现的时候都不需要特判，判断链表为空的条件dummy.next == None

💡

由于链表本身就是递归定义的结构，所以几乎所有链表有关的操作都可以通过递归来实现，碰到链表的题目时，尽量使用递归来完成

💡

利用快慢指针减少对链表的遍历次数

💡

注意访问链表值之前一定需要先判空！！

1.1 链表概念

链表包含单链表，双链表，循环单链表，实际应用中的功能不同，但实现方式都差不多

1.2 单链表操作

1.2.1 创建

💡

创建分为头插法和尾插法，头插法得到的链表是逆序的

1.2.2 遍历

1.2.3 插入

1.2.4 删除

链表习题：

双指针习题1： 1669. 合并两个链表

双指针习题2：21. 合并两个有序链表

循环 or 递归：206. 反转链表

快慢指针：19. 删除链表的倒数第 N 个结点

2. 栈

💡

仅在尾部插入和删除的线性结构，满足先进后出的特点

💡

我们可以通过python的list内的append()和pop()函数来实现一个栈

💡

弹栈或读取栈顶元素前，一定要先判空！！

可以点这跳转哈→

2.1 代码实现

栈习题1：20. 有效的括号

栈习题2：682. 棒球比赛

2.2 单调栈

💡

在O(n)时间内在找到列表内所有数的左/右侧找到比当前元素大/小的数

💡

抓住特点，单调，即栈内的元素大小是单调的(递增/递减)

💡

每次元素入栈前，先依据大小关系将栈内一部分元素弹栈

💡

及时去掉无用数据，保证栈中元素有序。

单调栈习题1：739. 每日温度

单调栈+字典：496. 下一个更大元素 I

3. 队列

💡

在一头插入，另一头删除的线性结构，满足先进先出的特点

💡

不同于栈，直接用列表作为队列的效率很低。因为，在列表末尾添加和删除元素非常快，但在列表开头插入或移除元素却很慢（因为所有其他元素都必须移动一位）

💡

用 collections.deque，可以快速从两端添加或删除元素。其中append()和pop()都是默认从队列的右边(尾部)入队和出队(栈)，appendleft()和popleft() 则是左边即队头

💡

出队或读取队头元素前，一定要先判空！！

3.1 代码实现

队列习题：剑指 Offer II 042. 最近请求次数

栈和队列综合习题：1700. 无法吃午餐的学生数量

3.2 单调队列(滑动窗口)

💡

在O(n)时间内计算全部滑动窗口的最值

💡

抓住特点，单调，即队列内的元素大小是单调的(递增/递减)

💡

每次元素入队前，先根据队列长度限制，超过长度部分的元素从队头出队，随后依据大小关系将队内一部分元素从队尾出队

单调队列习题：239. 滑动窗口最大值

3.3 优先队列(堆)

💡

以一定的优先级来排列顺序的队列

💡

堆(完全二叉树)是实现优先队列的一种手段

💡

用heapify()将列表初始化成一个堆(小根堆)，heappush()和heappop()用于加入和弹出，若要转化成大根堆，给每个元素乘上-1即可

💡

堆可以在O(logn)的时间内求得数组最值，可以用来解决Top-k问题

3.3.1 代码实现

优先队列习题：1046. 最后一块石头的重量

4. 字符串

4.1 字符串哈希

💡

将字符串到一个整数的映射，可以在O(1)时间判断两个字符串是否相等，需要用O(n)时间进行预处理

💡

把每个字符看做P进制数，然后用前缀和的思想减法求区间哈希

4.1.1 代码实现

字符串哈希+二分：1044. 最长重复子串

4.2 KMP 子串匹配

💡

在O(n + m)的时间内求出模式串p在匹配串s内出现的所有位置

💡

当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了

算法优化过程

next数组示例

4.2.1 代码实现

KMP算法习题：28. 找出字符串中第一个匹配项的下标