【243 - 毕业总结】

# 学习总结
## 概述
> 主要贴合脑图进行课程总结，并将课程中提到的需要重点记忆的代码模板，和各个知识点的LeetCode题目进行汇总。便于后面的思考与刷题。

* 核心：
1. 重在理解，避免死磕
2. 重在练习，五遍刷题
3. 机器思维，避免人肉

* [数据结构脑图](https://naotu.baidu.com/file/b832f043e2ead159d584cca4efb19703?token=7a6a56eb2630548c)
* [算法脑图](https://naotu.baidu.com/file/0a53d3a5343bd86375f348b2831d3610?token=5ab1de1c90d5f3ec)

### 复杂度分析
#### 时间复杂度
* [如何理解算法时间复杂度表示法](https://www.zhihu.com/question/21387264)
* [主定理](https://zh.wikipedia.org/wiki/%E4%B8%BB%E5%AE%9A%E7%90%86)
* O(1) 常数复杂度：Hash表，缓存
* O(log n) 对数复杂度：二分查找，二叉搜索树
* O(n) 线性复杂度：大多数遍历
* O(n^2): 双重for循环
* O(2^n)：递归

#### 空间复杂度
* **空间换时间，升维**：在大多数情况下，会选择牺牲空间复杂度，来提高时间复杂度
* 一般在算法中，更多的是考虑是否为“原地算法”，即是否需要申请额外的空间。

## 数组与链表
> **非受限线性表**：指的就是不受规则限制，区别于栈和队列。

* 数组和链表是所有数据结构的基础，基本上所有数据结构都可以基于数组和链表实现。
* 数组和链表之间重点掌握区别，数组的**查找**时间复杂度是O(1)，而链表的**增加和删除**时间复杂度为O(1)。
* 数组：注意防止越界
* 链表：单链表、双向链表、循环链表、静态链表（借助数组，伴随向后继节点的指针）

### LeetCode
#### Array
* [盛最多水的容器](https://leetcode-cn.com/problems/container-with-most-water/) -- 左右双指针夹逼
* [移动零](https://leetcode-cn.com/problems/move-zeroes/) -- 快慢指针
* [两数之和](https://leetcode-cn.com/problems/two-sum/) -- 哈希表记录
* **[三数之和](https://leetcode-cn.com/problems/3sum/)** -- 排序，左右双指针夹逼/哈希表记录
* [删除排序数组中的重复项](https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/) -- 快慢指针
* **[合并两个有序数组](https://leetcode-cn.com/problems/merge-sorted-array/)** -- 额外空间+双指针，同于归并排序中的merge
* [加一](https://leetcode-cn.com/problems/plus-one/)

#### Linked
* [反转链表](https://leetcode-cn.com/problems/reverse-linked-list/)
* [两两交换链表中的节点](https://leetcode-cn.com/problems/swap-nodes-in-pairs/)
* [环形链表](https://leetcode-cn.com/problems/linked-list-cycle/) -- 缓存
* [合并两个有序链表](https://leetcode-cn.com/problems/merge-two-sorted-lists/)

## 栈和队列
> **受限线性表**：需要满足一定的规则，即先进后出或者先进先出等。

* 栈和队列的重点是掌握其在特殊场合下的应用。
* 栈：先进后出，FILO。应用：浏览器前进后退、括号匹配、表达式计算。
* 队列：先进先出，FIFO。
* 队列的拓展：双端队列（两边均可入队和出队），优先队列（根据优先级来出队）。
* [Java PriorityQueue 源码](https://docs.oracle.com/javase/10/docs/api/java/util/PriorityQueue.html)

### LeetCode
#### Stack
* **[有效的括号](https://leetcode-cn.com/problems/valid-parentheses/)**
* [最小栈](https://leetcode-cn.com/problems/min-stack/)
* [柱状图中最大的矩形](https://leetcode-cn.com/problems/largest-rectangle-in-histogram/)
* **[滑动窗口](https://leetcode-cn.com/problems/sliding-window-maximum/)**
* [接雨水](https://leetcode-cn.com/problems/trapping-rain-water/?utm_source=LCUS&utm_medium=ip_redirect_q_uns&utm_campaign=transfer2china)

#### Queue
* [设计循环双端队列](https://leetcode-cn.com/problems/design-circular-deque/?utm_source=LCUS&utm_medium=ip_redirect_q_uns&utm_campaign=transfer2china)

## 哈希表、映射、集合
* 哈希表：又称散列表。重点需要注意哈希冲突，设计好的哈希函数可以减少重复性，但不能完全避免哈希冲突。常用拉链表（散列表+链表）解决哈希冲突，如HashMap。
* 映射：Map。K/V键值对，key不重复
* 集合：Set。key不重复
### LeetCode
* [有效的字母异位词](https://leetcode-cn.com/problems/valid-anagram/description/)
* [字母异位词分组](https://leetcode-cn.com/problems/group-anagrams/)
* [两数之和](https://leetcode-cn.com/problems/two-sum/description/)

## 二叉树、二叉搜索树
* 顺序和链式结构都可以实现。
* 遍历方式：广度优先遍历（BFS）、深度优先遍历（DFS）；DFS分为前序遍历（根左右）、中序遍历（左根右）、后序遍历（左右根）。重点掌握所有的模板。
* 分类：完全二叉树（除了叶子节点外，其余节点的度均为2的二叉树），满二叉树（最后一层全是叶子节点的完全二叉树），二叉搜索树等。
* 二叉搜索树的中序遍历即为有序遍历。
* [自平衡二叉搜索树（AVL）的动图演示](https://visualgo.net/zh/bst)
### LeetCode
* **[二叉树的前序遍历](https://leetcode-cn.com/problems/binary-tree-preorder-traversal/)**
* **[二叉树的中序遍历](https://leetcode-cn.com/problems/binary-tree-inorder-traversal/)**
* [N叉树的前序遍历](https://leetcode-cn.com/problems/n-ary-tree-preorder-traversal/description/)
* [N叉树的后序遍历](https://leetcode-cn.com/problems/n-ary-tree-postorder-traversal/)
* [N叉树的层序遍历](https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal/) -- 广度优先搜索

## 递归
* [递归模板](https://shimo.im/docs/DjqqGCT3xqDYwPyY/read)
* 核心：递归四部曲，终止条件、执行当前层逻辑、下坠、清理当前层的状态。
```java
public void recur(int level, int param) { 

  // terminator 
  if (level > MAX_LEVEL) { 
    // process result 
    return; 
  } 

  // process current logic 
  process(level, param); 

  // drill down 
  recur( level: level + 1, newParam); 

  // restore current status 
 
}
```
### LeetCode
* **[爬楼梯问题](https://leetcode-cn.com/problems/climbing-stairs/)** -- 记忆化递归
* [括号生成](https://leetcode-cn.com/problems/generate-parentheses/)
* [翻转二叉树](https://leetcode-cn.com/problems/invert-binary-tree/description/)
* [验证二叉搜索树](https://leetcode-cn.com/problems/validate-binary-search-tree/)
* [二叉树的最大深度](https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/)、[二叉树的最小深度](https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/)
* [二叉树的序列化和反序列化](https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/)
* [二叉树的最近公共祖先](https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/)
* [从前序和中序遍历序列构造二叉树](https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/)
* [组合](https://leetcode-cn.com/problems/combinations/)
* [全排列](https://leetcode-cn.com/problems/permutations/)、[全排列 II](https://leetcode-cn.com/problems/permutations-ii/)

## 分治、回溯
[分治代码模板](https://shimo.im/docs/3xvghYh3JJPKwdvt/read)
```python
def divide_conquer(problem, param1, param2, ...): 
  # recursion terminator 
  if problem is None: 
	print_result 
	return 

  # prepare data 
  data = prepare_data(problem) 
  subproblems = split_problem(problem, data) 

  # conquer subproblems 
  subresult1 = self.divide_conquer(subproblems[0], p1, ...) 
  subresult2 = self.divide_conquer(subproblems[1], p1, ...) 
  subresult3 = self.divide_conquer(subproblems[2], p1, ...) 
  …

  # process and generate the final result 
  result = process_result(subresult1, subresult2, subresult3, …)
	
  # revert the current level states
```
### LeetCode
* **[括号生成](https://leetcode-cn.com/problems/generate-parentheses/)**
* [求x的n次幂](https://leetcode-cn.com/problems/powx-n/)
* [子集](https://leetcode-cn.com/problems/subsets/)
* **[多数元素](https://leetcode-cn.com/problems/majority-element/description/)**
* [电话号码的字母组合](https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/)
* **[N皇后](https://leetcode-cn.com/problems/n-queens/)**

## BFS、DFS
* [BSF模板](https://shimo.im/docs/P8TqKHGKt3ytkYYd/read)
* 核心：维护一个queue队列，建立一个访问记录visited集合，有时候还需要在节点处记录当前的层数level。
```python
def BFS(graph, start, end):
    visited = set()
	queue = [] 
	queue.append([start]) 

	while queue: 
		node = queue.pop() 
		visited.add(node)

		process(node) 
		nodes = generate_related_nodes(node) 
		queue.push(nodes)

	# other processing work 
	...
```
* [DFS模板](https://shimo.im/docs/ddgwCccJQKxkrcTq/read)
* 核心：DFS在非递归写法时，是维护一个stack栈
```python
//递归写法
visited = set() 

def dfs(node, visited):
    if node in visited: # terminator
    	# already visited 
    	return 

	visited.add(node) 

	# process current node here. 
	...
	for next_node in node.children(): 
		if next_node not in visited: 
			dfs(next_node, visited)
			
//非递归写法
def DFS(self, tree): 

	if tree.root is None: 
		return [] 

	visited, stack = [], [tree.root]

	while stack: 
		node = stack.pop() 
		visited.add(node)

		process (node) 
		nodes = generate_related_nodes(node) 
		stack.push(nodes) 

	# other processing work 
	...
```
### LeetCode
* [二叉树的层序遍历](https://leetcode-cn.com/problems/binary-tree-level-order-traversal/#/description)
* [最小基因变化](https://leetcode-cn.com/problems/minimum-genetic-mutation/#/description)
* [在每个树行中找最大值](https://leetcode-cn.com/problems/find-largest-value-in-each-tree-row/#/description)
* **[单词接龙](https://leetcode-cn.com/problems/word-ladder/description/)** -- DFS，双向DFS
* [单词接龙II](https://leetcode-cn.com/problems/word-ladder-ii/description/)
* **[岛屿的数量](https://leetcode-cn.com/problems/number-of-islands/)** -- 下沉周围岛屿
* [扫雷游戏](https://leetcode-cn.com/problems/minesweeper/description/)

## 贪心算法
* 贪心算法是**弱化版的动态规划**。很多时候都得**先判断是否能用贪心算法**解决，再使用贪心算法。如最经典的`找零`问题，在保证大的币种肯定是小的币种的倍数的情况下，可以利用贪心算法解决问题。
### LeetCode
[柠檬水找零](https://leetcode-cn.com/problems/lemonade-change/solution/)

## 二分查找
* 特点：**有序**、**有界**、**能够通过索引随机访问**。
* [二分查找模板](https://shimo.im/docs/hjQqRQkGgwd9g36J/read)
```python
left, right = 0, len(array) - 1 
while left <= right: 
	  mid = (left + right) / 2 
	  if array[mid] == target: 
		    # find the target!! 
		    break or return result 
	  elif array[mid] < target: 
		    left = mid + 1 
	  else: 
		    right = mid - 1
```
> 注意，一般防止越界，第三行代码会改写为`mid = right + (left - right) >> 1`
* [Fast InvSqrt() 扩展阅读](https://www.beyond3d.com/content/articles/8/)

### LeetCode
* [x的平方根](https://leetcode-cn.com/problems/sqrtx/)
* [有效的完全平方数](https://leetcode-cn.com/problems/valid-perfect-square/)
* [搜索旋转排序数组](https://leetcode-cn.com/problems/search-in-rotated-sorted-array/)
* [搜索二维矩阵](https://leetcode-cn.com/problems/search-a-2d-matrix/)
* [搜索旋转排序数组中的最小值](https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/)

## 动态规划
> 动态规划在大多数情况下和记忆化递归的时间复杂度相近，如经典的[爬楼梯问题](https://leetcode-cn.com/problems/climbing-stairs/description/)，既可以使用斐波那契数列，`f(n) = f(n-1) + f(n-2)`，加上缓存cache的记忆化递归的方式求解，也可以使用动态规划，利用dp方程，`dp[i] = dp[i-1] + dp[i-2]`进行求解。

* 自底向上递推
* 核心：**状态转移方程**、**最近重复子问题**、**最优子结构**

### LeetCode
* [不同路径](https://leetcode-cn.com/problems/unique-paths/)
* [不同路径 II](https://leetcode-cn.com/problems/unique-paths-ii/)
* [最长公共子序列](https://leetcode-cn.com/problems/longest-common-subsequence/)
* [三角形最短路径和](https://leetcode-cn.com/problems/triangle/description/)
* [最大子序和](https://leetcode-cn.com/problems/maximum-subarray/)
* [乘积最大子序列](https://leetcode-cn.com/problems/maximum-product-subarray/description/)
* [硬币兑换](https://leetcode.com/problems/coin-change/description/)
* [打家抢劫](https://leetcode-cn.com/problems/house-robber/)、[打家抢劫 II](https://leetcode-cn.com/problems/house-robber-ii/description/)
* [买买股票的最佳时机](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/#/description)、[股票 II](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/)、[股票 III](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/)、[股票（含冷冻期）](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/)、[股票 IV](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/)、[股票（含手续费）](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/) -- [团灭股票问题方法](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/yi-ge-fang-fa-tuan-mie-6-dao-gu-piao-wen-ti-by-l-3/)

## 字典树
* 字典树，又称前缀树、Trie树。主要应用于搜索时前缀单词提示。
* 核心：理解和记忆Trie树的代码模板
* [Trie树模板](https://shimo.im/docs/Pk6vPY3HJ9hKkh33/read)
```python
class Trie(object):
  
	def __init__(self): 
		self.root = {} 
		self.end_of_word = "#" 
 
	def insert(self, word): 
		node = self.root 
		for char in word: 
			node = node.setdefault(char, {}) 
		node[self.end_of_word] = self.end_of_word 
 
	def search(self, word): 
		node = self.root 
		for char in word: 
			if char not in node: 
				return False 
			node = node[char] 
		return self.end_of_word in node 
 
	def startsWith(self, prefix): 
		node = self.root 
		for char in prefix: 
			if char not in node: 
				return False 
			node = node[char] 
		return True
```

### LeetCode
* [实现Trie树](https://leetcode-cn.com/problems/implement-trie-prefix-tree/solution/)
* [单词搜索 II](https://leetcode-cn.com/problems/word-search-ii/)

## 并查集
* 并查集，主要应用于解决站队问题，即朋友圈问题。
* 核心：熟悉并查集的基本操作，即初始化、查询、合并。
* [并查集模板](https://shimo.im/docs/ydPCH33xDhK9YwWR/read)
```java
class UnionFind { 
	private int count = 0; 
	private int[] parent; 
	public UnionFind(int n) { 
		count = n; 
		parent = new int[n]; 
		for (int i = 0; i < n; i++) { 
			parent[i] = i;
		}
	} 
	public int find(int p) { 
		while (p != parent[p]) { 
			parent[p] = parent[parent[p]]; 
			p = parent[p]; 
		}
		return p; 
	}
	public void union(int p, int q) { 
		int rootP = find(p); 
		int rootQ = find(q); 
		if (rootP == rootQ) return; 
		parent[rootP] = rootQ; 
		count--;
	}
}
```

### LeetCode
* **[朋友圈问题](https://leetcode-cn.com/problems/friend-circles/)**
* [岛屿数量](https://leetcode-cn.com/problems/number-of-islands/)
* [被围绕的区域](https://leetcode-cn.com/problems/surrounded-regions/)

【243 - 毕业总结】 #1553

Description

学习总结

概述

复杂度分析

时间复杂度

空间复杂度

数组与链表

LeetCode

Array

Linked

栈和队列

LeetCode

Stack

Queue

哈希表、映射、集合

LeetCode

二叉树、二叉搜索树

LeetCode

递归

LeetCode

分治、回溯

LeetCode

BFS、DFS

LeetCode

贪心算法

LeetCode

二分查找

LeetCode

动态规划

LeetCode

字典树

LeetCode

并查集

LeetCode

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions