前言

这些是2020-2021刷题、面试积累的常见算法模板(不含dp)。大部分有对应的leetcode原题。

二分

二分模板大概有俩类，总计四个。

种类一

当我们将区间[l, r]划分成[l, mid]和[mid + 1, r]时，其更新操作是r = mid或者l = mid + 1;，计算mid时不需要加1。

左边界

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int left_bound(vector<int>& nums, int target) { // 找左边界
        int left = 0,right = nums.size() - 1,mid;
        while(left <= right) {
            mid = left + ((right - left) >> 1);
            if(nums[mid] == target) {
                right = mid - 1; // 右边向左边移动一位
            }else if(nums[mid] > target) {
                right = mid - 1;
            }else if(nums[mid] < target) {
                left = mid + 1;
            }
        }
        if(left >= nums.size() || nums[left] != target) return -1; // 判断是否满足条件(是否是错误退出)
        return left;
    }

右边界

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int right_bound(vector<int>& nums,int target) { // 找右边界
        int left = 0,right = nums.size() - 1,mid;
        while(left <= right) {
            mid = left + ((right - left) >> 1);
            if(nums[mid] == target) {
                left = mid + 1; // 左边向右移动一位
            }else if(nums[mid] > target) {
                right = mid - 1;
            }else if(nums[mid] < target) {
                left = mid + 1;
            }
        }
        if(right < 0 || nums[right] != target )  return -1; // 判断是否满足条件(是否是错误退出)
        return right;
    }

目标节点

1
2
3
4
5
6
7
8
9
10
11
12
13
int target_bound(vector<int>& nums,int target) { // 找目标元素
        int left = 0,right = nums.size() - 1,mid;
        while(left <= right) {
            mid = left + (right - left >> 1);
            if(nums[mid] == target) return mid; // 直接返回
            else if(nums[mid] > target) {
                right = mid - 1;
            }else if(nums[mid] < target) {
                left = mid + 1;
            }
        }
        return -1; //错误退出处理
    }

种类二

当我们将区间[l, r]划分成[l, mid - 1]和[mid, r]时，其更新操作是r = mid - 1或者l = mid;，此时为了防止死循环，计算mid时需要加1。

1
2
3
4
5
6
7
8
9
10
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

快排模版

yxc数组快排

1
2
3
4
5
6
7
8
9
10
void quick_sort(vector<int>&v,int l,int r){//快排模版
    if(l >= r)return;
    int i = l-1, j = r+1, x = v[(l+r) >> 1];
    while(i  < j){
        do j--;while(v[j] > x);
        do i++;while(v[i] < x);
        if(i  < j)swap(v[i], v[j]);
        else quick_sort(v, j+1, r),quick_sort(v, l, j);
    }
}

快排变种 / TOPK

快速选择算法

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
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) 
    {
        return findTopK(nums,0,nums.size() - 1,k);
    }
    int findTopK(vector<int>& nums,int l,int r,int k)
    {
        int index = partition(nums,l,r);
        if(index + 1 == k) return nums[index];
        if(index + 1 > k) return findTopK(nums,l,index - 1,k);
        else return findTopK(nums,index + 1,r,k);
    }
    int partition(vector<int>& nums,int l,int r)
    {
        int x = l + (r - l >> 1),i = l + 1,j = l;
        swap(nums[x],nums[l]);
        while(i <= r)
        {
            if(nums[i] >= nums[l]) swap(nums[++j],nums[i]);
            i++;
        }
        swap(nums[l],nums[j]);
        return j;
    }
};

归并模版

数组归并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
vector<int>q = {10,5,2,34,23,623,4123,8};
vector<int>res(q.size());

void msort(vector<int>& q,int l,int r){
    if(l>=r) return ;//当两个指针重合的时候就不用再排了
    int mid = (l+r) >> 1;
    msort(q,l,mid);//排序左半边
    msort(q,mid+1,r);//排序右半边
    int k = 0,i = l,j = mid + 1;//两个指针分别指向左半边和右半边的开头
    while(i <= mid && j <= r)
        if(q[i] <= q[j])    res[ k ++ ] = q[ i ++ ];
        else res[ k ++ ] = q[ j ++ ];
    while(i <= mid) res[ k ++ ] = q[ i ++ ];//把剩下的那一段放到res里面去
    while(j <= r) res[ k ++ ] = q[ j ++ ];
    i = l，k = 0;//再分别指向q和res的开头位置
    for(int i = l,k = 0; i <= r; i ++,k ++)  q[i] = res[k];
}

