拓扑排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 返回有向无环图（DAG）的其中一个拓扑序
# 如果图中有环，返回空列表
# 节点编号从 0 到 n-1
def topologicalSort(n: int, edges: List[List[int]]) -> List[int]:
    g = [[] for _ in range(n)]
    in_deg = [0] * n
    for x, y in edges:
        g[x].append(y)
        in_deg[y] += 1  # 统计 y 的先修课数量

    topo_order = []
    q = deque(i for i, d in enumerate(in_deg) if d == 0)  # 没有先修课，可以直接上
    while q:
        x = q.popleft()
        topo_order.append(x)
        for y in g[x]:
            in_deg[y] -= 1  # 修完 x 后，y 的先修课数量减一
            if in_deg[y] == 0:  # y 的先修课全部上完
                q.append(y)  # 加入学习队列

    if len(topo_order) < n:  # 图中有环
        return []
    return topo_order

Dijkstra算法

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
# 返回从起点 start 到每个点的最短路长度 dis，如果节点 x 不可达，则 dis[x] = math.inf
# 要求：没有负数边权
# 时间复杂度 O(n + mlogm)，其中 m 是 edges 的长度。注意堆中有 O(m) 个元素
def Dijkstra(n: int, edges: List[List[int]], start: int) -> List[int]:
    # 注：如果节点编号从 1 开始（而不是从 0 开始），可以把 n 加一
    g = [[] for _ in range(n)]  # 邻接表
    for x, y, wt in edges:
        g[x].append((y, wt))
        # g[y].append((x, wt))  # 无向图加上这行

    dis = [inf] * n
    dis[start] = 0  # 起点到自己的距离是 0
    parent = [-1] * n
    h = [(0, start)]  # 堆中保存 (起点到节点 x 的最短路长度，节点 x)

    while h:
        dis_x, x = heappop(h)
        if dis_x > dis[x]:  # x 之前出堆过
            continue
        for y, wt in g[x]:
            new_dis_y = dis_x + wt
            if new_dis_y < dis[y]:
                dis[y] = new_dis_y  # 更新 x 的邻居的最短路
                parent[y] = x
                # 懒更新堆：只插入数据，不更新堆中数据
                # 相同节点可能有多个不同的 new_dis_y，除了最小的 new_dis_y，其余值都会触发上面的 continue
                heappush(h, (new_dis_y, y))

    return dis, parent

def get_path(parent: List[int], start: int, end: int) -> List[int]:
    if parent[end] == -1 and end != start: # end 节点不可达
        return []
    path = []
    curr = end
    while curr != -1:
        path.append(curr)
        curr = parent[curr]
    return path[::-1] # 反转路径，得到从 start 到 end 的顺序

Floyed算法

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
# 返回一个二维列表，其中 (i,j) 这一项表示从 i 到 j 的最短路长度
# 如果无法从 i 到 j，则最短路长度为 math.inf
# 允许负数边权
# 如果计算完毕后，存在 i，使得从 i 到 i 的最短路长度小于 0，说明图中有负环
# 节点编号从 0 到 n-1
# 时间复杂度 O(n^3 + m)，其中 m 是 edges 的长度
def Floyd(self, n: int, edges: List[List[int]]) -> List[List[int]]:
    f = [[inf] * n for _ in range(n)]
    # path[i][j] 记录从 i 到 j 最短路径上，i 的下一个节点
    path = [[-1] * n for _ in range(n)]

    # 创建邻接矩阵
    for i in range(n):
        f[i][i] = 0
        path[i][i] = i
    for x, y, wt in edges:
        f[x][y] = min(f[x][y], wt)  # 如果有重边，取边权最小值
        path[x][y] = y
        f[y][x] = min(f[y][x], wt)  # 无向图
        path[y][x] = x

    for k in range(n):
        for i in range(n):
            if f[i][k] == inf:  # 针对稀疏图的优化
                continue
            for j in range(n):
                f[i][j] = min(f[i][j], f[i][k] + f[k][j])
                path[i][j] = path[i][k]
    return f, path

def get_path(path: List[List[int]], start: int, end: int) -> List[int]:
    if path[start][end] == -1: # 路径不存在
        return []
    
    result_path = [start]
    curr = start
    while curr != end:
        curr = path[curr][end]
        result_path.append(curr)
    return result_path

Bellman-Ford算法

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
# 返回从起点 start 到每个点的最短路长度 dis，以及记录最短路径前驱节点的 parent 数组
# 同时返回一个布尔值 has_negative_cycle，表示图中是否存在从 start 可达的负权环
# 如果节点 x 不可达，则 dis[x] = math.inf
# 要求：图中可以有负数边权，但不能有从 start 可达的负权环（若有，最短路无意义）
# 时间复杂度 O(n*m)，其中 m 是 edges 的长度
def BellmanFord(n: int, edges: List[List[int]], start: int) -> tuple[List[int], List[int], bool]:
    dis = [inf] * n
    dis[start] = 0
    parent = [-1] * n

    # 进行 n-1 轮松弛操作（假设有 n 个节点，节点编号从 0 到 n - 1）
    for _ in range(n - 1):
        for u, v, w in edges:
            if dis[u] != inf and dis[u] + w < dis[v]:
                dis[v] = dis[u] + w
                parent[v] = u

    # 第 n 轮松弛，用于检测负权环
    has_negative_cycle = False
    for u, v, w in edges:
        if dis[u] != inf and dis[u] + w < dis[v]:
            has_negative_cycle = True
            # 在实际应用中，可以标记受负权环影响的节点
            # 例如，将它们的 dis 设为 -inf
            break
            
    return dis, parent, has_negative_cycle

# 根据 parent 数组回溯从 start 到 end 的最短路径 (与 Dijkstra 版本相同)
def get_path(parent: List[int], start: int, end: int) -> List[int]:
    if parent[end] == -1 and end != start: # end 节点不可达
        return []
    path = []
    curr = end
    while curr != -1:
        path.append(curr)
        curr = parent[curr]
    return path[::-1] # 反转路径，得到从 start 到 end 的顺序

并查集

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
class UnionFind:
    def __init__(self, n: int):
        # 一开始有 n 个集合 {0}, {1}, ..., {n-1}
        # 集合 i 的代表元是自己，大小为 1
        self._fa = list(range(n))  # 代表元
        self._size = [1] * n  # 集合大小
        self.cc = n  # 连通块个数

    # 返回 x 所在集合的代表元
    # 同时做路径压缩，也就是把 x 所在集合中的所有元素的 fa 都改成代表元
    def find(self, x: int) -> int:
        # 如果 fa[x] == x，则表示 x 是代表元
        if self._fa[x] != x:
            self._fa[x] = self.find(self._fa[x])  # fa 改成代表元
        return self._fa[x]

    # 判断 x 和 y 是否在同一个集合
    def is_same(self, x: int, y: int) -> bool:
        # 如果 x 的代表元和 y 的代表元相同，那么 x 和 y 就在同一个集合
        # 这就是代表元的作用：用来快速判断两个元素是否在同一个集合
        return self.find(x) == self.find(y)

    # 把 from 所在集合合并到 to 所在集合中
    # 返回是否合并成功
    def merge(self, from_: int, to: int) -> bool:
        x, y = self.find(from_), self.find(to)
        if x == y:  # from 和 to 在同一个集合，不做合并
            return False
        self._fa[x] = y  # 合并集合。修改后就可以认为 from 和 to 在同一个集合了
        self._size[y] += self._size[x]  # 更新集合大小（注意集合大小保存在代表元上）
        # 无需更新 _size[x]，因为我们不用 _size[x] 而是用 _size[find(x)] 获取集合大小，但 find(x) == y，我们不会再访问 _size[x]
        self.cc -= 1  # 成功合并，连通块个数减一
        return True

    # 返回 x 所在集合的大小
    def get_size(self, x: int) -> int:
        return self._size[self.find(x)]  # 集合大小保存在代表元上

树状数组

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
class FenwickTree:
    """
    树状数组 (Fenwick Tree / Binary Indexed Tree)
    支持单点更新和前缀和查询，时间复杂度均为 O(log n)
    """
    def __init__(self, size):
        """
        初始化一个大小为 size 的树状数组。
        通常 size 为原数组长度 n。内部数组大小为 n+1，使用 1-based 索引。
        """
        self.size = size
        self.tree = [0] * (size + 1)

    def _lowbit(self, x):
        """返回 x 的二进制表示中最低位的 1 所代表的值"""
        return x & (-x)

    def update(self, index, delta):
        """
        在原数组的 index 位置上增加 delta。
        index 是 1-based。
        """
        while index <= self.size:
            self.tree[index] += delta
            index += self._lowbit(index)

    def query(self, index):
        """
        查询原数组前缀 [1, index] 的和。
        index 是 1-based。
        """
        result = 0
        while index > 0:
            result += self.tree[index]
            index -= self._lowbit(index)
        return result

    def query_range(self, left, right):
        """
        查询原数组区间 [left, right] 的和。
        left 和 right 都是 1-based。
        """
        if left > right:
            return 0
        return self.query(right) - self.query(left - 1)

