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

这周比较忙，都没怎么刷题。。。

划重点

1. 做题时，先想所有可能的解决办法，然后选一个你认为最合适的

2. 做题四件套

3. Clarification

4. Confirm the requirements with related people(interviewer, etc.)

5. Possible Solutions

6. Find optimal Time & Space Complexity

7. Coding

8. Testing codes

9. 时间和空间复杂度

10. O(1): Constant Complexity 常数复杂度

11. O(logn): Logarithmic Complexity 对数复杂度

12. O(n): Linear Complexity 线性时间复杂度

13. O(n²): N square Complexity 平方

14. O(n³): N cubic Complexity 立方

15. O(2^n): Exponential growth 指数，例如：斐波那契数列 2^n

16. O(n!): Factorial 阶乘

第 5 课 哈希表、映射、集合

哈希表(Hash table):

• 按照 Key-Value 进行访问的数据结构

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

• 哈希碰撞，如果 Key 重复，可将 Value 串成一个链表（散列表）

映射(Map): Key -> Value,

集合(Set):

Map, Set 可用 hash table 来实现，查找时间复杂度 O(1)

第 6 课 树、二叉树、二叉搜索树

树(Tree):

• n 个有限节点组成的一个具有层次关系的集合

• 树和图的区别：看有没有环

二叉树(Binary Tree):

• 每个节点最多只能有两棵子树、且有左右之分

• 遍历：

• 前序(Pre-Order): 根->左->右

• 中序(In-Order): 左->根->右

• 后序(Post-Order): 左->右->根

二叉搜索树(Binary Search Tree):

• 左子树或者右子树大于/小于根

• 查询、插入 O(logn)

第 6 课 堆、二叉堆、图

堆(heap):

• 一个树的数组对象

二叉堆

• 完全二叉堆或者近似完全二叉堆

图

• 顶点、边、入度出度