算法训练营 - 学习笔记 - 第一周

一直想学习下算法，在 极客大学の小耳朵 同学的好几波攻势及一再推荐下，报名了算法训练营（池老师应该给她加鸡腿🍗）。老实说，我也不知道能不能抽出那么多时间学习（工作+生活+带 2 娃，而且我最近也不确定是不是要在技术这条路上继续走下去，还是说要转 System Engineer, 看产品需求、测试需求、生命周期、安全性、连接性、可维护性、可清洁性等，有点迷茫😵），只能自勉，加油💪💪

划重点

1. 学习算法训练营最大的误区：刷题只刷一遍。

2. 学习算法训练营的一般方法：

3. 先看题 5-10 分钟

4. 没有思路，直接看高分题解（不要死磕，不要不服气觉得自己能写出来或者再抢救一下什么的）

5. 五遍刷题法（五毒神掌）

6. 去到 Leetcode 国际站看老外解题的 most votes

7. 不断反复训练变成肌肉记忆

8. 没有解题思路的时候，想想以下：

9. 暴力求解法

10. 找最近重复子问题

11. 升维

12. 空间换时间

13. 排序双指针理论

14. 先排序，左右夹逼，双指针法

15. 任何复杂的逻辑都是由以下的语句构成，CPU 只会做重复的事情：

16. if else, for, while, recursion

17. 要熟悉的办法就是多做，没有任何巧妙的地方！

第 3 课 数组、链表、跳表

数组(Array)：

• 内存中一块连续的存储区域

• 查找方便，时间复杂度 O(1)

• 插入、删除困难，O(n)

链表(Link List)：

• 单链表、双链表、循环链表

• node -> value,

• node -> next, prev, head, tail,

• 查找困难 O(n)

• 插入、删除方便， O(1)

跳表(Skip List):

• 链表升维，添加索引，空间换时间

• n/2, n/4, n/8,

• 第 k 层， n / (2^k) = 2, k = log2(n/2) -> log2(n) - 1

第 4 课 栈、队列、优先队列、双端队列

栈(Stack):

• 先进后出，后进先出

队列(Queue):

• 先进先出

• 插入删除 O(1)

• 查询 O(n)

优先队列(Priority Queue):

• 插入操作：O(1)

• 取出操作：O(LogN) - 按照元素的优先级取出

• 底层实现复杂：heap, bst, treap

双端队列(Dequeue, Double-Ended-Queue):

• 首尾都能插入和删除

参考链接

https://u.geekbang.org/lesson/144?article=246042

https://u.geekbang.org/lesson/144?article=246047