C++中实现动态多态

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

// 1. 定义基类 (接口)
class Shape {
public:
    // 声明一个虚函数以实现多态
    // "= 0" 使其成为纯虚函数，从而使 Shape 成为一个抽象基类
    // 这意味着 Shape 类的实例无法被创建
    virtual void draw() const = 0;

    // 声明一个虚析构函数,
    // 这能确保通过基类指针删除派生类对象时，
    // 能够正确调用派生类的析构函数
    virtual ~Shape() {
        std::cout << "Shape destructor called" << std::endl;
    }
};

// 2. 定义派生类
class Rectangle : public Shape {
public:
    void draw() const override {
        std::cout << "Drawing a Rectangle." << std::endl;
    }

    ~Rectangle() {
        std::cout << "Rectangle destructor called" << std::endl;
    }
};

class Circle : public Shape {
public:
    void draw() const override {
        std::cout << "Drawing a Circle." << std::endl;
    }

    ~Circle() {
        std::cout << "Circle destructor called" << std::endl;
    }
};

class Triangle : public Shape {
public:
    void draw() const override {
        std::cout << "Drawing a Triangle." << std::endl;
    }
    ~Triangle() {
        std::cout << "Triangle destructor called" << std::endl;
    }
};


// 3. 动态多态
int main() {
    // 创建一个用于存放不同形状的容器
    // 使用智能指针 (std::unique_ptr) 是现代C++的推荐做法，
    // 它可以自动管理内存
    std::vector<std::unique_ptr<Shape>> shapes;

    // 创建不同形状的对象并将其添加到容器中
    shapes.push_back(std::make_unique<Rectangle>());
    shapes.push_back(std::make_unique<Circle>());
    shapes.push_back(std::make_unique<Triangle>());

    // 遍历容器并通过基类指针调用 draw() 方法
    // 在运行时，将根据对象的实际类型调用相应的 draw() 方法
    std::cout << "--- Calling draw() on different shapes ---" << std::endl;
    for (const auto& shape : shapes) {
        shape->draw(); // 此处展示了动态多态
    }
    
    std::cout << "\n--- Destructors will be called automatically ---" << std::endl;
    // 当 main 函数结束时，智能指针会自动释放内存，
    // 并且由于基类的析构函数是虚函数，会正确调用每个派生类的析构函数
    
    return 0;
}

C++多线程

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
101
102
103
104
#include <iostream>
#include <thread>
#include <vector>
#include <queue>
#include <mutex>
#include <condition_variable>
#include <chrono> // 用于 std::chrono::milliseconds

// 模拟共享数据缓冲区
std::queue<int> g_dataQueue;
// 用于保护共享数据的互斥锁
std::mutex g_mutex;
// 用于线程间同步的条件变量
std::condition_variable g_conditionVariable;
// 标志，用于通知消费者没有更多数据了
bool g_finished = false;

// 生产者线程函数
void producer(int numItems) {
    for (int i = 0; i < numItems; ++i) {
        // 模拟生产一个数据项需要一些时间
        std::this_thread::sleep_for(std::chrono::milliseconds(100));
        
        {
            // 使用 std::lock_guard 自动管理互斥锁的加锁与解锁
            std::lock_guard<std::mutex> lock(g_mutex);
            
            // 将生产的数据放入队列
            int item = i + 1;
            g_dataQueue.push(item);
            std::cout << "Producer produced: " << item << std::endl;
        } // lock_guard 在此处超出作用域，自动释放锁
        
        // 通知一个等待的消费者线程数据已准备好
        g_conditionVariable.notify_one();
    }

    // 生产完成后，设置标志并通知所有消费者
    {
        std::lock_guard<std::mutex> lock(g_mutex);
        g_finished = true;
    }
    g_conditionVariable.notify_all(); // 唤醒所有可能在等待的消费者
}

// 消费者线程函数
void consumer() {
    while (true) {
        int item;

        {
            // 使用 std::unique_lock，因为它能与条件变量更好地配合
            std::unique_lock<std::mutex> lock(g_mutex);
            
            // 等待，直到队列不为空或生产已结束
            // wait方法会自动释放锁，并让线程休眠。
            // 当被唤醒时，它会重新获取锁并检查lambda表达式（第二个参数）的条件。
            // 如果条件为false，它会再次释放锁并继续休眠。
            // 这种方式可以避免“虚假唤醒”（spurious wakeups）。
            g_conditionVariable.wait(lock, []{
                return !g_dataQueue.empty() || g_finished;
            });
            
            // 如果队列为空且生产已经结束，则消费者可以退出
            if (g_dataQueue.empty() && g_finished) {
                break;
            }
            
            // 从队列中取出数据
            item = g_dataQueue.front();
            g_dataQueue.pop();
            
        } // unique_lock 在此处超出作用域，自动释放锁

        // 处理数据（在解锁后进行，以减少锁的持有时间）
        std::cout << "Consumer consumed: " << item << std::endl;
        std::this_thread::sleep_for(std::chrono::milliseconds(150)); // 模拟消费
    }
    std::cout << "Consumer finished." << std::endl;
}

