thetheOrange的笔记

发表于 更新于 分类于 本文字数： 4.1k 阅读时长 ≈ 7 分钟

二叉搜索树/二叉排序树定义

满足以下特征的二叉树，即为二叉搜索树：

  1. 若左子树非空，则左子树上的所有节点要小于根节点
  2. 若右子树非空，则右子树上的所有节点要大于根节点
  3. 所有子结构满足上面两个条件

平衡二叉树的定义

平衡二叉树，满足以下特征：

  1. 左右子树的高度差不超过1
  2. 所有子结构满足条件1

使用平衡二叉树优化二叉搜索树

二叉搜索树在理想情况下查找效率是O(logn)的，但是在最坏情况下是O(n)的，比如下面这种情况:

二叉搜索树

但如果将这个二叉搜索树变为平衡二叉树，效率会得到大大提高，如下图：

优化后的二叉搜索树

左旋和右旋

左旋和右旋是调整二叉树为平衡二叉树的两大“武器”

左旋

  • 适用范围

当最小失衡二叉树出现以下情况时，可以使用左旋进行调整

可以左旋的情况

基本的步骤是：

  1. 将old_root的右孩子new_root作为新的根节点
  2. 如果new_root有左孩子，则将这个左孩子当做old_root的右孩子
  3. 将new_root的做左孩子设为old_root
  • 模版代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

// 左旋
Node* leftRotate(Node* root) {
	Node* newRoot = root->right;
	Node* tmp = newRoot->left;

	root->right = tmp;
	newRoot->left = root;

	// 更新高度
	root->height = 1 + max(getHeight(root->left), getHeight(root->right));
	newRoot->height = 1 + max(getHeight(root), getHeight(newRoot->right));
	return newRoot;
}

右旋

  • 适用范围

当最小失衡二叉树出现以下情况时，可以使用右旋进行调整

可以右旋的情况

基本的步骤是：

  1. 将old_root的左孩子new_root作为新的根节点
  2. 如果new_root有右孩子，则将这个右孩子当做old_root的左孩子
  3. 将new_root的右孩子设为old_root
  • 模版代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

// 右旋
Node* rightRotate(Node* root) {
	Node* newRoot = root->left;
	Node* tmp = newRoot->right;

	root->left = tmp;
	newRoot->right = root;

	// 更新高度
	root->height = 1 + max(getHeight(root->left), getHeight(root->right));
	newRoot->height = 1 + max(getHeight(newRoot->left), getHeight(root));
	return newRoot;
}

四种类型

LL

LL类型情况如下：

LL类型

判断条件：

  1. old_root的平衡因子大于1
  2. new_root的平衡因子大于0

只需对old_root进行右旋即可

1
2
3

if (getBalance(root) > 1 && getBalance(root->left) > 0) return leftRotate(root);

LR

LR类型情况如下:

LR类型

判断条件：

  1. old_root的平衡因子大于1
  2. new_root的平衡因子小于0

操作步骤：

  1. 先对new_root进行左旋
  2. 再对old_root进行右旋
1
2
3
4
if (getBalance(root) > 1 && getBalance(root->left) < 0) {
	root->left = leftRotate(root->right);
	return rightRotate(root);
}

RR

RR类型情况如下：

RR类型

判断条件：

  1. old_root的平衡因子小于-1
  2. new_root的平衡因子小于0

只需对old_root进行左旋即可

1
2
3

if (getBalance(root) < -1 && getBalance(root->right) < 0) return rightRotate(root);

RL

RL类型情况如下：

RL类型

判断条件：

  1. old_root的平衡因子小于-1
  2. new_root的平衡因子大于0

操作步骤：

  1. 先对new_root进行右旋
  2. 再对old_root进行左旋
1
2
3
4
5
6

if (getBalance(root) < -1 && getBalance(root->left) > 0) {
	root->right = rightRotate(root->right);
	return leftRotate(root);
}

插入操作

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

// 插入节点
Node* insert(Node* root, int val) {
	if (!root) return new Node(val);
	if (val > root->val) {
		root->right = insert(root->right, val);
	}
	else if (val < root->val) {
		root->left = insert(root->left, val);
	}
	else {
		return root;
	}

	// 更新高度
	root->height = 1 + max(getHeight(root->left), getHeight(root->right));

	// 平衡性调整
	if (getBalance(root) < -1) {
		// RL
		if (getBalance(root->right) > 0) {
			root->right = rightRotate(root->right);
			return leftRotate(root);
		}
		// RR
		else {
			return leftRotate(root);
		}
	}
	else if (getBalance(root) > 1) {
		// LR
		if (getBalance(root->left) < 0) {
			root->left = leftRotate(root->left);
			return rightRotate(root);
		}
		// LL
		else {
			return rightRotate(root);
		}
	}
	return root;
}

删除操作

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

// 删除节点
Node* delete_node(Node* root, int val) {
	if (!root) return root;
	if (root->val == val) {
		if (!root->left && !root->right) {
			return nullptr;
		}
		else if (root->left && !root->right) {
			return root->left;
		}
		else if (!root->left && root->right) {
			return root->right;
		}
		else {
			Node* tmp = root->right;
			while (tmp->left) tmp = tmp->left;
			tmp->left = root->left;
			return root->right;
		}
	}
	if (val > root->val) root->right = delete_node(root->right, val);
	if (val < root->val) root->left = delete_node(root->left, val);

	if (!root) return nullptr;

	// 更新树高
	root->height = 1 + max(getHeight(root->left), getHeight(root->right));

	// 调整二叉树
	// LL
	if (getBalance(root) > 1 && getBalance(root->left) >= 0) {
		return rightRotate(root);
	}
	// LR
	if (getBalance(root) > 1 && getBalance(root->left) < 0) {
		root->left = leftRotate(root->left);
		return rightRotate(root);
	}
	// RR
	if (getBalance(root) < -1 && getBalance(root->right) <= 0) {
		return leftRotate(root);
	}
	// RL
	if (getBalance(root) < -1 && getBalance(root->right) > 0) {
		root->right = rightRotate(root->right);
		return leftRotate(root);
	}
	return root;
}


发表于 更新于 分类于 本文字数： 1k 阅读时长 ≈ 2 分钟

Floyd算法

借助邻接矩阵辅助，Floyd算法可以解决数据量不大，且权值中有负数的图，但不能是存在负环的图的最短路径问题。该算法步骤如下：

  1. 在n个节点中寻找”跳点”bridge
  2. 如果graph[from][bridge] != INT_MAX && graph[bridge][to] != INT_MAX && graph[from][bridge] + graph[bridge][to] < graph[from][to] 则更新邻接矩阵
1
2
3
4
5
6
7
8
9
10
for (int bridge = 0; bridge < n; ++bridge) {
    for (int from = 0; from < n; ++from)
        for (int to = 0; to < n; ++to) {
            if (graph[from][bridge] != INT_MAX &&
                graph[bridge][to] != INT_MAX &&
                graph[from][bridge] + graph[bridge][to] < graph[from][to]) {
                    graph[from][to] = graph[from][bridge] + graph[bridge][to];
                }
    }
}

显而易见，floyd算法的时间复杂度是O(n^3) 空间复杂度是O(n^2)

Bellman-Ford算法

Bellman-Ford 可以解决权值中存在负数，但不能存在负环的图，找出任意两点的最短路径问题。该算法步骤如下：

  1. 初始化distance数组 即vector<int>distance(n, INT_MAX);
  2. 对所有边进行n-1的“松弛”（取最小值）操作

算法模版如下：

1
2
3
4
5
6
7
8
9
10
vector<int> distance(n, INT_MAX);
distance[0] = 0; // 源点设为0

for (int i = 0; i < n; ++i)
    for (auto edge : edges) {
        int from = edge[0], to = edge[1], weight = edge[2];
        if (distance[from] != INT_MAX) {
            distance[to] = min(distance[to], distance[from] + weight);
        }
    }

Bellman-Ford算法的时间复杂度为 O(n^2) 空间复杂度为O(n)

发表于 更新于 分类于 本文字数： 2.9k 阅读时长 ≈ 5 分钟

Kruskal算法模版

  1. 按各边权值进行从小到大排序
  2. 检测是否有环（使用并查集）
    1. 如果两节点属于同一个集合 则说明有环
    2. 如果两节点不属于同一个集合 不成环则进行合并

借助洛谷上的最小生成树

如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz。
输入格式

第一行包含两个整数 N,MN,M，表示该图共有 NN 个结点和 MM 条无向边。

接下来 MM 行每行包含三个整数 Xi,Yi,ZiXi​,Yi​,Zi​，表示有一条长度为 ZiZi​ 的无向边连接结点 Xi,YiXi​,Yi​。
输出格式

如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。

模版代码如下：

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
55
56
57
58

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

vector<int> father;
int ans = 0;
int cnt = 0;

// 构建并查集
void build(int n) {
	for (int i = 0; i <= n; ++i) father.push_back(i);
}
// 查询并查集
int find(int x) {
	if (x != father[x]) father[x] = find(father[x]);
	return father[x];
}
// 合并
void _union(int x, int y, int w) {
	int fx = find(x), fy = find(y);
	if (fx != fy) {
		father[fy] = fx;
		ans += w;
	}
}

int main() {
	int N, M;
	cin >> N >> M;
	vector<vector<int>> edge;
	for (int i = 0; i < M; ++i) {
		int from, to, weight;
		cin >> from >> to >> weight;
		edge.push_back({ from, to, weight });
	}
	auto cmp = [](vector<int>& a, vector<int>& b) -> bool{
		return a[2] < b[2];
		};
	// 根据权值排序
	sort(edge.begin(), edge.end(), cmp);
	build(N);
	for (auto e : edge) {
		int from = e[0], to = e[1], w = e[2];
		// 如果不成环 则合并
		if (find(from) != find(to)) {
			_union(from, to, w);
			cnt++;
		}
		// 如果成环 则跳过
	}
	if (cnt == N-1) cout << ans;
	else cout << "orz";
	return 0;
}

Prim算法模版

prim算法和Dijkstra算法十分类似

过程如下：

  1. 创建visited数组 初始设为false 即vector<bool>visited(n, false);
  2. 任取一个点 将这个点的所有边加入到小根堆中
  3. 当小根堆不为空 则弹出元素
    1. 弹出元素若已访问过 则continue
    2. 弹出元素若未访问过 则visited[cur] = true; 这里可以计算最小生成树的权值 如ans += weight
    3. 处理各边 将各边加入到堆中
  4. 当小根堆为空 也就得到了最小生成树

针对洛谷上的模版题（见前文）也可以使用prim算法进行计算

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
55
56
57
58
59
#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
#include <limits.h>
#include <queue>

using namespace std;

int main() {
    // 建图
    int N, M;
    cin >> N >> M;
    vector<vector<vector<int>>> graph(N + 1);
    for (int i = 0; i < M; ++i) {
        int from, to, weight;
        cin >> from >> to >> weight;
        graph[from].push_back({ to, weight });
        graph[to].push_back({ from, weight });
    }

    // 开始 Prim 算法
    vector<bool> visited(N + 1, false);
    int ans = 0, cnt = 1;

    auto cmp = [](vector<int>& a, vector<int>& b)-> bool {
        return a[1] > b[1]; // 使用小根堆
        };
    priority_queue<vector<int>, vector<vector<int>>, decltype(cmp)> q(cmp);
    for (auto i : graph[1]) q.push(i);
    visited[1] = true;

    while (!q.empty()) {
        vector<int> cur = q.top();
        q.pop();
        int from = cur[0], weight = cur[1];

        if (visited[from]) continue;
        visited[from] = true;
        ans += weight; // 累加当前边的权重
        cnt++;

        // 处理各边
        for (auto neighbor : graph[from]) {
            q.push(neighbor);
        }
    }

    // 检查是否所有节点都被访问
    if (cnt == N) {
        cout << ans;
    }
    else {
        cout << "orz";
    }

    return 0;
}

时空复杂度分析

kruskal算法：

  • 时间复杂度 O(E * log E)
  • 空间复杂度 O(V)

prim算法

  • 时间复杂度 O(E * log V)
  • 空间复杂度 O(V)

发表于 更新于 分类于 本文字数： 1.9k 阅读时长 ≈ 3 分钟

1. 结构实现

并查集要实现三个方法：

  1. int find(int x); 查找代表元素
  2. bool isSameSet(int x, int y); 查看是否为同一集合
  3. void _union(int x, int y); 合并集合

而并查集的结构，我们可以使用数组（顺序表）进行存储。数组下标i表示每个节点，数组的值father[i]对应着这个节点的代表节点。

对于father数组的初始化，我们有如下代码：

1
2
// 这里的n是节点总数
for (int i = 0; i < n; ++i) father[i] = i;

这样初始化，表示着每个节点一开始代表着自己。后期我们查找某个节点的代表节点的时候，只需依次跳转，直到father[i] == i就表示找到代表节点了

接下来，我们依次来看前面三种方法的实现

1.1 find

1
2
3
4
int find(int x) {
    if (x != father[x]) father[x] = find(father[x]);
    return father[x];
}

注意，这里在每次的递归中father[x] = find(x);保证最后的扁平化，保证时间复杂度保持在常数级别。

1.2 isSameSet

1
2
3
bool isSameSet(int x, int y) {
    return find(x) == find(y);
}

查看代表元素是否相同，如果相同则表示在同一个集合中

1.3 _union

1
2
3
4
5
6
7
void _union(int x, int y) {
    int fx = find(x), fy = find(y);
    // 如果不是同一个集合 则进行合并
    if (fx != fy) {
        father[fx] = fy; // 只需修改代表节点即可合并
    }
}

2. 具体案例

990. 等式方程的可满足性

给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations[i] 的长度为 4，并采用两种不同的形式之一：”a==b” 或 “a!=b”。在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。

只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回 true，否则返回 false。

这题我们可以将相等看作两个节点联通，或者说，这两个节点属于同一个集合。而不等式可以看作这两个节点不属于同一个节点。

也就是说，我们使用并查集，先将等式的组合进行合并，再根据不等式中的字母元素，判断该元素是否同属一个节点。一旦出现矛盾，则返回false

解题代码如下：

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
class Solution {
public:
    /*
        1. 对于所有的等式 可以看成合并操作
        2. 对应所有的不等式 看成这两个元素不在同一个集合中
    */
    vector<int> father;
    bool isEqual(string const& s) {
        return s[1] == '=';
    }
    int find(int x) {
        if (x != father[x]) father[x] = find(father[x]);
        return father[x];
    }
    void Union(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx != fy) {
            father[fx] = fy;
        }
    }
    bool isSameSet(int x, int y) {
        return find(x) == find(y);
    }
    bool equationsPossible(vector<string>& equations) {
        father.assign(26, 0);  
        for (char i = 'a'; i <= 'z'; ++i) father[i-'a'] = i-'a';
        for (auto s : equations) {
            if (isEqual(s)) Union(s[0]-'a', s.back()-'a');
        }
        for (auto s : equations) {
            if (!isEqual(s)) if (isSameSet(s[0]-'a', s.back()-'a')) return false;
        }
        return true;
    }
};

发表于 更新于 分类于 本文字数： 3.6k 阅读时长 ≈ 7 分钟

BFS

使用场景

针对无权图，给定一个起始点，要求其他点到起始点的最短路径，可以使用BFS（广度优先搜索）算法得出结果。

代码实现和原理分析

给出下面一个图，假设起始点为3

有向无权图

使用distance数组和visited数组分别记录每个点的最短路径和该点是否被访问过。

如需记录最短路径，则需要path数组

1
2
3
vector<int> distance(n+1, -1); // -1表示距离无穷大 如果遍历结束后distance[i]为-1 则表示与这个节点不相通
vector<bool> visited(n+1, false); // 初始化为false 表示默认都没访问到
vector<int> path(n+1, -1); // 记录前驱节点

对于起始点，其distance[start]应该初始化为0， visited[start]初始化为true

1
2
distance[start] = 0;
visited[start] = true;

开始广度优先搜索，依次标记每个未访问的节点为访问状态，这样做可以保证最短路径的节点，最先被标记， 同时也可以避免成环问题 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
queue<int> q;
q.push(start);