int main(){
    msort(q, 0, (int)q.size()-1);
    for(int i = 0; i < q.size(); i++)   cout<<q[i]<<"\t";cout<<endl;
    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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution { //lc 148
public:
    ListNode* sortList(ListNode* head) {
        if(!head || !head->next) return head;
        ListNode* mid = findMid(head);
        ListNode* left = sortList(head);
        ListNode* right = sortList(mid);
        return merge(left,right);
    }

    ListNode* findMid(ListNode* head)
    {
        ListNode* slow = head,*fast = head,*prev = nullptr;
        while(fast && fast->next)
        {   
            prev = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        prev->next = nullptr;
        return slow;
    }

    ListNode* merge(ListNode* l,ListNode* r)
    {
        ListNode dummy,*head = &dummy;
        while(l && r)
        {
            if(l->val < r->val) 
            {
                head->next = l;
                l = l->next;
            }
            else
            {
                head->next = r;
                r = r->next;
            }
            head = head->next;
        }
        if(l) head->next = l;
        if(r) head->next = r;
        return dummy.next;
    }
};

堆排序

小根堆

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

using namespace std;

class Heap//小堆
{
    vector<int> h;
    void down(int u)
    {
        int l = u * 2, r = u * 2 + 1,s = h.size(),t = u;
        if(l < s && h[l] < h[t])    t = l;
        if(r < s && h[r] < h[t])    t = r;
        swap(h[u],h[t]);
        if(t != u)  down(t);
    }

    void up(int u)
    {
        while(u / 2 && h[u] < h[u/2] )
        {
            swap(h[u/2],h[u]);
            u /= 2;
        }
    }
public:
    Heap()
    {
        h.push_back(0);
    }
    void add(const int& val)
    {
        h.push_back(val);
        up(h.size()-1);
    }
    int pop()
    {
        swap(h[1],h.back());
        int res = h.back();
        h.pop_back();
        down(1);
        return res;
    }
    int size()
    {
        return h.size();
    }
    bool empty()
    {
        return size() == 1;
    }

};

int main() {
    std::cout << "Hello, World!" << std::endl;
    Heap h;
    vector<int>nums{1,2,5,7,3,4,9,10,6,8};
    for(const auto& it : nums) h.add(it);
    while(!h.empty())
    {
        cout<<h.pop()<<"\t";
    }
    cout<<endl;
    return 0;
}

前缀和

1
2
3
4
5
6
7
8
9
10
11
for(int i=1 ; i<=n ; i++)
        s[i] = a[i] + s[i-1];

for(int i=1 ; i<=n ; i++)
        for(int j=1 ; j<=m ; j++)
            s[i][j] += s[i-1][j] + s[i][j-1] + a[i][j] - s[i-1][j-1];
//子矩阵(x1,y1)->(x2,y2)的和
int x1, x2, y1, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        printf("%d\n", s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]);

DFS(tree)

dfs其实还没有学完，因为其中记忆化搜索部分涉及到了DP暂时还没有学习，以下就讲解一些没有涉及到记忆化搜索到操作。

树的DFS

这也是最基础的DFS，需要掌握前中后这三种基础的递归方式，常规题就是求树的各种属性以及翻转之类的操作。由于比较简单，这里就不给出代码了。

之后是借助这三种迭代附加属性的变种题目，例如avl使用中序遍历求顺序，逆波兰表达式等等，也不是很难的题目。

再之后就是这三种遍历方式的迭代写法需要掌握，这有一点麻烦，下面给出相关的代码

先序迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        if(root == nullptr)return {};
        vector<int>res;
        stack<TreeNode*>sta;
        sta.push(root);
        while(!sta.empty()){
            auto tmp = sta.top();
            sta.pop();
            if(tmp) res.emplace_back(tmp->val);
            if(tmp->right) sta.push(tmp->right);
            if(tmp->left) sta.push(tmp->left);
        }
        return res;
    }
};

后续迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        if(root == nullptr)return{};
        stack<TreeNode*>sta;
        vector<int>res;
        sta.push(root);
        while(!sta.empty()){
            auto tmp = sta.top();
            sta.pop();
            if(tmp)res.push_back(tmp->val);
            if(tmp->left) sta.push(tmp->left);
            if(tmp->right)sta.push(tmp->right);
        }
        reverse(res.begin(),res.end());
        return res;
    }
};

注意这里后序遍历其实走的不是后序遍历，后序是左->右->中，这里采用的是另一种中->左->右的形式，之后再把他们reverse，至于为什么要这样写呢，自然为了三种遍历形式的写法统一啦。

