首页 算法题集锦
文章
取消

算法题集锦

发表于 2023/10/09
作者 Olimi
阅读量: 19 分钟阅读

Owner: Olimi tags: 总结, 见闻分享 date: 2023年10月9日 22:15 status: Published type: Post

top-k问题

第 k个max。快排的思路，对pivot二分找order，然后就可以排除一半。平均复杂度是O（n）

Dijkstra算法

迪杰斯特拉（Dijkstra）算法是一种用于在图中找到最短路径的算法。这个算法用于找到从起始节点到所有其他节点的最短路径。以下是该算法的一般步骤：

  1. 创建两个集合，已访问节点集合（visited）和未访问节点集合（unvisited）。起始节点加入未访问节点集合。
  2. 设置起始节点的距离为0，所有其他节点的距离为无穷大（在实际应用中，这可以是一个很大的值）。
  3. 选择未访问节点集合中距离最小的节点，访问该节点的所有未访问邻居。对于每个邻居，计算从当前节点到邻居节点的距离，并更新邻居节点的距离值（如果计算出的新距离小于原来的距离值）。
  4. 当前节点加入已访问节点集合，从未访问节点集合中移除。
  5. 如果目标节点已被访问，或者未访问节点集合中最小距离为无穷大（这意味着没有路径连接到目标节点），则算法结束。
  6. 否则，回到第3步。
    • 算法实现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

     #include <queue>
 #include <vector>
 #include <utility> // for pair
 #include <iostream>
 #include <limits> // for numeric_limits
    
 using namespace std;
    
 typedef pair<int, int> Pair;
    
 vector<int> dijkstra(vector<vector<Pair>> graph, int start) {
     int n = graph.size();
     priority_queue<Pair, vector<Pair>, greater<Pair>> pq; // min heap
     vector<int> distances(n, numeric_limits<int>::max());
    
     pq.push(make_pair(0, start));
     distances[start] = 0;
    
     while (!pq.empty()) {
         int dist = pq.top().first;
         int prev = pq.top().second;
         pq.pop();
    
         vector<Pair>& neighbors = graph[prev];
    
         for (auto& neighbor : neighbors) {
             int next = neighbor.first;
             int nextDist = neighbor.second;
    
             if (distances[prev] + nextDist < distances[next]) {
                 distances[next] = distances[prev] + nextDist;
                 pq.push(make_pair(distances[next], next));
             }
         }
     }
    
     return distances;
 }
    
 int main() {
     vector<vector<Pair>> graph = {
         { make_pair(1, 3), make_pair(2, 1) },
         { make_pair(2, 3) },
         { make_pair(0, 2), make_pair(1, 1), make_pair(3, 2) },
         { make_pair(0, 4), make_pair(2, 5) }
     };
        
     vector<int> distances = dijkstra(graph, 0);
    
     for (int i = 0; i < distances.size(); i++)
         cout << "The shortest distance from node 0 to node " << i << " is " << distances[i] << endl;
    
     return 0;
 }

  • 算法实现2，邻接矩阵：

    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

      #include <limits>
  #include <vector>
  #include <iostream>
  #include <queue>
    
  using namespace std;
    
  const int INF = numeric_limits<int>::max();
    
  vector<int> dijkstra(vector<vector<int>> graph, int start) {
      int n = graph.size();
      vector<int> distances(n, INF);
      vector<bool> visited(n, false);
      priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    
      distances[start] = 0;
      pq.push({0, start});
    
      while (!pq.empty()) {
          int u = pq.top().second;
          pq.pop();
          if (visited[u])
              continue;
          visited[u] = true;
    
          for (int v = 0; v < n; v++) {
              if (graph[u][v] != INF && distances[u] != INF && distances[u] + graph[u][v] < distances[v]) {
                  distances[v] = distances[u] + graph[u][v];
                  pq.push({distances[v], v});
              }
          }
      }
    
      return distances;
  }
    
  int main() {
      vector<vector<int>> graph = {
          {0, 4, INF, 2, INF},
          {4, 0, 4, 1, INF},
          {INF, 4, 0, 1, 3},
          {2, 1, 1, 0, 7},
          {INF, INF, 3, 7, 0}
      };
    
      vector<int> distances = dijkstra(graph, 0);
    
      for (int i = 0; i < distances.size(); i++)
          cout << "The shortest distance from node 0 to node " << i << " is " << distances[i] << endl;
    
      return 0;
  }

  • m*n的二维矩阵？不是很懂。

    如果你有一个m*n的邻接矩阵（也就是说，你的图不是一个完全图，而是一个有向图），你仍然可以使用Dijkstra算法，但是你需要对算法做一些小的修改。

    你可以将m*n的邻接矩阵看作是一个图，其中每个格子是一个节点，每个节点与其上下左右的邻居相连。然后，你可以将这个图转换为一个一维的邻接矩阵，然后在这个一维的邻接矩阵上运行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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

      #include <limits>
  #include <vector>
  #include <iostream>
  #include <queue>
    
  using namespace std;
    
  const int INF = numeric_limits<int>::max();
  const vector<pair<int, int>> directions{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
  vector<int> dijkstra(vector<vector<int>> graph, pair<int, int> start) {
      int m = graph.size();
      int n = graph[0].size();
      vector<vector<int>> distances(m, vector<int>(n, INF));
      vector<vector<bool>> visited(m, vector<bool>(n, false));
      priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
    
      distances[start.first][start.second] = graph[start.first][start.second];
      pq.push({graph[start.first][start.second], start});
    
      while (!pq.empty()) {
          pair<int, int> u = pq.top().second;
          pq.pop();
          if (visited[u.first][u.second])
              continue;
          visited[u.first][u.second] = true;
    
          for (auto& direction : directions) {
              int x = u.first + direction.first;
              int y = u.second + direction.second;
              if (x >= 0 && x < m && y >= 0 && y < n && distances[u.first][u.second] + graph[x][y] < distances[x][y]) {
                  distances[x][y] = distances[u.first][u.second] + graph[x][y];
                  pq.push({distances[x][y], {x, y}});
              }
          }
      }
    
      // Convert 2D distances matrix to 1D distances array
      vector<int> res(m * n);
      for (int i = 0; i < m; ++i) {
          for (int j = 0; j < n; ++j) {
              res[i * n + j] = distances[i][j];
          }
      }
    
      return res;
  }
    
  int main() {
      vector<vector<int>> graph = {
          {1, 3, 1},
          {1, 5, 1},
          {4, 2, 1}
      };
    
      vector<int> distances = dijkstra(graph, {0, 0});
    
      for (int i = 0; i < distances.size(); i++)
          cout << "The shortest distance from node (0, 0) to node (" << i / graph[0].size() << ", " << i % graph[0].size() << ") is " << distances[i] << endl;
    
      return 0;
  }

    在这个实现中，dijkstra函数首先初始化所有节点到起始节点的距离为无穷大，除了起始节点本身到自己的距离为0。然后，它使用一个优先队列来保存所有已经找到但还未访问的节点，并按照这些节点的最短路径长度进行排序。每一步，它都会从优先队列中取出一个未访问的节点，然后更新所有从这个节点直接可达的节点的最短路径长度。这个过程会一直持续，直到优先队列为空，也就是说所有可达的节点都已经被访问过。

    在main函数中，我们创建了一个图，并调用dijkstra函数来计算从节点0到所有其他节点的最短距离。

LRU Cache

使用STL的list和unorder_map，考虑大规模数据量下重复删除、添加的问题。另外可以自行设计链表和哈希表等数据结构更高效地自定义。懒得弄了。

  • 实现参考

    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

      class LRUCache {
  public:
      LRUCache(int capacity) {
          this->capacity = capacity;
      }
    
      int get(int key) {
          if (cache.find(key) == cache.end()) {
              return -1;
          } else {
              // 将key对应的node移到链表头部
              lru.splice(lru.begin(), lru, cache[key]);
              auto v = *cache[key];
              cache[key] = lru.begin();
              return cache[key]->second;
          }
      }
    
      void put(int key, int value) {
          if (cache.find(key) == cache.end()) {
              if (lru.size() == capacity) {
                  auto &lru_back = lru.back();
                  cache.erase(lru_back.first);
                  // 修改尾部的节点，改为新的键值对
                  lru_back.first = value;
                  lru_back.second = value;
                  lru.splice(lru.begin(), lru, --lru.end());
                  cache[key] = lru.begin();
              } else {
                  // 插入新的节点
                  lru.emplace_front(key, value);
                  cache[key] = lru.begin();
              }
    
          } else {
              // 更新，移动
              cache[key]->second = value;
              lru.splice(lru.begin(), lru, cache[key]);
          }
      }
    
  private:
      int capacity;
      list<pair<int, int>> lru;
      unordered_map<int, list<pair<int, int>>::iterator> cache;
  };

中位数

给一个数组，再给一个这个数组下标作为元素的数组，逐个删除元素，计算中位数。

  • 代码

    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

      int main() {
      int t;
      cin >> t;
      while (t--) {
          int n;
          cin >> n;
          vector<int> a(n), b(n - 1);
          for (int i = 0; i < n; ++i) {
              cin >> a[i];
          }
          // 找到不在b中的那个index，使用位图法标记所有在b中的index。
          vector<bool> flag(n, false);
          for (int j = 0; j < n - 1; ++j) {
              cin >> b[j];
              flag[b[j] - 1] = true;
          }
          int index = 0;
          for (int i = 0; i < n; ++i) {
              if (!flag[i]) {
                  index = i;
                  break;
              }
          }
    
          // Reverse b
          reverse(b.begin(), b.end());
    
          multiset<int> data;
          data.insert(a[index]);
    
          vector<double> medians;
          medians.push_back(a[index]);
    
          auto mid = data.begin();
    
          for (int i: b) {
              auto idx = i - 1;
              data.insert(a[idx]);
    
              // Adjust mid iterator
              if (data.size() == 1) {
                  mid = data.begin();
              } else if (a[idx] < *mid) {
                  if (data.size() % 2 != 0) --mid;
              } else {
                  if (data.size() % 2 == 0) ++mid;
              }
    
              // Compute median
              if (data.size() % 2 != 0) {
                  medians.push_back(*mid);
              } else {
                  medians.push_back((*mid + *prev(mid)) / 2.0);
              }
          }
    
          // Print medians in reverse order
          reverse(medians.begin(), medians.end());
          for (auto median: medians) {
              cout << median << endl;
          }
      }
    
      return 0;
  }

KMP

假设我们有一个文本串 “ABABABCAB”，我们想在其中找到模式串 “ABABC”。使用 KMP 算法的话，首先我们需要创建一个部分匹配表。

部分匹配表的创建方法是：对于模式串的每个位置，找出该位置左侧的所有前缀和后缀的最长公共元素长度。我们先假定模式串 “ABABC” 的部分匹配表如下：

ABABC
00120

我们开始从文本串的第一个字符开始匹配。每当字符匹配，我们就将文本串和模式串的位置都向后移动一位。一旦出现不匹配的字符，我们就查看模式串中最后一个匹配字符的部分匹配值。

例如，当我们在文本串的第5位 ‘A’ 和模式串的第5位 ‘C’ 不匹配时，我们看到模式串的前4位 ‘ABAB’ 的最后一个字符 ‘B’ 的部分匹配值为2。这意味着 ‘ABAB’ 的最长前缀和后缀公共元素是 ‘AB’，长度为2。

因此，我们将模式串向右移动2位，使得 ‘AB’ 与文本串中的 ‘AB’ 对齐。然后，我们继续比较文本串的下一个字符 ‘A’ 和模式串的当前字符 ‘A’，由于它们匹配，所以我们继续进行。

这样，每当字符不匹配，我们就利用部分匹配表跳过一些已知不会匹配的字符，从而提高了搜索效率。

匹配表构建：

对于模式串的每个位置，计算该位置左侧的所有前缀和后缀的最长公共元素长度，可以通过以下步骤进行：

以模式串 “ABABC” 为例，我们为每个字符构建部分匹配表。

  1. 字符 ‘A’：这是模式串的第一个字符，所以其左侧没有其他字符，因此它的部分匹配值为 0。
  2. 字符 ‘B’：它的左侧只有一个字符 ‘A’。既然 ‘A’ 没有前缀和后缀，所以它的部分匹配值也是 0。
  3. 字符 ‘A’：它的左侧有两个字符 ‘AB’。’AB’ 的所有前缀有：’A’，所有后缀有：’B’。它们没有公共元素，因此这个位置的部分匹配值为 0。
  4. 字符 ‘B’：它的左侧有三个字符 ‘ABA’。’ABA’ 的所有前缀有：’A’, ‘AB’，所有后缀有：’A’, ‘BA’。它们的最长公共元素是 ‘A’，长度为1，因此这个位置的部分匹配值为 1。
  5. 字符 ‘C’：它的左侧有四个字符 ‘ABAB’。’ABAB’ 的所有前缀有：’A’, ‘AB’, ‘ABA’，所有后缀有：’B’, ‘AB’, ‘BAB’。它们的最长公共元素是 ‘AB’，长度为2，因此这个位置的部分匹配值为 2。

通过上述步骤，我们就得到了模式串 “ABABC” 的部分匹配表：

ABABC
00120

实际上，计算部分匹配表是一个动态规划的过程，可以通过一些优化的方法来提高效率，但基本思想是一样的。

代码实现：

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

#include <vector>
#include <string>
#include <iostream>
using namespace std;

// 这是我们之前定义的函数，用于计算部分匹配表
vector<int> computePrefixFunction(string pattern)
{
    int m = pattern.length();
    vector<int> pi(m);
    pi[0] = 0;
    int j = 0;

    for (int i = 1; i < m; ++i)
    {
        while (j > 0 && pattern[i] != pattern[j])
        {
            j = pi[j - 1];
        }

        if (pattern[i] == pattern[j])
        {
            ++j;
        }

        pi[i] = j;
    }

    return pi;
}

// KMP 字符串匹配函数
void KMP(string text, string pattern)
{
    int n = text.length();
    int m = pattern.length();
    vector<int> pi = computePrefixFunction(pattern);
    cout << "部分匹配表为：" << endl;
    for (auto i : pi)
    {
        cout << i << " ";
    }
    cout << endl;

    int j = 0;

    for (int i = 0; i < n; ++i)
    {
        while (j > 0 && text[i] != pattern[j])
        {
            j = pi[j - 1];
        }

        if (text[i] == pattern[j])
        {
            ++j;
        }

        if (j == m)
        {
            cout << "Pattern found at index: " << i - m + 1 << endl;
            j = pi[j - 1];
        }
    }
}

int main()
{
    string text = "ABABABCAB";
    string pattern = "ABABC";
    KMP(text, pattern);

    return 0;
}

归并多个有序链表

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

list<int> mergelist(vector<list<int>> &lists)
{
    list<int> res;
    int n = lists.size();
    if (n == 0)
        return res;
    if (n == 1)
        return lists[0];

    // 最小查找，每次找到最小的元素，然后插入到结果链表中。
    while (true)
    {
        int min = INT_MAX;
        int min_index = -1;
        for (int i = 0; i < n; i++)
        {
            if (lists[i].empty())
                continue;
            if (lists[i].front() < min)
            {
                min = lists[i].front();
                min_index = i;
            }
        }
        if (min_index == -1)
            break;
        res.push_back(min);
        lists[min_index].pop_front();
    }
    return res;
}

// 最小堆归并
list<int> mergelist2(vector<list<int>> &lists)
{
    list<int> res;
    int n = lists.size();
    if (n == 0)
        return res;
    if (n == 1)
        return lists[0];

    // 建立最小堆，将每个链表的头节点插入堆中
    priority_queue<pair<int, list<int>::iterator>, vector<pair<int, list<int>::iterator>>,
                   greater<pair<int, list<int>::iterator>>>
        q;
    for (auto &lst : lists)
    {
        if (!lst.empty())
        {
            q.push(make_pair(lst.front(), lst.begin()));
        }
    }

    // 取出堆顶元素，将其加入结果链表中，并将其所在链表的下一个节点插入堆中
    while (!q.empty())
    {
        auto cur = q.top();
        q.pop();
        res.push_back(cur.first);
        auto it = cur.second;
        if (++it != it->get_list().end())
        {
            q.push(make_pair(*it, it));
        }
    }
    return res;
}
通用
总结 算法
本文由作者按照 CC BY 4.0 进行授权
最近更新

场景题集锦

秋招复盘7.18：算法、八股