while (!q.empty()) {
    int size = q.size();
    while (size--) {
        int cur = q.front();
        q.pop();
        // 遍历邻居
        for (auto neighbor : graph[cur]) {
            if (!visited[neighbor]) {
                distance[neighbor] = distance[cur] + 1;
                path[neighbor] = cur;
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}

完整代码如下：

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
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main() {
	// 构造图
	vector<vector<int>> graph{ {}, {4}, {5}, {1}, {3, 2}, {3} };
	int n = 5;
	vector<int> distance(n + 1, -1);
	vector<int> path(n + 1, -1);
	vector<bool> visited(n + 1, false);
	distance[3] = 0;
	visited[3] = true;

	// 开始广度优先搜索
	queue<int> q;
	q.push(3);
	while (!q.empty()) {
		int size = q.size();
		while (size--) {
			int cur = q.front();
			q.pop();
			for (auto neighbor : graph[cur]) {
				if (!visited[neighbor]) {
					distance[neighbor] = distance[cur] + 1;
					path[neighbor] = cur;
					visited[neighbor] = true;
					q.push(neighbor);
				}
			}
		}
	}

	// 打印distance数组
	for (auto i : distance) {
		cout << i << ' ';
	}
	// 打印path数组
	cout << endl;
	for (auto i : path) {
		cout << i << ' ';
	}

	return 0;
}

时空复杂度分析

因为需要访问所有节点（最坏情况下）所以时间复杂度应该为 O(V+E) n为节点数量

空间复杂度 考虑到distance、visited和path数组的开销 应为O(V)

Dijkstra算法

使用场景

针对有权图，求最短路径问题，这里介绍的是使用堆进行优化的Dijkstra算法，而非暴力的Dijkstra算法

代码实现和原理分析

给出一个有权图，起点为1

有向有权图

Dijkstra算法的具体步骤，可以分为以下几点：

  1. 创建distance数组和visited数组，分别用于记录最短路径和该节点是否已被访问，这里的visited，还有另一层含义，即表示该节点的最短路径是否已经确定。
  2. 初始化distance和visited数组，设置distance[start] = 0;，同时需注意distance数组中的初始值要尽可能大
  3. 建立小根堆，将初始节点压入堆中
  4. 从小根堆中弹出元素
    1. 如果该节点未访问过 则visited[cur] = true;
    2. 如果该节点已访问过 则continue
    3. 处理各边
      1. 如果!visited[neighbor] && distance[cur] + weight < distance[neighbor]，则进行更新，即distance[neighbor] = distance[cur] + weight; q.push(neighbor);
      2. 其他情况不处理
    4. 重复第4步骤，直到小根堆为空

具体的代码如下：

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

// Dijkstra
// 创建图
vector<vector<vector<int>>> graph{ {{}}, {{2, 5}, {3, 100}, {4, 5}}, {{3, 3}}, {{5, 2}}, {{}}, {{1, 5}, {3, 1}} };
int start = 1, n = 5;

vector<int> distance(n + 1, INT_MAX);
vector<bool> visited(n + 1, false);
distance[start] = 0;

auto cmp = [](vector<int>& a, vector<int>& b) -> bool {
	return a[1] > b[1];
	};
// 使用优先队列创建小根堆
priority_queue<vector<int>, vector<vector<int>>, decltype(cmp)>q(cmp);
q.push({ start, 0 });

while (!q.empty()) {
	vector<int> cur = q.top();
	q.pop();
	if (visited[cur[0]]) continue;
	visited[cur[0]] = true;
	// 处理各边
	for (auto neighbor : graph[cur[0]]) {
        // neighbor.size() > 0判空
		if (neighbor.size() > 0 && !visited[neighbor[0]] && cur[1] + neighbor[1] < distance[neighbor[0]]) {
			distance[neighbor[0]] = cur[1] + neighbor[1];
			q.push({neighbor[0], distance[neighbor[0]]});
		}
	}
}

// 打印distance数组
for (auto i : distance) {
	cout << i << ' ';
}

时空复杂度分析

因为要遍历每一条边和每一个节点且要经过堆的调整 所以时间复杂度为 O((V + E) log V)
空间复杂度显然为 O(V)

0%