Skip to content

431_Week 预习周 #4

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
GeekUniversity merged 2 commits into from
Oct 14, 2019
Merged

431_Week 预习周 #4

Changes from all commits
Commits
Show all changes
2 commits
Select commit Hold shift + click to select a range
ebc3040
431_Week 预习周
Oct 10, 2019
5c06a46
431_Week 预习周
Oct 10, 2019
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
57 changes: 56 additions & 1 deletion Week 预习周/id_431/NOTE.md
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -1,4 +1,59 @@
# NOTE

## 第一课

### 精通一个领域需要三步走

1. Chunk it up 切碎知识点
2. Deliberate Practicing 刻意练习
3. Feedback 反馈

### 数据结构简单分类

* 一维数据结构
* 基础：数组 array（String），链表 linked list
* 高级：栈 stack，队列 queue，双端队列 deque，集合 set，映射 map（hash or map），etc

* 二维数据结构
* 基础：树 tree，图 graph
* 高级：二叉搜索树 binary search tree（red-black tree，AVL），堆 heap，并查集 disjoint set，字典树 Trie，etc

* 特殊数据结构
* 位运算 Bitwise，布隆过滤器 BloomFilter
* LRU Cache

### 算法

* if-else，switch —> branch
* for，while loop —> Iteration
* 递归 Recursion（Divide & Conquer，Backtrace）
* 搜索 Search；深度优先搜索 Depth first search，广度优先搜索 Breadth first search，A\*，etc
* 动态规划 Dynamic Programming
* 二分查找法 Binary search
* 贪心 Greedy
* 数学 Math，几何 Geometry

### 切题四件套

* Clarification 多看题目和面试官多沟通，保证自己正确理解题目
* Possible solutions 想所有可能的解决方法，比较时间复杂度和空间复杂度
* Coding 编写程序
* Test cases 列举几个测试样例

### 脑图

![数据结构](http://processon.com/chart_image/5d9d49e2e4b03347e1381791.png?_=1570673460420)

![算法](http://processon.com/chart_image/5d9d537ce4b0a95d96080c2c.png?_=1570673503844)

## 第二课

### 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 阶乘