中序迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int>res;
        stack<TreeNode*>sta;
        auto tmp = root;
        while(tmp || !sta.empty()){
            if(tmp){
                sta.push(tmp);
                tmp = tmp->left;
            }else{
                tmp = sta.top();
                sta.pop();
                res.push_back(tmp->val);
                tmp = tmp->right;
            }
        }
        return res;
    }
};

DFS + BFS(Graph)

常规操作就是使用一个vis数组来记录此节点是否遍历过，之后再根据此记录进行相关操作，这里地方大多数时候DFS和BFS是可以互换的，都能实现其目的。常规题有LC323无向图中连通分量的数目，LC684冗余链接，LC785判断二分图等，基本上检查连通图的题使用并查集比使用DFS和BFS要简单，建议使用并查集。

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
class Solution {
public:
    int cnt = 0;
    int countComponents(int n, vector<vector<int>>& edges) {
        vector<vector<int>>graph(n);
        vector<bool>vis(n,false);
        for(int i = 0; i < edges.size(); i++) {
            graph[edges[i][0]].push_back(edges[i][1]);
            graph[edges[i][1]].push_back(edges[i][0]);
        }
        for(int i = 0; i < n; i++) {
            //bfs(graph,vis,i);
            if(!vis[i]) {
                dfs(graph,vis,i);
                cnt++;
            }
        }
        return cnt;
    }
    void bfs(vector<vector<int>>&graph,vector<bool>&vis,int&index) {
        if(vis[index]) return;
        cnt++;
        queue<int>q{{index}};
        while(!q.empty()) {
            int now = q.front();q.pop();
            if(vis[now]) continue;
            vis[now] = true;
            for(auto it : graph[now]) q.push(it);
        }
    }
    void dfs(vector<vector<int>>&graph,vector<bool>&vis,int&index) {
        if(vis[index]) return;
        vis[index] = true;
        for(auto it : graph[index]) dfs(graph,vis,it);
    }
};

floyd

1
2
3
4
5
6
7
void floyd()// 算法结束后，d[a][b]表示a到b的最短距离
    {
        for (int k = 1; k <= n; k ++ )
            for (int i = 1; i <= n; i ++ )
                for (int j = 1; j <= n; j ++ )
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    }

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
int n;      // n表示点数
    int g[N][N];        // 邻接矩阵，存储所有边
    int dist[N];        // 存储其他点到当前最小生成树的距离
    bool st[N];     // 存储每个点是否已经在生成树中


    // 如果图不连通，则返回INF(值是0x3f3f3f3f), 否则返回最小生成树的树边权重之和
    int prim()
    {
        memset(dist, 0x3f, sizeof dist);

        int res = 0;
        for (int i = 0; i < n; i ++ )
        {
            int t = -1;
            for (int j = 1; j <= n; j ++ )
                if (!st[j] && (t == -1 || dist[t] > dist[j]))
                    t = j;

            if (i && dist[t] == INF) return INF;

            if (i) res += dist[t];
            st[t] = true;

            for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
        }

        return res;
    }

Kruskal

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
int n, m;       // n是点数，m是边数
    int p[N];       // 并查集的父节点数组

    struct Edge     // 存储边
    {
        int a, b, w;

        bool operator< (const Edge &W)const
        {
            return w < W.w;
        }
    }edges[M];

    int find(int x)     // 并查集核心操作
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    int kruskal()
    {
        sort(edges, edges + m);

        for (int i = 1; i <= n; i ++ ) p[i] = i;    // 初始化并查集

        int res = 0, cnt = 0;
        for (int i = 0; i < m; i ++ )
        {
            int a = edges[i].a, b = edges[i].b, w = edges[i].w;

            a = find(a), b = find(b);
            if (a != b)     // 如果两个连通块不连通，则将这两个连通块合并
            {
                p[a] = b;
                res += w;
                cnt ++ ;
            }
        }

        if (cnt < n - 1) return INF;
        return res;
    }

拓扑排序

