文章

2`并查集，单调栈，字典树，A※

发表于 更新于
作者 senlongan
17 分钟阅读

并查集

并查集使用树形数据结构，用于处理不相交集合的合并及查询问题，从而加快查询效率（比如pq元素是否属于同集合）

经典问题：亲戚/朋友问题：例如(a,b) 即a是b的朋友，且(b,c)，则abc互为朋友关系

数据结构：通常由数组实现

算法:

此处元素整形，如果是string，应使用unordered_map<string, string>

  • init():初始化
1
2
3
4
5

void init(int n)
{
    for (int i = 1; i <= n; ++i)
        parents[i] = i;//元素i的父节点为本身，每个元素单独为一个集合
}

展开

  • merge(p,q): 把两个不相交的集合合并为一个集合

    每棵树表示一组集合，一旦两个元素所在的根节点组成父子关系，那么两者所在的集合将合并为一个集合

1
2
3
4

void merge(int i, int j)
{
    parents[findRoot(i)] = findRoot(j);//i的根节点指向j的根节点，变为同一集合
}

展开

  • findRoot(p): 查找p所在集合的根节点
1
2
3
4

int findRoot(int x)
{
    return x == parents[x] ? x : findRoot(parents[x]);//如果x是根节点直接返回，否则递归查询父节点
}

展开

  • isConnected(p,q):查询两个元素是否在同一个集合中
1
2
3
4

bool isConnected(p,q)
{
    return findRoot(p) == findRoot(q);//如果两个元素根节点相同，则在一个集合中
}

展开

  • 路径压缩：在查询节点p的根节点q时，如果pq路径很长，每次都要花费很多查询时间，如何保证查询时间复杂度只需要O(1)呢？

    每次的findRoot都相当于对树的重构，所有以q为根树内的节点，全部重构为直接指向q，从而在以后的findRoot时，可以一步到位

1
2
3
4

int findRoot(int x)
{
    return x == parents[x] ? x : (parents[x] = findRoot(parents[x]));
}

展开

单调栈

单调栈（Monotone Stack）：一种特殊的栈。在栈的「先进后出」规则基础上，要求「从 栈底 到 栈顶 的元素是单调递增 / 单调递减

单调递增栈：从 栈底 到 栈顶 的元素是单调增的

  • 入栈：只有比栈顶元素大的元素才能直接进栈，否则需要先将栈中比当前元素大的元素出栈，再将当前元素入栈 0 经典问题：

时间复杂度为 O(n) 一次遍历的情况下，求解出某个元素左边或者右边第一个比它大或者小的元素

问题：

对于给定的整数数组nums，找到每个元素右侧第一个比自己大的数的下标，如果没有，填-1

关注的是比自己大的元素下标，因此我们维护一个单调递减栈，反之如果要找到右侧比自己小的元素下标，维护一个单调递增栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14

vector<int> solve(vector<int>& nums) {
  int n = nums.size();
  vector<int> res(n, -1);//元素初始为-1
  stack<int> st;

  for (int i = 0; i < n; ++i) {
    while (!st.empty() && nums[i] > nums[st.top()]) {
      res[st.top()] = i;//出栈时操作
      st.pop();
    }
    st.push(i);
  }
  return res;
}

展开

如果是左侧查询，并不依赖还未遍历到的元素，因此可以遍历到哪个元素，直接求得这个元素的结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14

vector<int> solve(vector<int>& nums) {
  int n = nums.size();
  vector<int> res(n, -1);
  stack<int> st;

  for (int i = 0; i < n; ++i) {
    while (!st.empty() && nums[i] > nums[st.top()]) {
      st.pop();
    }
    res[i] = st.empty() ? -1 : st.top();//入栈时操作
    st.push(i);
  }
  return res;
}

展开

总结：

求右侧第一个比自己大的元素从左向右遍历，单调递减栈，出栈时操作
求右侧第一个比自己小的元素从左向右遍历，单调递增栈，出栈时操作
求左侧第一个比自己大的元素从左向右遍历，单调递减栈，入栈时操作
求左侧第一个比自己小的元素从左向右遍历，单调递增栈，入栈时操作

字典树

字典树/前缀树：使用树形数据结构，保存大量的字符串，每个从根节点开始的路径（不一定到叶结点）表示一个字符串，从而加快查询效率（就像查字典一样）

数据结构：

第一种：

  • 根节点为空，不存储任何字符串
  • int N = 1000050;//数组数量
  • int trie[N][26];26叉树，用2维数组，元素值为节点编号
  • int cnt[N];节点编号n存储了多少个完整的单词
  • int id;节点唯一编号（标识）

第2种：（数据大小不确定，动态分配内存时）

  • calss有类成员 一维数组保存26个子节点，每个节点是一个class
  • 包含是否存储单词，以便查询

算法：

  • 插入:
1
2
3
4
5
6
7
8
9
10
11

void insert(string s)
{
	int p = 0;//从根节点索引开始
	for (int i = 0; i < s.size(); i++)
	{
		int x = s[i] - 'a';
		if (trie[p][x] == 0) trie[p][x] = ++id;//除了根节点为0，其他不为0
		p = trie[p][x];
	}
	cnt[p]++;
}

展开

  • 查询:
1
2
3
4
5
6
7
8
9
10
11

int  find(string s)
{
	int p = 0;//从根节点索引开始
	for (int i = 0; i < s.size(); i++)
	{
		int x = s[i] - 'a';
		if (trie[p][x] == 0)return 0;//没有此节点
		p = trie[p][x];
	}
	return cnt[p];//如果没有存储单词即0，返回没有找到，否则找到
}

展开

A*

作用：

可以在指定区域内 A到B 的多条可行路径中 快速找到最短路径

其他搜索算法：

  • 深度优先搜索，会沿着一条路径一直深入探索，直到无法继续或达到目标节点才回溯（寻找AB最短路径效率很差）
  • 广度优先搜索，会一层一层地向外扩展，先遍历完当前层的所有节点，再进入下一层（各个方向平等的搜索），直到找到叶节点 / 目标节点 停止
  • Dijkstra，每个节点到起点的距离作为优先级，和广度一样，使用队列遍历节点，不过这里因为代价的关系使用优先队列（当每个节点代价相等，它和bfs 将花费一样的时间查询）
  • 最佳优先搜索，每个节点到终点的距离作为优先级，每次考虑距离中点最近的那个节点，就可以沿着某方向的路径前进，可以大大加快路径的搜索速度（如果AB间有障碍物，很有可能搜索不到最短路径）

A*算法：

1741617841232

A* 实际上是综合上面这些算法的特点于一身的，像bfs一样每次向外搜索邻居节点加入代遍历列表，会选取代价最小的方向进行下一次搜索，它的代价结合了Dijkstra和最佳优先搜索

  • gn是距离起点的代价，hn距离终点的估算（因为路径中有未知的障碍物，无法知道真正的代价，所以我们计算的只是忽略障碍物的代价）代价（启发函数），两者相加为fn节点代价
  • hn可以控制算法的速度和精确度
    • 如果hn == 0，则退化成了Dijkstra算法
    • hn <= n到终点的代价，能保证找到最短路径, hn值越小，算法越慢
    • hn == n到终点的代价，能保证找到最短路径,算法很快
    • hn > n到终点的代价，不能保证找到最短路径, 算法很快
    • 当hn比g(n)大很多，则退化成了最佳优先搜索
  • 启发函数常见的有：
    • 曼哈顿距离、只允许朝上下左右四个方向移动
    • 对角距离、允许朝八个方向移动（对角代价更大）
    • 欧几里得距离、允许朝任何方向移动

steps：

  • 确立搜索区域，
  • 简化搜索区域：划分网格 / 节点（可以用vector< vector< Node*»存储，每个节点有可走（非障碍物），不可走（障碍物）两种情况）
  • 开始搜索算法:
    • 每次选取优先级最高（值最小）的节点
    • 两个集合open_set和close_set，表示待遍历的节点，与已遍历的节点，其他未遍历的不在两个集合中
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

// 定义节点结构
struct Node {
    int x, y; // 节点的坐标
    float g;  // 从起点到当前节点的实际代价
    float h;  // 从当前节点到终点的启发式估计代价
    float f;  // 优先级

    Node* parent; // 父节点指针

    bool isWalkable;//是否可走

    Node(int x, int y, float g = 0, float h = 0, Node* parent = nullptr, bool isWalkable = true)//构造
        : x(x), y(y), g(g), h(h), f(g + h), parent(parent), isWalkable(isWalkable) {}

    // 重载比较运算符，用于优先队列
    bool operator<(const Node& other) const {
        return f > other.f; // 注意：优先队列默认是最大堆，所以这里用 > 来实现最小堆
    }
};

// 计算启发式估计代价（曼哈顿距离） 
float heuristic(int x1, int y1, int x2, int y2) {
    return std::abs(x1 - x2) + std::abs(y1 - y2);
}

// 两节点的距离(曼哈顿距离)
float distance(Node* a, Node* b) {
    return std::abs(a->x - b->x) + std::abs(a->y - b->y);
}

// 获取上下左右节点
std::vector<Node*> getNeighbors(Node* node) {
    std::vector<Node*> neighbors;
    //如果之前划分的网格是2维数组,则直接从数组查询就好，不用new创建
    neighbors.push_back(new Node(node->x + 1, node->y));
    neighbors.push_back(new Node(node->x - 1, node->y));
    neighbors.push_back(new Node(node->x, node->y + 1));
    neighbors.push_back(new Node(node->x, node->y - 1));
    return neighbors;
}

// A*算法实现
std::vector<Node*> AStar(Node* start, Node* goal) {//接受起点和终点，返回最短路径
    // 初始化open_set和close_set
    std::priority_queue<Node*> open_set;
    std::unordered_set<Node*> close_set;

    // 将起点加入open_set中
    open_set.push(start);

    while (!open_set.empty()) {
        // 每次从open_set中选取优先级最高的节点n
        Node* current = open_set.top();
        open_set.pop();

        // 如果节点n为终点（找到了path）
        if (current->x == goal->x && current->y == goal->y) {
            // 从终点开始逐步追踪parent节点，一直达到起点
            std::vector<Node*> path;
            while (current != nullptr) {
                path.push_back(current);
                current = current->parent;
            }
            // 返回找到的结果路径，算法结束
            return path;
        } 

        // 将节点n从open_set中删除，并加入close_set中
        close_set.insert(current);

        // 遍历节点n所有的邻近节点
        for (Node* neighbor : getNeighbors(current)) {
            // 如果邻近节点m在close_set中，或者是不可走的，则跳过
            if (close_set.find(neighbor) != close_set.end() || !isWalkable) {
                continue;
            }

            // 计算 经由当前节点 到邻近节点的实际代价
            float tentative_g = current->g + distance(current, neighbor);

            // 如果邻近节点m不在open_set中，或者neighbor在open_set中但，是经由current节点的g值更小（需要更新父节点指向current，以及 重新计算fgh代价值）
            if (open_set.find(neighbor) == open_set.end() || tentative_g < neighbor->g) {
                // 设置节点m的parent为节点n
                neighbor->parent = current;
                // 更新节点m的g，h，f值
                neighbor->g = tentative_g;
                neighbor->h = heuristic(neighbor->x, neighbor->y, goal->x, goal->y);
                neighbor->f = neighbor->g + neighbor->h;
                // 如果邻近节点m不在open_set中，则将其加入open_set
                if (open_set.find(neighbor) == open_set.end()) {
                    open_set.push(neighbor);
                }
            }
        }
    }

    // 如果open_set为空且未找到路径，返回空路径
    return std::vector<Node*>();
}

展开

runtime error: member access within null pointer of type ‘ListNode‘

链表的每个节点都是struct，我们通常会用指向struct的指针，在访问时很容易出现访问空指针（指针指向mullptr）的情况，因此需要在访问前判断一下，head == nullptr ，head->next == nullptr ，cur == nullptr , cur->next == nullptr

其他常见算法和数据结构：

  • 暴力，循环，递归（深搜dfs，回溯），二分查找，动态规划dp，贪心，双指针，快慢指针，滚动数组，滑动窗口，广度bfs，分治，并查集（合并，查询），前缀和，排序（拓步，归并，计数，桶，基数）
  • 字符串，队列（优先队列），栈，单调栈，哈希，集合，数组（1.2维），链表（双向），矩阵，树（N叉树），字典树，图，空间数据结构
算法与数据结构
本文由作者按照 CC BY 4.0 进行授权
本页总访问量次