C++ 笔试常用算法模板

去年找工作时记录的一些常用模板（套路），实测能应付大多笔试或面试手撕题目。使用的前提是已经理解各类算法，仅做备忘和提示用。

关于面试手撕，一般以简单和中等难度题为主，大多都可以通过暴力求解，因为通常实在本地IDE或者其他Web IDE上手撕，没有LeetCode上那种时间或空间复杂度的限制。但是正是因为可以暴力求解，好的面试官会一步步引导或者提问有没有更优的解法（这时候即使忘了怎么写，但知道思路也比不知道好）、现有的复杂度是怎样的、是否考虑特殊情况或边界等等，算是了解基础的一个手段。
工作了后会发现，在面向工程的时候，的确需要精益求精来压榨算法的最大潜能，并且需要应对各种特殊情况（不要把用户想象得很聪明）。

一、二叉树遍历

DFS

void dfs(TreeNode* node) {
	if (!node) return;
	//相应的处理
	dfs(node->left);
	dfs(node->right);
}

如前序遍历：

class Solution {
public:
    void traversal(TreeNode* cur, vector<int>& vec) {
        if (cur == NULL) return;
        vec.push_back(cur->val);    // 中
        traversal(cur->left, vec);  // 左
        traversal(cur->right, vec); // 右
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }
};

BFS

void bfs(TreeNode* root) {
    queue <TreeNode*> q;
    q.push(root);
while (!q.empty()) {
    int currentLevelSize = q.size();
    for (int i = 1; i <= currentLevelSize; ++i) {
        auto node = q.front(); 
        q.pop();
        ret.back().push_back(node->val);
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    	}
	}
}

如层序遍历：

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        vector<vector<int>> result;
        while (!que.empty()) {
            int size = que.size();
            vector<int> vec;
            // 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                vec.push_back(node->val);
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            result.push_back(vec);
        }
        return result;
    }
};

二、回溯模板

适用场景用于解决暴力枚举的场景，例如枚举组合、排列等。

回溯三步：

1. 递归函数的返回值以及参数
2. 回溯函数终止条件
3. 单层搜索的过程

vector<vector<int>> res;

vector<int> path;
void dfs(参数) {
    if (满足递归结束) {
        res.push_back(path);
        return;
    }
    //递归方向
    for (xxx) {
        path.push_back(val);
        dfs();
        path.pop_back();
    }
}

或

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

如组合问题：

class Solution {
private:
    vector<vector<int>> result; // 存放符合条件结果的集合
    vector<int> path; // 用来存放符合条件结果
    void backtracking(int n, int k, int startIndex) {
        if (path.size() == k) {
            result.push_back(path);
            return;
        }
        for (int i = startIndex; i <= n; i++) {
            path.push_back(i); // 处理节点
            backtracking(n, k, i + 1); // 递归
            path.pop_back(); // 回溯，撤销处理的节点
        }
    }
public:
    vector<vector<int>> combine(int n, int k) {
        result.clear(); // 可以不写
        path.clear();   // 可以不写
        backtracking(n, k, 1);
        return result;
    }
};

三、动态规划

动规五步：

1. 确定dp数组的定义
2. dp数组的递推公式
3. dp数组如何初始化
4. dp数组遍历顺序
5. 举例推导dp数组

01背包

适用场景

给出若干个物品，每个物品具有一定的价值和价格，求解在限定的总额下可以获取的最大价值，注意，每个物品只能选取一次。

朴素版本

int n, C; //n个物品， C表示背包容量
int v[],  w[]; //v[i]表示第i个物品的价格/体积    w[i]表示第i个物品的价值
int dp[n+1][C+1]; //容器规模
//初始化 dp[0][j] j∈[0,C]
for (int i = 1 ; i <= n ; i++) {
    for (int j = 0 ; j <= C ; j++) {
        if (j >= v[i - 1]) dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i-1]] + w[i - 1]);
        else dp[i][j] = dp[i - 1][j];
    }
}
return dp[n][C];

先遍历物品，然后遍历背包重量的代码。

// weight数组的大小 就是物品个数
for(int i = 1; i < weight.size(); i++) { // 遍历物品
    for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
        if (j < weight[i]) dp[i][j] = dp[i - 1][j];
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

    }
}

滚动数组优化

int n, C; //n个物品， C表示背包容量
int v[],  w[]; //v[i]表示第i个物品的价格/体积    w[i]表示第i个物品的价值
int dp[C+1]; //容器规模
//初始化 dp[j] j∈[0,C]
for (int i = 1 ; i <= n ; i++) {
    for (int j = C ; j >=  v[i - 1] ; j--) {
        dp[j] = max(dp[j], dp[j-v[i-1]] + w[i - 1]);
    }
}
return dp[C];

一维dp数组遍历顺序

for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

    }
}

完全背包

适用场景

给出若干个物品，每个物品具有一定的价值和价格，求解在限定的总额下可以获取的最大价值，注意，每个物品不限制选取次数。

朴素版本和滚动数组优化的区别主要在于空间复杂度上，时间复杂度差不多，所以笔试的时候基本上没差别（空间很少会被卡）。

朴素版本

int n, C; //n个物品， C表示背包容量
int v[],  w[]; //v[i]表示第i个物品的价格/体积    w[i]表示第i个物品的价值
int dp[n + 1][C + 1]; //容器规模
//初始化 dp[0][j] j∈[0,C]
for (int i = 1 ; i <= n ; i++) {
    for (int j = 0 ; j <= C ; j++) {
        if (j >= v[i - 1]) dp[i][j] = max(dp[i-1][j], dp[i][j-v[i-1]] + w[i - 1]);
        else dp[i][j] = dp[i - 1][j];
    }
}
return dp[n][C];

滚动数组优化

int n, C; //n个物品， C表示背包容量
int v[],  w[]; //v[i]表示第i个物品的价格/体积    w[i]表示第i个物品的价值
int dp[C+1]; //容器规模
//初始化 dp[j] j∈[0,C]
for (int i = 1 ; i <= n ; i++) {
    for (int j = v[i-1] ; j <= C ; j++) {
        dp[j] = max(dp[j], dp[j-v[i-1]] + w[i - 1]);
    }
}
return dp[C];

最长递增子序列

适用场景

给定一个数组，求数组最长上升子序列的长度。

朴素版本可以求解的数据规模约为 1000。如果题目数据给到了10000或者更大，需要使用贪心+二分进行优化。

朴素版本

int lengthOfLIS(vector<int>& nums) {
    int dp[nums.size()];
    int ans = 1;
    dp[0] = 1;
    for (int i = 1 ; i < nums.size() ; i++) {
        dp[i] = 1;
        for (int j = 0 ; j < i ; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = max(dp[j] + 1, dp[i]);
            }
        }
        ans = max(ans, dp[i]);
    }
    return ans;
}

贪心+二分优化

int lengthOfLIS(vector<int>& nums) {
   vector<int> ls;
   for (int num : nums) {
       auto it = lower_bound(ls.begin(), ls.end(), num);
       if (it == ls.end()) ls.push_back(num);
       else *it = num;
    }
    return ls.size();
}

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if (nums.size() <= 1) return nums.size();
        vector<int> dp(nums.size(), 1);
        int result = 0;
        for (int i = 1; i < nums.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
            }
            if (dp[i] > result) result = dp[i]; // 取长的子序列
        }
        return result;
    }
};

最长公共子序列

适用场景

求两个数组或者字符的最长公共的子序列的长度。时间复杂度为O(n^2)

int longestCommonSubsequence(string text1, string text2) {
    int len1 = text1.size(), len2 = text2.size();
    vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));
    for (int i = 1 ; i <= len1 ; i++) {
        for (int j = 1 ; j <= len2 ;j++) {
            if (text1[i - 1] == text2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[len1][len2];
}

最长回文子串

适用场景

求解一个数组/字符串的最长回文子串的长度，时间复杂度为O(n^2)。

int longestPalindrome(string s) {
    int n = s.size();
    bool dp[n][n];
    int  mxlen = -1;
    for (int j = 0 ; j < n ; j++) {
        for (int i = j ; i >= 0 ; i--) {
            if (i == j) dp[i][j] = true;
            else if (i + 1 == j) dp[i][j] = s[i] == s[j];
            else {
                dp[i][j] = s[i] == s[j] && dp[i + 1][j - 1];
            }
            if (dp[i][j] && j - i + 1 > mxlen) {
                mxlen = j - i + 1;
            }
        }
    }
    return mxlen;
}

四、图

建图

建图的方式一般有两种，邻接矩阵和邻接表；

1.邻接矩阵，适用于稠密图【边的数量远大于点】

2.邻接表，适用于稀疏图【点的数量远大于边】

邻接矩阵

int graph[n][n];
for (int i = 0 ; i < m ; i++) {
	int a,b,w; //a和b存在一条边，权重为w
	cin >> a >> b >> w;
	graph[a][b] = graph[b][a] = w; // 如果是有向图则不需要建立双向边
}

邻接表

vector<vector<pair<int,int>>> graph(n, vector<int>(0));
for (int i = 0 ; i < m ; i++) {
    int a,b,w; //a和b存在一条边，权重为w
    graph[a].push_back({b,w});
    graph[b].push_back({a,w});  // 如果是有向图则不需要建立双向边
}

图的遍历

DFS

vector<vector<pair<int,int>> graph;
vector<bool> vst;
void dfs(int node) {
	for (auto p: graph[node]) {
        int next = p.first, weight = p.second;
        if (!vst[next]) {
            vst[next] = true;
            dfs(next);
            // 如果需要回溯的话 , vst[next] = false;
        }
    }
}

BFS

vector<vector<pair<int,int>> graph;
vector<bool> vst;
void bfs() {
	queue<int> q;
    q.push(start);
    vst[start] = true;
    while (!q.size()) {
        int node = q.front();q.pop();
        for (int p : graph[node]) {
            int next = p.first, weight = p.second;
            if (!vst[next]) {
                vst[next] = true;
                q.push_back(next);
            }
        }
    }
}

岛屿最大面积

// 版本一
class Solution {
private:
    int count;
    int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
    void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {
        for (int i = 0; i < 4; i++) {
            int nextx = x + dir[i][0];
            int nexty = y + dir[i][1];
            if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // 越界了，直接跳过
            if (!visited[nextx][nexty] && grid[nextx][nexty] == 1) { // 没有访问过的 同时 是陆地的

                visited[nextx][nexty] = true;   // 标记访问
                count++;                        // 面积加一
                dfs(grid, visited, nextx, nexty);   //继续进行dfs
            }
        }
    }

public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();  //m行n列
        vector<vector<bool>> visited = vector<vector<bool>>(m, vector<bool>(n, false)); // m行n列的访问矩阵，默认为false

        int result = 0; //最大岛屿面积
        for (int i = 0; i < m; i++) {   
            for (int j = 0; j < n; j++) {   //两层循环遍历矩阵内每个元素
                if (!visited[i][j] && grid[i][j] == 1) {    // 如果该区域没有被访问过，且是陆地
                    count = 1;  // 统计陆地的面积，因为dfs处理下一个节点，所以这里遇到陆地了就先计数，dfs处理接下来的相邻陆地
                    visited[i][j] = true;
                    dfs(grid, visited, i, j); // 将与其链接的陆地都标记上 true
                    result = max(result, count);    //求的是最大面积
                }
            }
        }
        return result;
    }
};

拓扑排序

适用场景

求解有向图的拓扑序、有向图判断是否成环。

vector<vector<int> graph;
vector<int> indegre; //存储每个节点的入度
queue<int> q;
for (int i = 0 ; i < n ; i++) {
    if (indegre[i] == 0)q.push(i);
}

while(!q.size()) {
    int node = q.front(); q.pop();
    for (int next : graph[node]) {
        indegre[next]--;
        if (indegre[next] == 0) q.push(next);
    }
}

并查集

适用场景

用于解决 连通性问题。比如a和b相邻，b和c相邻，可以判断出a和c相邻。

class UF
{
private:
	vector<int> father;

public:
	UF(int n)
	{
        // 初始化
		for (int i = 0; i < n; i++)
		{
			father.push_back(i);
		}
	}

	int find(int x)
	{
        // 当节点的父节点是它本身时，说明找到了根节点
		if (father[x]!=x)
		{
			father[x]=find(father[x]);
		}
		return father[x];
	}

	void join(int x, int y)
	{
		father[find(x)] = find(y);
	}

	bool isConnected(int x, int y)
	{
		return father[find(x)] == find(y);
	}

};

最小生成树

适用场景

连接无向图中所有的节点的最小费用。

常见的算法有2种：

1. kruskal：稀疏图，时间复杂度是$O(mlogm)$。
2. prim：稠密图，时间复杂度是$O(n^2)$。

n是点的数量，m是边的数量

Kruskal

int N = 1e5; //点的数量
int fa[N];

void init(int n) {
	for (int i = 0;i < n ; i++) fa[i] = i;
}

//找到x的根节点
int find(int x) {
    return x == fa[x] ? x : (fa[x] = find(fa[x]));
}

//合并两个节点
void union(int x, int y) {
    fa[find(x)] = find(y);
}

int kruskal(vector<vector<int>>& edges, int n, int m) {
	// edges[i] = {a,b,w} 表示a和b之间存在有一条边，权重为w
    init(n);
    sort(edges.begin(), edges.end(), [](const vector<int>& a, const vector<int>& b){return a[2]<b[2];});
    int ans = 0;
    for (auto arr : edges) {
        int a = arr[0], b = arr[1], w = arr[2];
        if (find(a) != find(b)) {
            union(a,b);
            ans += w;
        }
    }
    return ans;
}

prim

int prim(vector<vector<int>>& graph, int n) {
    vector<int> dis(n,INT_MAX);
    vector<bool> vst(n, false);
    int res = 0;
    for (int i = 0 ; i < n ; i++) {
        int min_index = -1;
        for (int j = 0 ; j < n ; j++) {
            if (!vst[j] && (min_index == -1 || dis[min_index] > dis[j]) min_index = j;
        }
        if (i != 0) res += dis[min_index];
        vst[min_index] = true;
        for (int j = 0 ; j < n ; j++) dis[j] = min(dis[j], graph[min_index][j]);
    }
    return res;
}

最短路径

适用场景

如果图中的节点的不存在边权（边权均为1），那么直接BFS即可求出最短路。

BFS

// 返回从st到达target的最短路径
int bfs(int st, int target, int n, vector<vector<int>>& graph) {
	queue<int> q;
	vector<bool> vst(n, false);
    q.push(st);
    vst[st] = true;
    int cnt = 0
    while (!q.size()) {
        int size = q.size();
        while(size--) {
            int node = q.front();q.pop();
	        if (node == target) return cnt;
            for (int next: graph[node]) {
                if (vst[next]) continue;
                vst[next] = true;
                q.push(next);
            }
        }
        cnt++;
    }
    return -1;
}

迪杰斯特拉 Dijkstra

朴素版本

//求st为起点的最短路
//graph[i][j]: i到j的距离，不存在则初始化成最大值
//n表示节点的数量
void dijkstra(int st, int n, vector<vector<int>>& graph) {
    vector<int> dis(n, INT_MAX);
    vector<bool> vst(n, false);
    dis[st] = 0;
    for (int i = 0 ; i < n ; i++) {
		int x = -1;
		for (int j = 0 ; j < n ; j++) {
			if (!vst[j] && (x == -1 || dis[j] < dis[x])) x=j;
		}
		vst[x] = true;
		for (int j = 0 ; j < n ; j++) {
			dis[j] = min(dis[j], dis[x] + graph[x][j]);
		}
	}
}

堆优化版本

void dijkstra(int st, int n, vector<vector<pair<int,int>>>& graph) {
    vector<int> dis(n, INT_MAX);
    vector<bool> vst(n, false);
    dis[st] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq; 
    pq.push({0, st});
    while (!pq.size()) {
        int d = pq.top().first();
        int u = pq.top().second();
        pq.pop();
        if (vst[u]) continue;
        vist[u] = true;
        for (auto [v,w] : graph[u]) {
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                pq.push({dis[v], v});
            }
        }
    }
}

弗洛伊德 Floyd-Warshall

适用场景

多源最短路，可以在$O(n^3)$的时间内求出任意两个点的最短距离。

vector<vector<int>> dp;
for (int i = 0 ; i < n ; i++) {
    for (int j = 0 ; j < n ; j++) {
        dp[i][j] = graph[i][j];
    }
}

for (int k = 0 ; k < n ; k++) {
    for (int i = 0 ; i < n ; i++) {
        for (int j = 0 ; j < n ; j++) {
            dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j]);
        }
    }
}

五、数组\区间

前缀和

适用场景

多次求区间和。$O(n)$的时间预处理出前缀和数组后，可以$O(1)$求出区间的和。不支持区间修改。

vector<int> nums;
int n;

vector<int> pre_sum(n + 1, 0);

for (int i = 1 ; i <= n ; i++ ) pre_sum[i] = pre_sum[i-1] +nums[i-1];

//查询区间和[left, right], 其中left，right是下标。
int sum = pre_sum[right+1] - pre_sum[left];

二维前缀和

vector<vector<int>> matrix;
int m = matrix.size(), n = matrix[0].size();
vector<vector<int>> pre(m + 1, vector<int>(n + 1));
for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
        pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + matrix[i - 1][j - 1];
    }
}

# 查询子矩阵的和 [x1,y1] [x2,y2]表示子矩阵的左上和右下两个顶点
int sum = pre[x2 + 1][y2 + 1] - pre[x1][y2 + 1] - pre[x2 + 1][y1] + pre[x1][y1];

差分

适用场景

给定一个数组和多次区间修改的操作，求修改后的数组。

int diff[10001];

void update(int l, int r, int val) {
	diff[l] += v;
    if (r+1 <n) diff[r+1] -= v;
}

int main() {
    int nums[] = {1,3,2,4,5};
    int n = sizeof(nums) / sizeof(int);
    diff[0] = nums[0];
    for(int i = 1; i < n; i++) diff[i] = nums[i] - nums[i - 1];

    //多次调用update后，对diff数组求前缀和可以得出 多次修改后的数组
    
	int* res = new int[n]; //修改后的数组
    res[0] = diff[0];
    for (int i=1 ; i<=n ; i++) res[i] += res[i-1] + diff[i];
}

二维差分

vector<vector<int>> matrix; //原数组

int n, m ; //长宽

vector<vector<int>> diff(n+1, vector<int>(m+1, 0));

void insert(int x1, int y1, int x2, int y2, int d) {
	diff[x1][y1] += d;
	diff[x2+1][y1] -= d;
	diff[x1][y2+1] -= d;
	diff[x2+1][y2+1] += d;
}

for (int i = 1 ; i <= n ; i++ ) {
	for (int j = 1 ; j <= m ; j++) {
		insert(i,j,i,j,matrix[i][j]);
	}
}

int q; //修改次数
cin >> q;
while (q--) {
	int x1,y1,x2,y2,d;
	cin >> x1 >> y1 >> x2 >> y2 >> d;
	insert(x1,y1,x2,y2,d);
}

for (int i = 1 ; i <= n ; i++) {
	for (int j = 1 ; j <= m ; j++) {
		matrix[i][j] = matrix[i-1][j] + matrix[i][j-1] - matrix[i-1][j-1] + diff[i][j];
	}
}

// matrix就是复原后的数组

树状数组

适用场景

当我们进行 单点修改，然后进行区间 区间查询、单点查询的时候，适用树状数组可以在$O(logn)$的复杂度求解。

vector<int> tree(MAXN, 0); 

int lowbit(int x) {
	return x&(-x);
}
// 单点修改，第i个元素增加x
inline void update(int i, int x)
{
    for (int pos = i; pos < MAXN; pos += lowbit(pos))
        tree[pos] += x;
}
// 查询前n项和
inline int query(int n)
{
    int ans = 0;
    for (int pos = n; pos; pos -= lowbit(pos))
        ans += tree[pos];
    return ans;
}

// 查询区间[a,b]的和
inline int query(int a, int b)
{
    return query(b) - query(a - 1);
}

线段树

适用场景

当我们需要区间修改、区间查询、单点查询的时候，可以使用线段树，能够在$O(logn)$的复杂度下求解。

#define MAXN 100005
typedef long long ll;
ll n, m, A[MAXN], tree[MAXN * 4], mark[MAXN * 4]; // A原数组、 tree线段树数组、mark懒标记数组
inline void push_down(ll p, ll len)
{
    mark[p * 2] += mark[p];
    mark[p * 2 + 1] += mark[p];
    tree[p * 2] += mark[p] * (len - len / 2);
    tree[p * 2 + 1] += mark[p] * (len / 2);
    mark[p] = 0;
}
// 建树
void build(ll l = 1, ll r = n, ll p = 1)
{
    if (l == r)
        tree[p] = A[l];
    else
    {
        ll mid = (l + r) / 2;
        build(l, mid, p * 2);
        build(mid + 1, r, p * 2 + 1);
        tree[p] = tree[p * 2] + tree[p * 2 + 1];
    }
}
void update(ll l, ll r, ll d, ll p = 1, ll cl = 1, ll cr = n)
{
    if (cl > r || cr < l)
        return;
    else if (cl >= l && cr <= r)
    {
        tree[p] += (cr - cl + 1) * d;
        if (cr > cl)
            mark[p] += d;
    }
    else
    {
        ll mid = (cl + cr) / 2;
        push_down(p, cr - cl + 1);
        update(l, r, d, p * 2, cl, mid);
        update(l, r, d, p * 2 + 1, mid + 1, cr);
        tree[p] = tree[p * 2] + tree[p * 2 + 1];
    }
}
ll query(ll l, ll r, ll p = 1, ll cl = 1, ll cr = n)
{
    if (cl > r || cr < l)
        return 0;
    else if (cl >= l && cr <= r)
        return tree[p];
    else
    {
        ll mid = (cl + cr) / 2;
        push_down(p, cr - cl + 1);
        return query(l, r, p * 2, cl, mid) + query(l, r, p * 2 + 1, mid + 1, cr);
    }
}
/**
1.输入数组A，注意下标从[1,n]。
2.调用update(l,r,d)函数，这里的l和r并不是下标。
3.调用query(l,r) 这里的l和r并不是下标
*/

滑动窗口

适用场景

求解数组/字符串 满足某个约束的最长/最短 的子数组/子串。需要满足二段性才可以使用。

for (int l = 0, r = 0 ; r < n ; r++) {
	//如果右指针的元素加入到窗口内后，根据题目判断进行滑动左指针
	while (l <= r && check()) l++;
}

二分查找

适用场景

满足二段性的数列中，求某一个值的位置、大于某个值的最小值、小于某个值的最大值。时间复杂度为$O(logn)$。

// 区间划分为[l,mid] 和 [mid+1,r]，选择此模板
int bsec1(int l, int r)
{
    while (l < r)
    {
        int mid = (l + r)/2;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return r;
}

// 区间划分为[l,mid-1] 和 [mid,r]，选择此模板
int bsec2(int l, int r)
{
    while (l < r)
    {
        int mid = ( l + r + 1 ) /2;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return r;
}

单调栈

适用场景

求序列中下一个更大、更小的元素。时间复杂度$O(n)$。

stack<int> s;
for (int i = 0; i < n; ++i) {
    while (!s.empty() && nums[i] > nums[s.top()]) {
        int top = s.top();s.pop();
		 //此时说明 nums[top]的下一个更大的元素为nums[i]
    }
    s.push(i);
}

单调队列

适用场景

求解移动区间的最值问题。时间复杂度$O(n)$。

vector<int> res(nums.size() - k + 1); //存储长长度为k的每一个区间的最值
deque<int> queue;
for (int i = 0; i < nums.size(); i++) {
    if (!queue.empty() && i - k + 1 > queue.front()) queue.pop_front();
    while (!queue.empty() && nums[queue.back()] < nums[i]) queue.pop_back();
    queue.push_back(i);
    if (i >= k - 1) res[i - k + 1] = nums[queue.front()]; 
}
return res;

六、其他

求质数/素数

适用场景

筛法求质数，时间复杂度约为$O(n)$。

int cnt;
vector<int> primes;
bool st[N];
void get_primes(int n) {
    for (int i = 2 ; i <= n ; i++) {
        if (!st[i]) {
            primes.push_back(i);
            for (int j = i + i ; j <= n ; j += i) st[j] = true;
        }
    }
}

求约数

适用场景

根号N的时间复杂度下求出一个数字的所有约数。

vector<int> get_divisors(int n) {
    vector<int> res;
    for (int i = 1; i <= n / i ; i++) {
        if (n % i == 0) {
            res.push_back(i);
            if (i != n / i) res.push_back(n / i);
        }
    }
    sort(res.begin(), res.end());
    return res;
}

快速幂

适用场景

快速的求出x的y次方。时间复杂度$O(logn)$。

long long fast_pow(int x, int y, int mod) {
    long long res = 1;
    while (y > 0) {
        if (y % 2 == 1) {
            res = (long long)res * x % mod;
        }
        x = (long long)x * x % mod;
        y /= 2;
    }
    return res;
}

离散化

适用场景

当数据值比较大的时候，可以映射成更小的值。例如[101,99,200] 可以映射成[1,0,2]。

int A[MAXN], C[MAXN], L[MAXN]; //原数组为A
memcpy(C, A, sizeof(A)); // 复制原数组到C中
sort(C, C + n); // 数组排序
int l = unique(C, C + n) - C; // 去重
for (int i = 0; i < n; ++i)
    L[i] = lower_bound(C, C + l, A[i]) - C + 1; // 二分查找

优先队列

priority_queue<int, vector<int>, [](int a, int b) {return a>b;}; // 队列存储int类型比较
priority_queue<int, vector<vector<int>>, [](const vector<int>& a, const vector<int>& b) {return a[1]>b[1];}; // 队列存储vector类型，按照第二个元素进行排序

string 删除与分割

C++中要从string中删除所有某个特定字符, 可用如下代码

str.erase(std::remove(str.begin(), str.end(), 'a'), str.end());

字符串分割：

// 使用字符串分割
void Stringsplit(const string& str, const string& splits, vector<string>& res)
{
	if (str == "")		return;
	//在字符串末尾也加入分隔符，方便截取最后一段
	string strs = str + splits;
	size_t pos = strs.find(splits);
	int step = splits.size();	//记录分隔字符串的长度

	// 若找不到内容则字符串搜索函数返回 npos
	while (pos != strs.npos)
	{
		string temp = strs.substr(0, pos);
		if(temp.size()!=0)res.push_back(temp);
		//去掉已分割的字符串,在剩下的字符串中进行分割
		strs = strs.substr(pos + step, strs.size());
		pos = strs.find(splits);
	}
}

C++ 进制

C++中以四种进制进行输出

#include <iostream>
#include <bitset>
 
using namespace std;
 
int main()
{
    int a=64;
    cout<<(bitset<32>)a<<endl;//二进制32位输出
    cout<<oct<<a<<endl;//八进制
    cout<<dec<<a<<endl;//十进制
    cout<<hex<<a<<endl;//十六进制
    return 0;
}

vector计数

//记录与首元素相同的数字的个数，因为数组有序，并且最多出现4次，所以不用遍历所有区间
    int cnt = count(nums.begin(), nums.begin() + 4, nums[0]);
vector<int> nums_new(nums.begin() + 1,
                             nums.end());//去掉一个首元素（顺子的第一个）
nums_new.erase(find(nums_new.begin(), nums_new.end(),
                            nums[0] + 1));//去掉一个首元素+1（顺子的第二个）                          

vector逆序

reverse(ans.begin(),ans.end())
或
 {ans.rbegin(),ans.rend()}

vector二维数组排序

#include <iostream>
#include <vector>
#include <algorithm>

bool customSort(const std::vector<int>& a, const std::vector<int>& b) {
    if (a[0] < b[0]) {
        return true;  // 第一列升序排列
    } else if (a[0] > b[0]) {
        return false;
    } else {
        return a[1] > b[1];  // 第二列降序排列
    }
}

void sortTwoDimensionalArray(std::vector<std::vector<int>>& arr) {
    std::sort(arr.begin(), arr.end(), customSort);
}

可以打印下来，笔试前可以抱抱佛脚抢记一波。

话说现在GPT工具如此方便，简单中等题秒出答案，总感觉失去了考核的意义。就像开挂一样，在没有监管或监管不力的情况下，对于诚信者怎么不算是一种劣币驱逐良币呢。
现在这种情况，是不是某种程度上也在筛选会不会变通、会不会使用工具的候选人呢？求职者如过江之鲫，会有企业care公不公平吗?