求有向图中是否存在环

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
class Solution { // leetcode 1136
public:
    int minimumSemesters(int n, vector<vector<int>>& relations) {
        // 一个数组记录入度
        // 简历一个图[node,target]
        // queue记录入度为0的课程
        vector<int>degree(n+1,0); // 课程数量，入度
        vector<vector<int>>graph(n+1); // 链接矩阵
        queue<int>q; // 记录当前入度为0且未遍历的节点
        for(int i = 0; i < relations.size(); i++) { // 建立链接矩阵
            int node = relations[i][0],target = relations[i][1];
            graph[node].push_back(target); // 节点为node的位置指向的目标
            degree[target] ++; // 目标节点的入度 + 1
        }
        for(int i = 1; i < degree.size(); i++) 
            if(!degree[i]) q.push(i); // 入度为0的节点加入遍历队列
        int time = 0;
        while(!q.empty()) {
            int size = q.size();
            while(size -- ) { // 当前学期能修的课程数
                int now = q.front();q.pop();
                for(const int& it : graph[now]) { // 当前节点的链接节点入度 -1
                    degree[it] -- ;
                    //如果当前节点的入度为0说明该课程可以修
                    if(degree[it] == 0) q.push(it); 
                }
            }
            time++;
        }
        for(int i = 0; i < degree.size(); i++) 
            if(degree[i]) return -1;
        return time;
    }
};

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
class Solution { // leetcode743
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        using Pair = pair<int,int>;
        vector<vector<Pair>>graph(n+1);
        vector<int>vis(n+1,0);
        priority_queue<Pair,vector<Pair>,greater<Pair>>pq; // time node
        pq.push({0,k});
        for(int i = 0; i < times.size(); i++) {
            int node = times[i][0],next = times[i][1],time = times[i][2];
            graph[node].push_back({time,next});
        }
        int res = 0;
        while(!pq.empty()) {
            auto [time,node] = pq.top();pq.pop();
            if(vis[node]) continue;

            vis[node] = true;
            res = max(time,res);
            for(auto [nexttime,next] : graph[node]){
                
                if(vis[next] == false) {
                    pq.push({nexttime + time,next});
                }
            }
        }
        return count(begin(vis) + 1,end(vis),true) == n ? res : -1;
    }
};

SPFA

求最短路径，可以检查负权环，是bellman- fold的升级版。

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
class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        vector<int>dis(n+1,INT_MAX / 2),cnt(n+1,0); // time，当前节点入队情况
        vector<int>nodeInQueueNums(n+1,0);
        using Pair = pair<int,int>;
        vector<vector<Pair>> graph(n+1); // 链接矩阵
        for(const auto& it : times) {
            int node = it[0],next = it[1],time = it[2];
            graph[node].push_back({next,time});
        }
        dis[k] = 0; // 更新k到k的花费time
        cnt[k]++; // 入队标记
        nodeInQueueNums[k]++;
        queue<int>q{{k}}; // k入队
        while(!q.empty()) {
            int node = q.front();q.pop();
            cnt[node]--;
            for(const auto& it : graph[node]) {
                auto [next,time] = it;
                if(dis[next] > dis[node] + time) {
                    nodeInQueueNums[next]++;
                    dis[next] = dis[node] + time;
                    cnt[next]++;
                    q.push(next);
                    if(nodeInQueueNums[next] > n) return -1;//存在负权环
                }
            }
        }
        int res = *max_element(begin(dis) + 1,end(dis));
        return res == INT_MAX / 2 ? -1 : res;
    }
};

并查集

求无向联通量，是否存在冗余边等。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class UnionFind{
    vector<int>root;
    public:
    UnionFind(int size) :root(size) {
        for(int i = 0; i < size; i++) root[i] = i;
    }
    int find(int x) {
        return root[x] == x ? x : root[x] = find(root[x]);
    }
    void merge(int x,int y) {
        root[find(y)] = root[find(x)];
    }
    bool connect(int x,int y) {
        return find(x) == find(y);
    }
};

二分图染色

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
int n;      // n表示点数
  int h[N], e[M], ne[M], idx;     // 邻接表存储图
  int color[N];       // 表示每个点的颜色，-1表示为染色，0表示白色，1表示黑色

  // 参数：u表示当前节点，father表示当前节点的父节点（防止向树根遍历），c表示当前点的颜色
  bool dfs(int u, int father, int c)
  {
      color[u] = c;
      for (int i = h[u]; i != -1; i = ne[i])
      {
          int j = e[i];
          if (color[j] == -1)
          {
              if (!dfs(j, u, !c)) return false;
          }
          else if (color[j] == c) return false;
      }

      return true;
  }

  bool check()
  {
      memset(color, -1, sizeof color);
      bool flag = true;
      for (int i = 1; i <= n; i ++ )
          if (color[i] == -1)
              if (!dfs(i, -1, 0))
              {
                  flag = false;
                  break;
              }
      return flag;
  }