section-1

数组、链表、跳表、栈、队列

总结

1. 一维数据结构加速通常需要升为二维
2. 好文：数据结构与算法之美笔记 : 平衡二叉树、跳表、B - Tree、 B + Tree 、 B * Tree

数组

暂无

链表

head -> node -> tail

快慢指针的特性：每轮移动之后两者的距离会加一，如果一个链表存在环，那么快慢指针必然会相遇。

如果存在环，如何判断环的长度呢？方法是，快慢指针相遇后继续移动，直到第二次相遇。两次相遇间的移动次数即为环的长度。

跳表

1. 链表元素是有序的
2. 出现的很晚（1990年）
3. 对标平衡二叉搜索树「AVL Tree」和二分查找
4. 原理简单、容易实现、方便扩展、效率更高
5. 新的项目均使用跳表替代平衡二叉搜索树
6. 空间复杂度是O(n)，但是实际复杂度大于原链表

栈和队列

• stack：先进后出 LIFO last in first out
• queue：先进先出 FIFO first in first out
• deque：同时有以上两种特性

Priority Queue

1. 底层数据结构 Heap、BST「binary search tree」

API

• peek()

• push()

• pop()

• offer()

• poll()

复杂度

数组	时间复杂度	空间复杂度
插入删除	O(n)	O(n)
随机访问	O(1)	O(n)

链表	时间复杂度	空间复杂度
插入删除	O(1)	O(n)
随机访问	O(n)	O(n)

跳表	时间复杂度	空间复杂度
插入删除	O(log n)	O(n)
搜索	O(log n)	O(n)

栈和队列	时间复杂度	空间复杂度
插入删除	O(1)	O(n)
搜索	O(n)	O(n)

优先队列	时间复杂度	空间复杂度
插入	O(log n)	O(n)
取出	O(log n)	O(n)

心得

这周学习的知识内容还好，只是每节的LeetCode题目比较多，在做题的同时，发现有同类型的题目，故一并进行了练习，导致花的时间比较多，具体可参见本文末尾。

发现问题及后续准备如下：

1. 「困难」难度的题目，大多解析都需要研究半小时以上才勉强理解，需要多加练习。
2. 除了每节提到的题目外，又额外做了一些题目，导致课后作业都未完全完成，之后需要尽量专注于每节作业，有余力再看其他题目。
3. 每道题目均按照五毒法练习，保证真正熟练。

LeetCode

数组

题目	项目链接	leetcode
26. 删除排序数组中的重复项	RemoveDuplicatesFromSortedArray	remove-duplicates-from-sorted-array
1. 两数之和	TwoSum	two-sum
15. 三数之和	ThreeSum	3sum
283. 移动零	MoveZeroes	move-zeroes
11. 盛最多水的容器	ContainerWithMostWater	container-with-most-water
70. 爬楼梯	ClimbingStairs	climbing-stairs
66. 加一	PlusOne	plus-one
189. 轮转数组	RotateArray	rotate-array
88. 合并两个有序数组	MergeSortedArray	merge-sorted-array
---
16. 最接近的三数之和	ThreeSumClosest	3sum-closest
18. 四数之和	FourSum	4sum

链表

题目	项目链接	leetcode
206. 反转链表	ReverseLinkedList	reverse-linked-list
21. 合并两个有序链表	MergeTwoSortedLists	merge-two-sorted-lists
141. 环形链表	LinkedListCycle	linked-list-cycle
142. 环形链表 II	LinkedListCycleIi	linked-list-cycle-ii
24. 两两交换链表中的节点	SwapNodesInPairs	swap-nodes-in-pairs
25. K个一组翻转链表	ReverseNodesInKGroup	reverse-nodes-in-k-group

栈和队列

题目	项目链接	leetcode	备注
20. 有效的括号	ValidParentheses	valid-parentheses
678. 有效的括号字符串*	ValidParenthesisString	valid-parenthesis-string
155. 最小栈*	MinStack	min-stack
84. 柱状图中最大的矩形**	LargestRectangleInHistogram	largest-rectangle-in-histogram	单调栈
239. 滑动窗口最大值	SlidingWindowMaximum	sliding-window-maximum
71. 简化路径	SimplifyPath	simplify-path
150. 逆波兰表达式求值	EvaluateReversePolishNotation	evaluate-reverse-polish-notation
42. 接雨水*	TrappingRainWater	trapping-rain-water	单调栈、DP

参考资料

LRU缓存算法 Redis 跳表实现