题解模板.md · Repetition/LeetCode4FLAG

# ⾯试常考算法模板 Cheat Sheet V4.1

版权归属：迈微（苏州）信息科技有限公司

## 目录 Menu

- [二分法 Binary Search](#二分法-binary-search)
  - [使用条件](#使用条件)
  - [复杂度](#复杂度)
  - [领扣例题](#领扣例题)
  - [代码模版](#代码模版)
- [双指针 Two Pointers](#双指针-two-pointers)
- [排序算法 Sorting](#排序算法-sorting)
- [⼆叉树分治 Binary Tree Divide & Conquer](#⼆叉树分治-binary-tree-divide-conquer)
- [⼆叉搜索树⾮递归 BST Iteratorp](#⼆叉搜索树⾮递归-bst-iterator)
- [宽度优先搜索 BFS](#宽度优先搜索-bfs)
- [深度优先搜索 DFS](#深度优先搜索-dfs)
- [动态规划 Dynamic Programming](#动态规划-dynamic-programming)
- [堆 Heap](#堆-heap)
- [并查集 Union Find](#并查集-union-find)
- [字典树 Trie](#字典树-trie)

## 二分法 Binary Search

### 使用条件

1. 排序数组 (30-40%是⼆分)
2. 当⾯试官要求你找⼀个⽐ O(n) 更⼩的时间复杂度算法的时候(99%)
3. 找到数组中的⼀个分割位置，使得左半部分满⾜某个条件，右半部分不满⾜(100%)
4. 找到⼀个最⼤/最⼩的值使得某个条件被满⾜(90%)

### 复杂度
- 时间复杂度：O(logn)
- 空间复杂度：O(1)

### 领扣例题
- LintCode 14. ⼆分查找(在排序的数据集上进⾏⼆分)
  - https://www.lintcode.com/problem/first-position-of-target/description
- LintCode 460. 在排序数组中找最接近的K个数 (在未排序的数据集上进⾏⼆分)
  - https://www.lintcode.com/problem/find-k-closest-elements/description
- LintCode 437. 书籍复印(在答案集上进⾏⼆分 )
  - https://www.lintcode.com/problem/copy-books/description

### 代码模版

Java

```java
int binarySearch(int[] nums, int target) {
  // corner case 处理
  if (nums == null || nums.length == 0) {
    return -1;
  }

int start = 0, end = nums.length - 1;

// 要点1: start + 1 < end
 while (start + 1 < end) {
 // 要点2：start + (end - start) / 2
 int mid = start + (end - start) / 2;
 // 要点3：=, <, > 分开讨论，mid 不 +1 也不 -1
 if (nums[mid] == target) {
 return mid;
 } else if (nums[mid] < target) {
 start = mid;
 } else {
 end = mid;
 }
 }

// 要点4: 循环结束后，单独处理start和end
   if (nums[start] == target) {
    return start;
   }
   if (nums[end] == target) {
    return end;
   }
    return -1;
}
```

Python

```python
def binary_search(self, nums, target):
	# corner case 处理
	# 这⾥等价于 nums is None or len(nums) == 0
	if not nums:
		return -1

start, end = 0, len(nums) - 1

# 用 start + 1 < end 而不是 start < end 的⽬的是为了避免死循环
	# 在 first position of target 的情况下不会出现死循环
	# 但是在 last position of target 的情况下会出现死循环
	# 样例：nums=[1，1] target = 1
	# 为了统一模板，我们就都采用 start + 1 < end，就保证不会出现死循环
	while start + 1 < end:
		# python 没有 overflow 的问题，直接 // 2 就可以了
		# java和C++ 最好写成 mid = start + (end - start) / 2
		# 防止在 start = 2^31 - 1, end = 2^31 - 1 的情况下出现加法 overflow
		mid = (start + end) // 2
		# > , =, < 的逻辑先分开写，然后在看看 = 的情况是否能合并到其他分支里
		if nums[mid] < target:
			start = mid
		elif nums[mid] == target:
			end = mid
		else:
			end = mid

# 因为上⾯的循环退出条件是 start + 1 < end
	# 因此这⾥循环结束的时候，start 和 end 的关系是相邻关系（1和2，3和4这种）
	# 因此需要再单独判断 start 和 end 这两个数谁是我们要的答案
	# 如果是找 first position of target 就先看 start，否则就先看 end
	if nums[start] == target:
		return start
	if nums[end] == target:
		return end
	return -1
```

👆 [BACK to Table of Contents -->](#目录-menu)

## 双指针 Two Pointers
### 使用条件

- 滑动窗⼝ (90%)
- 时间复杂度要求 O(n) (80%是双指针)
- 要求原地操作，只可以使⽤交换，不能使⽤额外空间 (80%)
- 有⼦数组 subarray /⼦字符串 substring 的关键词 (50%)
- 有回⽂ Palindrome 关键词(50%)

### 复杂度

- 时间复杂度：O(n)
  - 时间复杂度与最内层循环主体的执⾏次数有关
  - 与有多少重循环⽆关
- 空间复杂度：O(1)
  - 只需要分配两个指针的额外内存

### 领扣例题
- LintCode 1879. 两数之和VII(同向双指针)
  - https://www.lintcode.com/problem/two-sum-vii/description
- LintCode1712.和相同的⼆元⼦数组(相向双指针)
  - https://www.lintcode.com/problem/binary-subarrays-with-sum/description
- LintCode627. 最⻓回⽂串 (背向双指针)
  - https://www.lintcode.com/problem/longest-palindrome/description
- LintCode 64: 合并有序数组
  - https://www.lintcode.com/problem/merge-sorted-array

### 代码模版

Java
```java
// 相向双指针(patition in quicksort)
public void patition(int[] A, int start, int end) {
	if (start >= end) {
		return;
	}
	int left = start, right = end;
	// key point 1: pivot is the value, not the index
	int pivot = A[(start + end) / 2];
	// key point 2: every time you compare left & right, it should be
	// left <= right not left < right
	while (left <= right) {
		while (left <= right && A[left] < pivot) {
			left++;
		}
		while (left <= right && A[right] > pivot) {
			right--;
		}
		if (left <= right) {
			int temp = A[left];
			A[left] = A[right];
			A[right] = temp;
			left++;
			right--;
		}
	}
}

// 背向双指针
left = position;
right = position + 1;
while (left >= 0 && right < length) {
	if (可以停下来了) {
		break;
	}
	left--;
	right++;
}

// 同向双指针
int j = 0;
for (int i = 0; i < n; i++) {
	// 不满⾜则循环到满⾜搭配为⽌
	while (j < n && i 到 j之间不满足条件) {
		j += 1;
	}
	if (i 到 j之间满足条件) {
		处理i，j这次搭配
	}
}

// 合并双指针
ArrayList<Integer> merge(ArrayList<Integer> list1, ArrayList<Integer> list2) {
	// 需要 new 一个新的 list，而不是在 list1 或者 list2 上直接改动
	ArrayList<Integer> newList = new ArrayList<Integer>();

int i = 0, j = 0;
	while (i < list1.size() && j < list2.size()) {
		if (list1.get(i) < list2.get(j)) {
			newList.add(list1.get(i));
			i++;
		} else {
			newList.add(list2.get(j));
			j++;
		}
	}

// 合并上下的数到 newList 里
	// 无需用 if (i < list1.size())，直接 while 即可
	while (i < list1.size()) {
		newList.add(list1.get(i));
		i++;
	}
	while (j < list2.size()) {
		newList.add(list2.get(j);
		j++;
	}

return newList;
}
```

Python
```python
# 相向双指针(patition in quicksort)
def patition(self, A, start, end):
	if start >= end:
		return
	left, right = start, end
	# key point 1: pivot is the value, not the index
	pivot = A[(start + end) // 2];
	# key point 2: every time you compare left & right, it should be
	# left <= right not left < right
	while left <= right:
		while left <= right and A[left] < pivot:
			left += 1
		while left <= right and A[right] > pivot:
			right -= 1
		if left <= right:
			A[left], A[right] = A[right], A[left]
			left += 1
			right -= 1

# 背向双指针
	left = position
	right = position + 1
	while left >= 0 and right < len(s):
		if left 和 right 可以停下来了:
			break
		left -= 1
		right += 1

# 同向双指针
	j = 0
	for i in range(n):
	# 不满⾜则循环到满足搭配为止
	while j < n and i到j之间不满⾜条件:
		j += 1
	if i到j之间满⾜条件:
		处理i到j这段区间

# 合并双指针
	def merge(list1, list2):
	new_list = []
	i, j = 0, 0

# 合并的过程只能操作 i, j 的移动，不要去⽤ list1.pop(0) 之类的操作
	# 因为 pop(0) 是 O(n) 的时间复杂度
	while i < len(list1) and j < len(list2):
		if list1[i] < list2[j]:
			new_list.append(list1[i])
			i += 1
		else:
			new_list.append(list2[j])
			j += 1

# 合并剩下的数到 new_list 里
	# 不要⽤ new_list.extend(list1[i:]) 之类的方法
	# 因为 list1[i:] 会产生额外空间耗费
	while i < len(list1):
		new_list.append(list1[i])
		i += 1
	while j < len(list2):
		new_list.append(list2[j])
		j += 1

return new_list
```

👆 [BACK to Table of Contents -->](#目录-menu)

## 排序算法 Sorting
### 使用条件

### 复杂度

- 时间复杂度：
  - 快速排序(期望复杂度) ： O(nlogn)
  - 归并排序(最坏复杂度) ： O(nlogn)
- 空间复杂度：
  - 快速排序 ： O(1)
  - 归并排序 ： O(n)

### 领扣例题
- LintCode 463. 整数排序
  - https://www.lintcode.com/problem/sort-integers/description
- LintCode 464. 整数排序 II
  - https://www.lintcode.com/problem/sort-integers-ii/description

### 代码模板

Java
```java
// quick sort
public class Solution {
	/**
	* @param A an integer array
	* @return void
	*/
	public void sortIntegers(int[] A) {
		quickSort(A, 0, A.length - 1);
	}
	
	private void quickSort(int[] A, int start, int end) {
		if (start >= end) {
			return;
		}
		int left = start, right = end;
		// key point 1: pivot is the value, not the index
		int pivot = A[(start + end) / 2];
		// key point 2: every time you compare left & right, it should be
		// left <= right not left < right
		while (left <= right) {
			while (left <= right && A[left] < pivot) {
				left++;
			}
			while (left <= right && A[right] > pivot) {
				right--;
			}
			if (left <= right) {
				int temp = A[left];
				A[left] = A[right];
				A[right] = temp;
				left++;
				right--;
			}
		}
		quickSort(A, start, right);
		quickSort(A, left, end);
	}
}

// merge sort
public class Solution {
	public void sortIntegers(int[] A) {
		if (A == null || A.length == 0) {
			return;
		}
		int[] temp = new int[A.length];
		mergeSort(A, 0, A.length - 1, temp);
	}
	
	private void mergeSort(int[] A, int start, int end, int[] temp) {
		if (start >= end) {
			return;
		}
		// 处理左半区间
		mergeSort(A, start, (start + end) / 2, temp);
		// 处理右半区间
		mergeSort(A, (start + end) / 2 + 1, end, temp);
		// 合并排序数组
		merge(A, start, end, temp);
	}
	
	private void merge(int[] A, int start, int end, int[] temp) {
		int middle = (start + end) / 2;
		int leftIndex = start;
		int rightIndex = middle + 1;
		int index = start;
		while (leftIndex <= middle && rightIndex <= end) {
			if (A[leftIndex] < A[rightIndex]) {
				temp[index++] = A[leftIndex++];
			} else {
				temp[index++] = A[rightIndex++];
			}
		}
		while (leftIndex <= middle) {
			temp[index++] = A[leftIndex++];
		}
		while (rightIndex <= end) {
			temp[index++] = A[rightIndex++];
		}
		for (int i = start; i <= end; i++) {
			A[i] = temp[i];
		}
	}
}

```

Python

```python
# quick sort
class Solution:
	# @param {int[]} A an integer array
	# @return nothing
	def sortIntegers(self, A):
		# Write your code here
		self.quickSort(A, 0, len(A) - 1)
	
	def quickSort(self, A, start, end):
		if start >= end:
			return
		left, right = start, end
		# key point 1: pivot is the value, not the index
		pivot = A[(start + end) // 2];
		
		# key point 2: every time you compare left & right, it should be
		# left <= right not left < right
		while left <= right:
			while left <= right and A[left] < pivot:
				left += 1
			while left <= right and A[right] > pivot:
				right -= 1
			if left <= right:
				A[left], A[right] = A[right], A[left]
				
				left += 1
				right -= 1
		self.quickSort(A, start, right)
		self.quickSort(A, left, end)

# merge sort
class Solution:
	def sortIntegers(self, A):
		if not A:
			return A
		temp = [0] * len(A)
		self.merge_sort(A, 0, len(A) - 1, temp)
		
	def merge_sort(self, A, start, end, temp):
		if start >= end:
			return
	
		# 处理左半区间
		self.merge_sort(A, start, (start + end) // 2, temp)
		# 处理右半区间
		self.merge_sort(A, (start + end) // 2 + 1, end, temp)
		# 合并排序数组
		self.merge(A, start, end, temp)
		
	def merge(self, A, start, end, temp):
		middle = (start + end) // 2
		left_index = start
		right_index = middle + 1
		index = start
		
		while left_index <= middle and right_index <= end:
			if A[left_index] < A[right_index]:
				temp[index] = A[left_index]
				index += 1
				left_index += 1
			else:
				temp[index] = A[right_index]
				index += 1
				right_index += 1
		
		while left_index <= middle:
			temp[index] = A[left_index]
			index += 1
			left_index += 1
		while right_index <= end:
			temp[index] = A[right_index]
			index += 1
			right_index += 1
		
		for i in range(start, end + 1):
			A[i] = temp[i]
```

👆 [BACK to Table of Contents -->](#目录-menu)

## 二叉树分治 Binary Tree Divide & Conquer

### 使用条件

- ⼆叉树相关的问题 (99%)
- 可以⼀分为⼆去分别处理之后再合并结果 (100%)
- 数组相关的问题 (10%)

### 复杂度
- 时间复杂度$ O(n)$
- 空间复杂度$ O(n) $ (含递归调⽤的栈空间最⼤耗费)

### 领扣例题
- LintCode 1534. 将⼆叉搜索树转换为已排序的双向链接列表
  - https://www.lintcode.com/problem/convert-binary-search-tree-to-sorted-doubly-linked-list/description
- LintCode 94. ⼆叉树中的最⼤路径和
  - https://www.lintcode.com/problem/binary-tree-maximum-path-sum/description
- LintCode 95.验证⼆叉查找树
  - https://www.lintcode.com/problem/validate-binary-search-tree/description

### 代码模板
Java
```java
public ResultType divideConquer(TreeNode node) {
	// 递归出⼝
	// 一般处理 node == null 就够了
	// 一部分情况不需要处理 node == leaf
	if (node == null) {
		return ...;
	}
	
	// 处理左子树
	ResultType leftResult = divideConquer(node.left);
	// 处理右子树
	ResultType rightResult = divideConquer(node.right);
	//合并答案
	ResultType result = merge leftResult and rightResult
	return result;
}
```

Python

```python
def divide_conquer(root):
	# 递归出⼝
	# 一般处理 node == null 就够了
	# 一部分情况不需要处理 node == leaf
	if root is None:
		return ...
	# 处理左子树
	left_result = divide_conquer(node.left)
	# 处理右子树
	right_result = divide_conquer(node.right)
	# 合并答案
	result = merge left_result and right_result to get merged result
	return result
```

👆 [BACK to Table of Contents -->](#目录-menu)

## 二叉搜索树⾮递归 BST Iterator

### 使用条件

- ⽤⾮递归的⽅式（Non-recursion / Iteration）实现⼆叉树的中序遍历
- 常⽤于 BST 但不仅仅可以⽤于 BST

### 复杂度

- 时间复杂度 O(n)
- 空间复杂度 O(n)

### 领扣例题

- LintCode 67. ⼆叉树的中序遍历
  - https://www.lintcode.com/problem/binary-tree-inorder-traversal/description
- LintCode 902. ⼆叉搜索树的第 k ⼤元素
  - https://www.lintcode.com/problem/kth-smallest-element-in-a-bst/description

### 代码模板

Java

```java
List<TreeNode> inorderTraversal(TreeNode root) {
	List<TreeNode> inorder = new ArrayList<>();
	if (root == null) {
		return inorder;
	}
	
	// 创建一个 dummy node, 右指针指向 root
	// 放到 stack 里，此时栈顶 dummy 就是 iterator 的当前位置
	TreeNode dummy = new TreeNode(0);
	dummy.right = root;
	Stack<TreeNode> stack = new Stack<>();
	stack.push(dummy);

// 每次将 iterator 挪到下一个点
	// 就是调整 stack 使得栈顶是下一个点
	while (!stack.isEmpty()) {
		TreeNode node = stack.pop();
		if (node.right != null) {
			node = node.right;
			while (node != null) {
				stack.push(node);
				node = node.left;
			}
		}
		if (!stack.isEmpty()) {
			inorder.add(stack.peek());
		}
	}
	return inorder;
}
```

Python

```python
def inorder_traversal(root):
	if root is None:
		return []

# 创建⼀个 dummy node，右指针指向 root
	# 并放到 stack ⾥，此时 stack 的栈顶 dummy
	# 是 iterator 的当前位置
	dummy = TreeNode(0)
	dummy.right = root
	stack = [dummy]

inorder = []
	# 每次将 iterator 挪到下⼀个点
	# 也就是调整 stack 使得栈顶到下⼀个点
	while stack:
		node = stack.pop()
		if node.right:
			node = node.right
			while node:
				stack.append(node)
				node = node.left
		if stack:
			inorder.append(stack[-1])
	return inorder
```

👆 [BACK to Table of Contents -->](#目录-menu)

## 宽度优先搜索 BFS

### 使用条件

- 拓扑排序(100%)
- 出现连通块的关键词(100%)
- 分层遍历(100%)
- 简单图最短路径(100%)
- 给定⼀个变换规则，从初始状态变到终⽌状态最少⼏步(100%)

### 复杂度
- 时间复杂度：O(n + m)
  - n 是点数, m 是边数
- 空间复杂度：O(n)

### 领扣例题
- LintCode 974. 01 矩阵(分层遍历)
  - https://www.lintcode.com/problem/01-matrix/description
- LintCode 431. 找⽆向图的连通块
  - https://www.lintcode.com/problem/connected-component-in-undirected-graph/description
- LintCode 127. 拓扑排序
  - https://www.lintcode.com/problem/topological-sorting/description

### 代码模版

Java

```java
ReturnType bfs(Node startNode) {
	// BFS 必须要⽤队列 queue，别⽤栈 stack！
	Queue<Node> queue = new ArrayDeque<>();
	// hashmap 有两个作⽤，⼀个是记录⼀个点是否被丢进过队列了，避免重复访问
	// 另外⼀个是记录 startNode 到其他所有节点的最短距离
	// 如果只求连通性的话，可以换成 HashSet 就⾏
	// node 做 key 的时候⽐较的是内存地址
	Map<Node, Integer> distance = new HashMap<>();

// 把起点放进队列和哈希表⾥，如果有多个起点，都放进去
	queue.offer(startNode);
	distance.put(startNode, 0); // or 1 if necessary

// while 队列不空，不停的从队列⾥拿出⼀个点，拓展邻居节点放到队列中
	while (!queue.isEmpty()) {
		Node node = queue.poll();
		// 如果有明确的终点可以在这⾥加终点的判断
		if (node 是终点) {
			break or return something;
		}
		for (Node neighbor : node.getNeighbors()) {
			if (distance.containsKey(neighbor)) {
				continue;
			}
			queue.offer(neighbor);
			distance.put(neighbor, distance.get(node) + 1);
		}
	}
	// 如果需要返回所有点离起点的距离，就 return hashmap
	return distance;
	// 如果需要返回所有连通的节点, 就 return HashMap ⾥的所有点
	return distance.keySet();
	// 如果需要返回离终点的最短距离
	return distance.get(endNode);
}
```

Python

```python
def bfs(start_node):
	# BFS 必须要⽤队列 queue，别⽤栈 stack！
	# distance(dict) 有两个作⽤，⼀个是记录⼀个点是否被丢进过队列了，避免重复访问
	# 另外⼀个是记录 start_node 到其他所有节点的最短距离
	# 如果只求连通性的话，可以换成 set 就⾏
	# node 做 key 的时候⽐较的是内存地址
	queue = collections.deque([start_node])
	distance = {start_node: 0}

# while 队列不空，不停的从队列⾥拿出⼀个点，拓展邻居节点放到队列中
	while queue:
		node = queue.popleft()
		# 如果有明确的终点可以在这⾥加终点的判断
		if node 是终点:
		break or return something
		for neighbor in node.get_neighbors():
			if neighor in distnace:
				continue
			queue.append(neighbor)
			distance[neighbor] = distance[node] + 1

# 如果需要返回所有点离起点的距离，就 return hashmap
	return distance
	# 如果需要返回所有连通的节点, 就 return HashMap ⾥的所有点
	return distance.keys()
	# 如果需要返回离终点的最短距离
	return distance[end_node]
```

**Java 拓扑排序 BFS 模板**

```java
List<Node> topologicalSort(List<Node> nodes) {
	// 统计所有点的⼊度信息，放⼊ hashmap ⾥
	Map<Node, Integer> indegrees = getIndegrees(nodes);

// 将所有⼊度为 0 的点放到队列中
	Queue<Node> queue = new ArrayDeque<>();
	for (Node node : nodes) {
		if (indegrees.get(node) == 0) {
			queue.offer(node);
		}
	}

List<Node> topoOrder = new ArrayList<>();
	while (!queue.isEmpty()) {
		Node node = queue.poll();
		topoOrder.add(node);
		for (Node neighbor : node.getNeighbors()) {
			// 入度减一
			indegrees.put(neighbor, indegrees.get(neighbor) - 1);
			// 入度减到0说明不再依赖任何点，可以被放到队列（拓扑序）里了
			if (indegrees.get(neighbor) == 0) {
			queue.offer(neighbor);
			}
		}
	}

// 如果 queue 是空的时候，图中还有点没有被挖出来，说明存在环
	// 有环就没有拓扑序
	if (topoOrder.size() != nodes.size()) {
		return 没有拓扑序;
	}
	return topoOrder;
}

Map<Node, Integer> getIndegrees(List<Node> nodes) {
	Map<Node, Integer> counter = new HashMap<>();
	for (Node node : nodes) {
		counter.put(node, 0);
	}
	for (Node node : nodes) {
		for (Node neighbor : node.getNeighbors()) {
			counter.put(neighbor, counter.get(neighbor) + 1);
		}
	}
	return counter;
}
```

Python
```python
def get_indegrees(nodes):
	counter = {node: 0 for node in nodes}
	for node in nodes:
		for neighbor in node.get_neighbors():
			counter[neighbor] += 1
	return counter

def topological_sort(nodes):
	# 统计⼊度
	indegrees = get_indegrees(nodes)
	# 所有⼊度为 0 的点都放到队列⾥
	queue = collections.deque([
	node
	for node in nodes
	if indegrees[node] == 0
	])
	# ⽤ BFS 算法⼀个个把点从图⾥挖出来
	topo_order = []
	while queue:
		node = queue.popleft()
		topo_order.append(node)
		for neighbor in node.get_neighbors():
			indegrees[neighbor] -= 1
			if indegrees[neighbor] == 0:
				queue.append(neighbor)
	# 判断是否有循环依赖
	if len(topo_order) != len(nodes):
		return 有循环依赖(环),没有拓扑序
	return topo_order
```

👆 [BACK to Table of Contents -->](#目录-menu)

## 深度优先搜索 DFS

### 使用条件
- 找满⾜某个条件的所有⽅案 (99%)
- ⼆叉树 Binary Tree 的问题 (90%)
- 组合问题(95%)
  - 问题模型：求出所有满⾜条件的“组合”
  - 判断条件：组合中的元素是顺序⽆关的
- 排列问题 (95%)
  - 问题模型：求出所有满⾜条件的“排列”
  - 判断条件：组合中的元素是顺序“相关”的。

### 不要用 DFS 的场景

- 连通块问题（⼀定要⽤ BFS，否则 StackOverflow）
- 拓扑排序（⼀定要⽤ BFS，否则 StackOverflow）
- ⼀切 BFS 可以解决的问题

### 复杂度
- 时间复杂度：O(⽅案个数 * 构造每个⽅案的时间)
  - 树的遍历 ： O(n)
  - 排列问题 ： O(n! * n)
  - 组合问题 ： O(2^n * n)

### 领扣例题

- LintCode 67.⼆叉树的中序遍历(遍历树)
  - https://www.lintcode.com/problem/binary-tree-inorder-traversal/description
- LintCode 652.因式分解(枚举所有情况)
  - https://www.lintcode.com/problem/factorization/description

### 代码模版

Java

```java
public ReturnType dfs(参数列表) {
	if (递归出⼝) {
		记录答案;
		return;
	}
	for (所有的拆解可能性) {
		修改所有的参数
		dfs(参数列表);
		还原所有被修改过的参数
	}
	return something 如果需要的话，很多时候不需要 return 值除了分治的写法
}
```

Python

```python
def dfs(参数列表):
	if 递归出口:
		记录答案
		return
	for 所有的拆解可能性:
	修改所有的参数
	dfs(参数列表)
	还原所有被修改过的参数
	return something 如果需要的话，很多时候不需要 return 值除了分治的写法
```

👆 [BACK to Table of Contents -->](#目录-menu)

## 动态规划 Dynamic Programming
### 使用条件
- 使用场景：
  - 求⽅案总数(90%)
  - 求最值(80%)
  - 求可⾏性(80%)
- 不适⽤的场景：
  - 找所有具体的⽅案（准确率99%）
  - 输⼊数据⽆序(除了背包问题外，准确率60%~70%)
  - 暴⼒算法已经是多项式时间复杂度（准确率80%）
- 动态规划四要素(对⽐递归的四要素)：
  - 状态 (State) -- 递归的定义
  - ⽅程 (Function) -- 递归的拆解
  - 初始化 (Initialization) -- 递归的出⼝
  - 答案 (Answer) -- 递归的调⽤

### ⼏种常⻅的动态规划：
- **背包型**
- 给出 n 个物品及其⼤⼩,问是否能挑选出⼀些物品装满⼤⼩为m的背包
- 题⽬中通常有“和”与“差”的概念，数值会被放到状态中
- 通常是⼆维的状态数组，前 i 个组成和为 j 状态数组的⼤⼩需要开 (n + 1) * (m + 1)
- ⼏种背包类型：
- **背包型**
 - 01背包
 - **状态 state**
 dp[i][j] 表⽰前 i 个数⾥挑若⼲个数是否能组成和为 j
 - **⽅程 function**
 dp[i][j] = dp[i - 1][j] or dp[i - 1][j - A[i - 1]] 如果 j >= A[i - 1]
 dp[i][j] = dp[i - 1][j] 如果 j < A[i - 1]
 第 i 个数的下标是 i - 1，所以⽤的是 A[i - 1] ⽽不是 A[i]
 - **初始化 initialization**
 dp[0][0] = true
 dp[0][1...m] = false
 - **答案 answer**
 使得 dp[n][v], 0 s <= v <= m 为 true 的最⼤ v
 - 多重背包
 - 状态 state
 dp[i][j] 表⽰前i个物品挑出⼀些放到 j 的背包⾥的最⼤价值和
 - ⽅程 function
 dp[i][j] = max(dp[i - 1][j - count * A[i - 1]] + count * V[i- 1])
 其中 0 <= count <= j / A[i - 1]
 - 初始化 initialization
 dp[0][0..m] = 0
 - 答案 answer
 dp[n][m]

- **区间型**
- 题⽬中有 subarray / substring 的信息
  - ⼤区间依赖⼩区间
  - ⽤ dp[i][j] 表⽰数组/字符串中 i, j 这⼀段区间的最优值/可⾏性/⽅案总数
  - **状态 state**
   dp[i][j] 表⽰数组/字符串中 i,j 这⼀段区间的最优值/可⾏性/⽅案总数
  - ⽅程 function
  dp[i][j] = max/min/sum/or(dp[i,j 之内更⼩的若⼲区间])
- **匹配型**
  - 通常给出两个字符串
  - 两个字符串的匹配值依赖于两个字符串前缀的匹配值
  - 字符串⻓度为 n,m 则需要开 (n + 1) x (m + 1) 的状态数组
  - 要初始化 dp[i][0] 与 dp[0][i]
  - 通常都可以⽤滚动数组进⾏空间优化
  - 状态 state
  dp[i][j] 表⽰第⼀个字符串的前 i 个字符与第⼆个字符串的前 j 个字符怎么样怎么样
(max/min/sum/or)

- **划分型**
  - 是前缀型动态规划的⼀种, 有前缀的思想
  - 如果指定了要划分为⼏个部分：
    - dp[i][j] 表⽰前i个数/字符划分为j个 部分的最优值/⽅案数/可⾏性
  - 如果没有指定划分为⼏个部分:
    - dp[i] 表⽰前i个数/字符划分为若⼲个 部分的最优值/⽅案数/可⾏性
  - 状态 state
    - 指定了要划分为⼏个部分: dp[i][j] 表⽰前i个数/字符划分为j个部分的最优值/⽅案数/可⾏性
    - 没有指定划分为⼏个部分: dp[i] 表⽰前i个数/字符划分为若⼲个部分的最优值/⽅案数/可⾏性

- **接⻰型**
  - 通常会给⼀个接⻰规则，问你最⻓的⻰有多⻓
  - 状态表⽰通常为: dp[i] 表⽰以坐标为 i 的元素结尾的最⻓⻰的⻓度
  - ⽅程通常是: dp[i] = max{dp[j] + 1}, j 的后⾯可以接上 i
  - LIS 的⼆分做法选择性的掌握，但并不是所有的接⻰型DP都可以⽤⼆分来优化
  - 状态 state
    - 状态表⽰通常为: dp[i] 表⽰以坐标为 i 的元素结尾的最⻓⻰的⻓度
  - ⽅程 function
    - dp[i] = max{dp[j] + 1}, j 的后⾯可以接上 i

### 复杂度
- 时间复杂度:
  - O(状态总数 * 每个状态的处理耗费)
  - 等于O(状态总数 * 决策数)
- 空间复杂度：
  - O(状态总数) (不使⽤滚动数组优化)
  - O(状态总数 / n)(使⽤滚动数组优化, n是被滚动掉的那⼀个维度)

### 领扣例题

- LintCode563.背包问题V(背包型):
  - https://www.lintcode.com/problem/backpack-v/description
- LintCode76.最⻓上升⼦序列(接⻰型):
  - https://www.lintcode.com/problem/longest-increasing-subsequence/description
- LintCode 476.⽯⼦归并V(区间型):
  - https://www.lintcode.com/problem/stone-game/description
- LintCode 192. 通配符匹配 (匹配型):
  - https://www.lintcode.com/problem/wildcard-matching/description
- LintCode107.单词拆分(划分型):
  - https://www.lintcode.com/problem/word-break/description

👆 [BACK to Table of Contents -->](#目录-menu)

## 堆 Heap

### 使用条件

- 找最⼤值或者最⼩值(60%)
- 找第 k ⼤(pop k 次 复杂度O(nlogk))(50%)
- 要求 logn 时间对数据进⾏操作(40%)

### 堆不能解决的问题
- 查询⽐某个数⼤的最⼩值/最接近的值（平衡排序⼆叉树 Balanced BST 才可以解决）
- 找某段区间的最⼤值最⼩值（线段树 SegmentTree 可以解决）
- O(n)找第k⼤ (使⽤快排中的partition操作)

### 领扣例题

- LintCode 1274. 查找和最⼩的K对数字
  - https://www.lintcode.com/problem/find-k-pairs-with-smallest-sums/description
- LintCode 919. 会议室 II
  - https://www.lintcode.com/problem/meeting-rooms-ii/description
- LintCode 1512.雇佣K个⼈的最低费⽤
  - https://www.lintcode.com/problem/minimum-cost-to-hire-k-workers/description

### 代码模板

Java 带删除特定元素功能的堆

```java
class ValueIndexPair {
	int val, index;
	public ValueIndexPair(int val, int index) {
		this.val = val;
		this.index = index;
	}
}

class Heap {
	private Queue<ValueIndexPair> minheap;
	private Set<Integer> deleteSet;
	public Heap() {
		minheap = new PriorityQueue<>((p1, p2) -> (p1.val - p2.val));
		deleteSet = new HashSet<>();
	}

public void push(int index, int val) {
		minheap.add(new ValueIndexPair(val, index));
	}

private void lazyDeletion() {
		while (minheap.size() != 0 && deleteSet.contains(minheap.peek().index)) {
			ValueIndexPair pair = minheap.poll();
			deleteSet.remove(pair.index);
		}
	}

public ValueIndexPair top() {
		lazyDeletion();
		return minheap.peek();
	}

public void pop() {
		lazyDeletion();
		minheap.poll();
	}

public void delete(int index) {
		deleteSet.add(index);
	}

public boolean isEmpty() {
		return minheap.size() == 0;
	}
}
```

Python
```python
from heapq import heappush, heappop

class Heap:
	def __init__(self):
		self.minheap = []
		self.deleted_set = set()

def push(self, index, val):
		heappush(self.minheap, (val, index))

def _lazy_deletion(self):
		while self.minheap and self.minheap[0][1] in self.deleted_set:
		heappop(self.minheap)

def top(self):
		self._lazy_deletion()
		return self.minheap[0]

def pop(self):
		self._lazy_deletion()
		heappop(self.minheap)

def delete(self, index):
		self.deleted_set.add(index)

def is_empty(self):
		return not bool(self.minheap)
```

👆 [BACK to Table of Contents -->](#目录-menu)

## 并查集 Union Find

### 使用条件

- 需要查询图的连通状况的问题
- 需要⽀持快速合并两个集合的问题

### 复杂度
- 时间复杂度 union O(1), find O(1)
- 空间复杂度 O(n)

### 领扣例题

- LintCode 1014. 打砖块
  - https://www.lintcode.com/problem/bricks-falling-when-hit/
- LintCode 1813. 构造⼆叉树
  - https://www.lintcode.com/problem/construct-binary-tree/

### 代码模板

Java

```java
class UnionFind {
	private Map<Integer, Integer> father;
	private Map<Integer, Integer> sizeOfSet;
	private int numOfSet = 0;
	public UnionFind() {
		// 初始化⽗指针，集合⼤⼩，集合数量
		father = new HashMap<Integer, Integer>();
		sizeOfSet = new HashMap<Integer, Integer>();
		numOfSet = 0;
	}

public void add(int x) {
		// 点如果已经出现，操作⽆效
		if (father.containsKey(x)) {
			return;
		}
		// 初始化点的⽗亲为 空对象null
		// 初始化该点所在集合⼤⼩为 1
		// 集合数量增加 1
		father.put(x, null);
		sizeOfSet.put(x, 1);
		numOfSet++;
	}

public void merge(int x, int y) {
		// 找到两个节点的根
		int rootX = find(x);
		int rootY = find(y);
		// 如果根不是同⼀个则连接
		if (rootX != rootY) {
			// 将一个点的根变成新的根
			// 集合数量减少 1
			// 计算新的根所在集合⼤⼩
			father.put(rootX, rootY);
			numOfSet--;
			sizeOfSet.put(rootY, sizeOfSet.get(rootX) + sizeOfSet.get(rootY));
		}
}

public int find(int x) {
		// 指针 root 指向被查找的点 x
		// 不断找到 root 的父亲
		// 直到 root 指向 x 的根节点
		int root = x;
		while (father.get(root) != null) {
		root = father.get(root);
		}
		// 将路径上所有点指向根节点 root
		while (x != root) {
			// 暂存 x 原本的⽗亲
			// 将 x 指向根节点
			// x 指针上移至 x 的父节点
			int originalFather = father.get(x);
			father.put(x, root);
			x = originalFather;
		}
		return root;
	}

public boolean isConnected(int x, int y) {
		// 两个节点连通 等价于 两个节点的根相同
		return find(x) == find(y);
	}

public int getNumOfSet() {
		// 获得集合数量
		return numOfSet;
	}

public int getSizeOfSet(int x) {
		// 获得某个点所在集合⼤⼩
		return sizeOfSet.get(find(x));
	}
}

```

Python

```python
class UnionFind:
def __init__(self):
	# 初始化⽗指针，集合⼤⼩，集合数量
	self.father = {}
	self.size_of_set = {}
	self.num_of_set = 0

def add(self, x):
	# 点如果已经出现，操作⽆效
	if x in self.father:
		return
	# 初始化点的⽗亲为 空对象None
	# 初始化该点所在集合⼤⼩为 1
	# 集合数量增加 1
	self.father[x] = None
	self.num_of_set += 1
	self.size_of_set[x] = 1

def merge(self, x, y):
	# 找到两个节点的根
	root_x, root_y = self.find(x), self.find(y)
	# 如果根不是同⼀个则连接
	if root_x != root_y:
		# 将⼀个点的根变成新的根
		# 集合数量减少 1
		# 计算新的根所在集合⼤⼩
		self.father[root_x] = root_y
		self.num_of_set -= 1
		self.size_of_set[root_y] += self.size_of_set[root_x]

def find(self, x):
	# 指针 root 指向被查找的点 x
	# 不断找到 root 的⽗亲
	# 直到 root 指向 x 的根节点
	root = x
	while self.father[root] != None:
		root = self.father[root]
	# 将路径上所有点指向根节点 root
	while x != root:
		# 暂存 x 原本的⽗亲
		# 将 x 指向根节点
		# x 指针上移⾄ x 的⽗节点
		original_father = self.father[x]
		self.father[x] = root
		x = original_father
	return root

def is_connected(self, x, y):
	# 两个节点连通 等价于 两个节点的根相同
	return self.find(x) == self.find(y)

def get_num_of_set(self):
	# 获得集合数量
	return self.num_of_set

def get_size_of_set(self, x):
	# 获得某个点所在集合⼤⼩
	return self.size_of_set[self.find(x)]
```

👆 [BACK to Table of Contents -->](#目录-menu)

## 字典树 Trie
### 使用条件
- 需要查询包含某个前缀的单词/字符串是否存在
- 字符矩阵中找单词的问题

### 复杂度
- 时间复杂度 O(L) 增删查改
- 空间复杂度 O(N * L) N 是单词数，L是单词⻓度

### 领扣例题
- LintCode 1221. 连接词
  - https://www.lintcode.com/problem/concatenated-words/
- LintCode 1624. 最⼤距离
  - https://www.lintcode.com/problem/max-distance/
- LintCode 1090. 映射配对之和
  - https://www.lintcode.com/problem/map-sum-pairs/

### 代码模板

Java

```java 
class TrieNode {
	// 儿子节点
	public Map<Character, TrieNode> children;
	// 根节点到该节点是否是一个单词
	public boolean isWord;
	// 根节点到该节点的单词是什么
	public String word;
	public TrieNode() {
		sons = new HashMap<Character, TrieNode>();
		isWord = false;
		word = null;
	}
}

public class Trie {
	private TrieNode root;
		public Trie() {
		root = new TrieNode();
	}

public TrieNode getRoot() {
		return root;
	}

// 插入单词
	public void insert(String word) {
		TrieNode node = root;
		for (int i = 0; i < word.length(); i++) {
			char letter = word.charAt(i);
			if (!node.sons.containsKey(letter)) {
				node.sons.put(letter, new TrieNode());
			}
			node = node.sons.get(letter);
		}
		node.isWord = true;
		node.word = word;
	}

// 判断单词 word 是不是在字典树中
	public boolean hasWord(String word) {
		int L = word.length();
		TrieNode node = root;
		for (int i = 0; i < L; i++) {
			char letter = word.charAt(i);
			if (!node.sons.containsKey(letter)) {
				return false;
			}
			node = node.sons.get(letter);
		}
		return node.isWord;
	}

// 判断前缀 prefix 是不是在字典树中
	public boolean hasPrefix(String prefix) {
		int L = prefix.length();
		TrieNode node = root;
		for (int i = 0; i < L; i++) {
			char letter = prefix.charAt(i);
			if (!node.sons.containsKey(letter)) {
				return false;
			}
			node = node.sons.get(letter);
		}
		return true;
	}
}
```

👆 [BACK to Table of Contents -->](#目录-menu)

<img align="center" src="FLAG.jpg"> 
 Feel free to ask any questions, open a PR if you feel something can be done differently!
<h2 align="center">🌟Star this repository🌟</h2>
Created by <a href="https://github.com/Charmve">Charmve</a> & <a href="https://github.com/MaiweiAI">maiwei.ai</a> Community | All Rights Received by <a href="https://github.com/MaiweiAI">maiwei.ai</a>

Repetition/LeetCode4FLAG

简介

发行版

贡献者

近期动态

Repetition/LeetCode4FLAG .gitee-modal { width: 500px !important; }

简介

发行版

贡献者

近期动态

搜索帮助

Repetition/LeetCode4FLAG