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存在一条边，权重为wcin >> 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存在一条边，权重为wgraph[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列的访问矩阵，默认为falseint 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); // 将与其链接的陆地都标记上 trueresult = 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之间存在有一条边，权重为winit(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 = 0while (!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();	//记录分隔字符串的长度// 若找不到内容则字符串搜索函数返回 nposwhile (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公不公平吗?