一、介绍
1、常见的数据结构
「队列」、「栈」这两种数据结构既可以使⽤链表也可以使⽤数组实现。⽤数组实现，就要处理扩容缩容的问题；⽤链表实现，没有这个问题，但需要更多的内存空间存储节点指针。
「图」的两种表⽰⽅法，邻接表就是链表，邻接矩阵就是⼆维数组。邻接矩阵判断连通性迅速，并可以进⾏矩阵运算解决⼀些问题，但是如果图⽐较稀疏的话很耗费空间。邻接表⽐较节省空间，但是很多操作的效率上肯定⽐不过邻接矩阵。
「散列表」就是通过散列函数把键映射到⼀个⼤数组⾥。⽽且对于解决散列冲突的⽅法，拉链法需要链表特性，操作简单，但需要额外的空间存储指针；线性探查法就需要数组特性，以便连续寻址，不需要指针的存储空间，但操作稍微复杂些。
「树」，⽤数组实现就是「堆」，因为「堆」是⼀个完全⼆叉树，⽤数组存储不需要节点指针，操作也⽐较简单；⽤链表实现就是很常⻅的那种「树」，因为不⼀定是完全⼆叉树，所以不适合⽤数组存储。为此，在这种链表「树」结构之上，⼜衍⽣出各种巧妙的设计，⽐如⼆叉搜索树、AVL树、红⿊树、区间树、B 树等等，以应对不同的问题。
2、常见的算法框架
数组遍历框架，典型的线性迭代结构：
1
2
3
4
5
| void traverse(int[] arr) {
for (int i = 0; i < arr.length; i++) {
}
}
|
链表遍历框架，兼具迭代和递归结构：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class ListNode {
int val;
ListNode next;
}
void traverse(ListNode head) {
for (ListNode p = head; p != null; p = p.next) {
}
}
void traverse(ListNode head) {
traverse(head.next)
}
|
⼆叉树遍历框架，典型的⾮线性递归遍历结构：
1
2
3
4
5
6
7
8
9
10
|
class TreeNode {
int val;
TreeNode left, right;
}
void traverse(TreeNode root) {
traverse(root.left)
traverse(root.right)
}
|
二、动态规划
1、斐波那契数列的算法优化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
private static int fib3(int N) {
if (N < 0) return 0;
int[] meno = new int[N + 1];
return helper(meno, N);
}
private static int helper(int[] meno, int n) {
if (n == 1 || n == 2) return 1;
if (meno[n] != 0) return meno[n];
meno[n] = helper(meno, n - 1) + helper(meno, n - 2);
return meno[n];
}
private static int fib(int N) {
int[] dp = new int[N + 1];
dp[1] = dp[2] = 1;
for (int i = 3; i <= N; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[N];
}
private static int fib2(int n) {
if (n == 1 || n == 2) {
return 1;
}
int prev = 1, curr = 1;
for (int i = 3; i <= n; i++) {
int sum = prev + curr;
prev = curr;
curr = sum;
}
return curr;
}
|
三、回溯算法
纯暴力穷举算法，复杂度很高
回溯算法的框架：
1
2
3
4
5
6
7
8
9
| result = []
def backtrack(路径, 选择列表):
if 满⾜结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择
|
1、全排列算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
public class QuanPaiLie {
private static List<List<Integer>> res = new LinkedList<>();
public static void main(String[] args) {
int[] nums = {1, 2, 3};
List<List<Integer>> res = permute(nums);
System.out.println(res.toString());
}
private static List<List<Integer>> permute(int[] nums) {
LinkedList<Integer> track = new LinkedList<>();
backtrack(nums, track);
return res;
}
private static void backtrack(int[] nums, LinkedList<Integer> track) {
if (track.size() == nums.length) {
res.add(new LinkedList(track));
return;
}
for (int i = 0; i < nums.length; i++) {
if (track.contains(nums[i]))
continue;
track.add(nums[i]);
backtrack(nums, track);
track.removeLast();
}
}
}
|
四、BFS算法
图的搜索算法分为BDF（广度优先搜索）和（深度优先搜索）
BFS框架
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
int BFS(Node start, Node target) {
Queue<Node> q;
Set<Node> visited;
q.offer(start);
visited.add(start);
int step = 0;
while (q not empty) {
int sz = q.size();
for (int i = 0; i < sz; i++) {
Node cur = q.poll();
if (cur is target)
return step;
for (Node x : cur.adj())
if (x not in visited) {
q.offer(x);
visited.add(x);
}
}
step++;
}
}
|
题目地址：https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() { }
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
public int minDepth(TreeNode root) {
if (root == null) return 0;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
int depth = 1;
while (!q.isEmpty()) {
int sz = q.size();
for (int i = 0; i < sz; i++) {
TreeNode cur = q.poll();
if (cur.left == null && cur.right == null) return depth;
if (cur.left != null) q.offer(cur.left);
if (cur.right != null) q.offer(cur.right);
}
depth++;
}
return depth;
}
|
DFS的时间复杂度比BFS高，但是DFS的空间复杂度比BFS低。
DFS在最坏的情况下空间复杂度为O(logN)，而BFS最坏情况下的空间复杂度为O(N)。
五、二分搜索
零、⼆分查找框架
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| int binarySearch(int[] nums, int target) {
int left = 0, right = ...;
while (...){
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
...
} else if (nums[mid] < target) {
left = ...
} else if (nums[mid] > target) {
right = ...
}
}
return ...;
}
|
二分查找
题目地址： https://leetcode-cn.com/problems/binary-search/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public static int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
else if (nums[mid] < target) left = mid + 1;
else if (nums[mid] > target) right = mid - 1;
}
return -1;
}
|