int main() {
    // 定义生产者将要生产的数据量
    const int itemsToProduce = 10;
    
    // 创建并启动生产者线程
    std::thread producerThread(producer, itemsToProduce);

    // 创建并启动两个消费者线程
    std::thread consumerThread1(consumer);
    std::thread consumerThread2(consumer);

    std::cout << "Main thread: Starting producer and consumers." << std::endl;

    // 等待所有线程执行完毕
    // join() 会阻塞主线程，直到目标线程执行结束
    producerThread.join();
    consumerThread1.join();
    consumerThread2.join();

    std::cout << "Main thread: All threads have finished." << std::endl;

    return 0;
}

C++多线程死锁

死锁（Deadlock）是指两个或多个线程在执行过程中，因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都将无法继续执行。

这个例子将创建两个线程和两个互斥锁（mutex）。每个线程都需要获取这两个锁才能完成工作，但它们会以相反的顺序来尝试获取锁，从而导致死锁。

  • 线程1: 尝试先锁定 mutex1，再锁定 mutex2。
  • 线程2: 尝试先锁定 mutex2，再锁定 mutex1。

当线程1锁定了 mutex1 并准备锁定 mutex2 的同时，线程2可能已经锁定了 mutex2 并正在准备锁定 mutex1。这时，两个线程都会无限期地等待对方释放自己需要的锁，从而形成死锁。

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
#include <iostream>
#include <thread>
#include <mutex>
#include <chrono>

// 创建两个全局互斥锁
std::mutex mutex1;
std::mutex mutex2;

// 线程1的执行函数
void worker1() {
    std::cout << "Worker 1 started." << std::endl;

    // 1. 锁定第一个互斥锁
    std::cout << "Worker 1 trying to lock mutex1..." << std::endl;
    std::lock_guard<std::mutex> lock1(mutex1);
    std::cout << "Worker 1 acquired mutex1." << std::endl;

    // 人为地增加一个小的延时，以确保另一个线程有时间运行并锁定mutex2
    // 这使得死锁的发生更加稳定和可复现
    std::this_thread::sleep_for(std::chrono::milliseconds(50));

    // 2. 尝试锁定第二个互斥锁
    // 此时，worker2可能已经持有了mutex2，导致此行代码阻塞
    std::cout << "Worker 1 trying to lock mutex2..." << std::endl;
    std::lock_guard<std::mutex> lock2(mutex2);
    std::cout << "Worker 1 acquired mutex2." << std::endl;

    // 以下代码将永远不会被执行
    std::cout << "Worker 1 finished its work." << std::endl;
}

// 线程2的执行函数（注意锁的顺序与worker1相反）
void worker2() {
    std::cout << "Worker 2 started." << std::endl;

    // 1. 锁定第一个互斥锁 (与worker1的顺序相反)
    std::cout << "Worker 2 trying to lock mutex2..." << std::endl;
    std::lock_guard<std::mutex> lock2(mutex2);
    std::cout << "Worker 2 acquired mutex2." << std::endl;
    
    // 同样增加延时，以增加死锁发生的机会
    std::this_thread::sleep_for(std::chrono::milliseconds(50));

    // 2. 尝试锁定第二个互斥锁
    // 此时，worker1可能已经持有了mutex1，导致此行代码阻塞
    std::cout << "Worker 2 trying to lock mutex1..." << std::endl;
    std::lock_guard<std::mutex> lock1(mutex1);
    std::cout << "Worker 2 acquired mutex1." << std::endl;

    // 以下代码将永远不会被执行
    std::cout << "Worker 2 finished its work." << std::endl;
}

int main() {
    std::cout << "Starting deadlock demonstration..." << std::endl;

    // 创建并启动两个线程
    std::thread t1(worker1);
    std::thread t2(worker2);

    // 等待两个线程结束。
    // 由于死锁，它们永远不会结束，所以主线程会在这里永久阻塞。
    t1.join();
    t2.join();

    // 这行代码将永远不会被执行
    std::cout << "Program finished." << std::endl;

    return 0;
}