Algorithms

LeetCode 题解模板

[TOC]

## 题目解读



## 解法 1

### 数学原理



### 算法与数据结构



### 参考代码

``` c++
#include <iostream>

class Solution {
public:

};

int main() {
    std:: cout << Solution(). << std:: endl;

    return 0;
}

```

### 复杂度分析

- 时间复杂度：$O(*)$，；
- 空间复杂度：$O(*)$，；

堆

• 大根堆

class MaxHeap {
  public:
    void push(int value) {
        heap.push_back(value);
        heapifyUp(heap.size() - 1);
    }

    void pop() {
        if (heap.empty()) {
            throw runtime_error("Heap is empty");
        }

        heap[0] = heap.back();
        heap.pop_back();

        if (!heap.empty()) {
            heapifyDown(0);
        }
    }

    int top() const {
        if (heap.empty()) {
            throw runtime_error("Heap is empty");
        }

        return heap[0];
    }

    bool empty() const { return heap.empty(); }

    int size() const { return heap.size(); }

  private:
    vector<int> heap;

    void heapifyUp(int index) {
        while (index > 0) {
            int parent = (index - 1) / 2;

            if (heap[parent] >= heap[index]) {
                break;
            }

            swap(heap[parent], heap[index]);
            index = parent;
        }
    }

    void heapifyDown(int index) {
        int n = heap.size();

        while (true) {
            int left = index * 2 + 1;
            int right = index * 2 + 2;
            int largest = index;

            if (left < n && heap[left] > heap[largest]) {
                largest = left;
            }

            if (right < n && heap[right] > heap[largest]) {
                largest = right;
            }

            if (largest == index) {
                break;
            }

            swap(heap[index], heap[largest]);
            index = largest;
        }
    }
};

Dijkstra's Algorithm

We assume that \(w(u, v) \geq 0\) for each edge \((u, v)\in E\)

DIJKSTRA. (G,w,s)
1 INITIALIZE-SINGLE-SOURCE(G,s)
2 S=∅
3 Q=G.V  // Q: min-priority queue
4 while Q≠∅
5   u=D EXTRACT-MIN(Q)
6   S=S∪{u}
7   for each vertex v∈G.Adj[u]
8       RELAX(u,v,w)

void dijkstra(vector<vector<pair<int, int>>> &graph, int src) {
    int n = graph.size();
    vector<int> dist(n, INT_MAX);
    // Sorted by distance, the vertices with smaller distance are ranked first.
    priority_queue<pair<int, int>, vector<pair<int, int>>,
                   greater<pair<int, int>>>
        pq; // Store the vertices to be processed and their distance from the
            // source point

    pq.push({0, src});
    dist[src] = 0;

    // O((V+E)logV)
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();

        for (auto it : graph[u]) {
            int v = it.first;
            int weight = it.second;

            if (dist[v] > dist[u] + weight) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        cout << i << "\t" << dist[i] << endl;
    }
}

// Test Code
#include <climits> // for INT_MAX
#include <iostream>
#include <queue>
#include <utility> // for pair
#include <vector>

using namespace std;

void dijkstra(vector<vector<pair<int, int>>> &graph, int src);

int main() {
    // Adjacency table
    vector<vector<pair<int, int>>> graph = {
        {{1, 4}, {2, 3}}, {{2, 1}, {3, 2}}, {{3, 4}}, {}};
    int src = 0;
    dijkstra(graph, src);

    return 0;
}

void dijkstra(vector<vector<pair<int, int>>> &graph, int src) {
    // ...
}

参考资料

[1] C. E. Leiserson, T. H. Cormen, R. L. Rivest, and C. Stein, "Introduction to Algorithms, 3rd Edition," MIT Press, 2009.