学习笔记|算法
1.框架
1.1 如何精通一个领域?
Chunk it up 切碎知识点
Deliberate Practicing 刻意练习
- 做题做五遍
Feedback 反馈
- 主动式反馈:看高手代码
- 被动式反馈:高手指点
1.2 数据结构
所有的数据结构不是直接创造的,而是现实中已有的逻辑,然后抽象成计算机语言。
一维数据结构
基础:数组 array(string)、链表 linked list
高级:栈 stack、队列 queue、双端队列 deque、集合 set、映射 map(hash or map)
二维数据结构
基础:树 tree、图 graph、
高级:二叉搜索树 binary search tree、红黑树 red-black tree,AVL、堆 heap、并查集 disjoint set、字典树 Trie
特殊数据结构
- 位运算 Bitwise、布隆过滤器 BloomFilter
- LRU Cache
1.3 算法
if-else,switch:branch 跳转语句
for,while loop:lteation 循环语句
递归 Recursion(Divide & Conquer 分治,Backtrace 回溯)
搜索 Search:深搜 Depth frist search,广搜 Breadth frist seach
动态规划 Dynamic Program
二分查找 Binary Search
贪心 Greedy
数学 Math,几何 Geometry
1.4 如何做算法题
Clarification:理解清楚题意
Possible solutions:把所有可能的方法过一遍
- compare 比较时间空间复杂度
- optimal 最理想的
Coding:多写
Test case:有始有终
(1)第一遍做题
10 分钟:读题 + 思考。
直接看解法:多解法,比较解法优劣。
背诵和默写下来(理解)。
(2)第二遍做题
经过第一遍之后,马上自己写。
debug。
直至通过、优化。
(3)第三遍做题
过了一天之后做题
(4)第四遍做题
过了一周之后做题
(5)第五遍做题
面试前一周练习
1.5 自顶向下编程
先写主干逻辑。
再写细节。
1.6 遇见题目没有思路?
能不能暴力?
暴力可不可以优化?(一维变二维,空间换时间)
…
基本情况能否解决?
找重复子问题。
数学归纳法——递推公式
…
2.时间复杂度
Big O notation
O(1):Constant Complexity 常数时间复杂度
O(log(n)):Logarithmic Complexity 对数时间复杂度
O(n):Linear Complexity 线性时间复杂度
O(n^2):N square Complexity 平方
O(n^3):N cube Complexity 立方
O(2^n):Exponential Growth 指数
O(n!):Factorial 阶乘
举个例子:
(1)时间复杂度为 O(log(n))。
因为 2^x = n,所以 x = log2 (n)。底数2可省略。
1 |
|
(2)时间复杂度为 O(k^n)
1 |
|
按树状排列,最多有 n 层,每层 k 个,在本程序中,k = 2。所以最下一层有 2^n 个。
graph TD
A(fib_6) --> B(fib_5)
A --> C(fib_4)
B --> D(fib_4)
B --> E(fib_3)
C --> F(fib_3)
C --> G(fib_2)
D --> J(fib_3)
D --> K(fib_2)
J --> L(fib_2)
J --> M(fib_1)
L --> N(fib_1)
2.1 主定理
2.2 思考
二叉树的前序/中序/后序遍历,时间复杂度是多少?
O(n),因为每个节点访问一次。
图的遍历,时间复杂度是多少?
O(n),因为每个节点访问一次。
搜索算法:深搜、广搜,时间复杂度是多少?
O(n),因为每个节点搜索一次。
二分查找
O(log(n)),次数为x,2^x = n。
3.数组、链表、跳表
3.1 数组 array
连续的一段内存空间,利用内存管理器管理。
随机访问时间复杂度:O(1)。
插入删除效率低,时间复杂度:O(n)。
3.2 链表 linked list
不需要一段连续的内存空间。
随机访问效率低,时间复杂度:O(n)。
插入删除效率高,时间复杂度:O(1)。
3.3 跳表 skip list
为了补足链表随机访问效率低的缺点。
(1)思想
主要思想:升维、空间换时间。
做法:增加多级索引,将一维链表,升级为二维数据结构。
(2)索引个数
n 个元素最多有多少级索引?
log2(n) - 1 个索引,因为 2^x = n。
(3)随机读取的时间复杂度
O(log(n)),每级索引都要访问一次,log2(n) - 1 个索引加上本身的链表,一共访问 log2(n) 次。
(4)空间复杂度
O(n),从最高级索引到第一级索引:{ n/2,n/4,n/8,… 8,4,2 },求和 = a1*((1 - q^n) / (1 - q))= n - 1。
(5)实际跳表形态
由于增加和删除,会使索引不完全工整,有的地方会多跨几步,有的地方会少跨几步。
索引的维护成本高:每次插入和删除的时候,索引都要更新一遍。
3.4 例题
一维数组的坐标变换。
题目 | 要点 |
---|---|
#283. 移动零 | 快慢指针(不一定是指针) |
#11. 盛最多水的容器 | 左右夹逼,左右向中间收敛 |
动态规划 | |
#1. 两数之和 | 双指针(相向而行,夹逼) 或者 哈希表 |
#15. 三数之和 | 双指针 |
#283. 移动零
i == 快指针,它从 0 遍历到 n;
j == 慢指针,它指的是第一个 0 的位置(如果 i 遍历到了 0),或者区间 [0, i] 中最后一个非零元素(如果 i 还未遍历到零)。
当 i 遍历到 非零数 时,和 j 位置的数交换,j++。我们将会发现:
慢指针之前的所有元素都是非零的。
快指针和慢指针之间的所有元素都是零。
1 |
|
#11. 盛最多水的容器
从两边向中间收敛,遍历 n 次。
最初以 0、n-1 为两边边界,宽度最长,但是高度不一定最高。
矮的一边向中间移动,以寻求更高的边界(宽度不一定够大,但是可以在高度上取得优势)。
移动边界后并计算容量,记录容量最大值。
1 |
|
#15. 三数之和
先排序,从 0 遍历每一个数 nums[k]。
nums[k] 右边的第一个元素索引标为 i;
nums[k] 右边的最后一个元素索引标为 j。
即 nums[i] 是子序列的最小元素,nums[j] 是子序列的最大元素。
如果 nums[i] + nums[j] < 0 - nums[k],最小元素右移动(变大)。
如果 nums[i] + nums[j] > 0 - nums[k],最大元素左移动(变小)。
特殊优化:
因为和为 0,比较特殊,也就意味着至少有一个元素 <= 0。if nums[k] > 0,break;
去重判断:
为了保持组合不重复,
k 遍历的点的值不可以重复。
i 在 i、j 的一个循环内,遍历的点的值不可以重复。
j 在 i、j 的一个循环内,遍历的点的值不可以重复。
那为什么不将重复的元素直接合并?
因为有 [-1, -1, 2] 这种组合。这种组合是当 nums[k] 和 nums[i] 重复的时候出现的。
1 |
|
4.堆栈和队列
4.1 Stack 栈
Last in,First out.
4.2 Queue 队
First in, First out.
4.3 Double-End Queue (Deque)双端队列
4.4 Priority Queue 优先队列
和 Queue 的区别在于,队列中的数,有顺序,当从尾部插入个数据,队列的数据会重新排列。
底层可能使用 heap 实现的。
4.5 复杂度
插入 | 删除/取出 | 查询 | |
---|---|---|---|
Stack \ Queue \ Deque | O(1) | O(1) | O(n),因为数据没有顺序 |
Priority Queue | O(1) | O(log N) | O(log N) |
4.6 例题
(1)什么问题用栈解决?
**最近相关性:**类似于洋葱,从内到外,或者从外到内一层层逐渐扩散的样子,而且最外层和最内层时一对。
(2)什么问题用队来解决?
强调 先来后到 的顺序。
所有的数据结构不是直接创造的,而是现实中已有的逻辑,然后抽象成计算机语言。
堆栈和队列的应用。
题目 | 要点 |
---|---|
#20. 有效的括号 | 最近相关性,stack |
#155. 最小栈 | 双栈(辅助栈),延伸:双栈实现队列 |
#84. 柱状图中最大的矩形 | 单调栈 + 哨兵(妙不可言,多看几遍) |
#239. 滑动窗口最大值 | 双端队列(单调队列) |
#155. 最小栈
要在常数时间内,找到最小值。显而易见的思路就是,在入栈的时候,进行比较,并保存最小值。但是问题是,如果最小值被弹出栈,新的最小值该如何寻找?
用辅助栈解决,当数据栈入栈一个数据,辅助栈同步的入栈此刻的最小值;反之,弹栈的话也是数据栈辅助栈同步的。
1 |
|
#84. 柱状图中最大的矩形
(1)先尝试暴力思路
1 |
|
在这个过程中,我们发现,后出现的高度可以先算出面积,符合 LIFO 的特点。
而且我们还发现,
当遇到高度比 heights[i] 高 时,继续遍历,
当遇到高度比 heights[i] 低 时,停止遍历。
符合单调增的情况,考虑单调栈(以单调增栈为例,当前元素小于栈顶,弹栈;当前元素大于栈顶,当前元素入栈)。这里不理解见视频分析:官方题解视频。
(2)使用单调栈
单调栈在添加元素的时候靠删除元素保持栈的单调性。
1 |
|
易错:
取 s.top() 之前,应该判断栈顶不为空!
注意特殊情况:栈中只有一个元素、栈中有全部元素。
栈中存入的应该是索引,便于计算宽度。
实现为代码如下:****
1 |
|
(3)单调栈 + 哨兵
为什么要加入哨兵?因为有两种情况,我们无法规避 if 讨论:
当栈中只有一个元素的时候,无法取出栈顶的前一个元素;
当所有元素全部入栈时,我们必须有段弹栈代码。
如何把两种特殊情况,统一起来呢?
加入哨兵,在 heights 数组前后,各加一个 0 的高度。
这样我们就可以不用考虑头和尾的情况了。
1 |
|
#239. 滑动窗口最大值
(1)如何 O(1) 找出最大值?——单调队列!
一堆数,增加一个数,可以 O(1) 找到最值,但是减小一个数,就不能 O(1) 找到最值。要想减小一个数,也能 O(1) 找到最值,需要用到单调队列。
单调队列在添加元素的时候靠删除元素保持队列的单调性(和单调栈一样)。
最大值在最前面,为 q.front().
当
nums[i] > 队尾元素
,队尾元素出队,直到nums[i] < 队尾元素
或者 队空【核心代码_2】。因为,当 num[i] 比前面的值都大时,前面的元素就没必要存在了(返回的永远是最大值)。
当
nums[i] < 队尾元素
或者 队空 时,nums[i] 入队。因为一旦,nums[i] 前面的最大值脱离窗口区间,nums[i] 就会成为新的最大值(只要它不被后面的数据取代)。
(2)如何及时让 脱离口区间的 老的 最大值出队?
队里不能存数值,应该存索引,便于知道,老的最大值是否已经脱离窗口区间【核心代码_1】。
1 |
|