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;
}
};
二、回溯模板
适用场景用于解决暴力枚举的场景，例如枚举组合、排列等。
回溯三步：
- 递归函数的返回值以及参数
- 回溯函数终止条件
- 单层搜索的过程
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;
}
};
三、动态规划
动规五步：
- 确定dp数组的定义
- dp数组的递推公式
- dp数组如何初始化
- dp数组遍历顺序
- 举例推导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种：
- kruskal：稀疏图，时间复杂度是 O ( m l o g m ) O(mlogm) O(mlogm)。
- prim：稠密图，时间复杂度是 O ( n 2 ) O(n^2) O(n2)。
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 ) O(n^3) O(n3)的时间内求出任意两个点的最短距离。
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(n) O(n)的时间预处理出前缀和数组后，可以 O ( 1 ) O(1) 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 ( l o g n ) O(logn) 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 ( l o g n ) O(logn) 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 ( l o g n ) O(logn) 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 ) O(n) 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 ) O(n) 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 ) O(n) 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 ( l o g n ) O(logn) 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);
}
可以打印下来，笔试前可以抱抱佛脚抢记一波。
标签：return,nums,int,笔试,C++,vector,模板,dp,size From： https://blog.csdn.net/m0_50910915/article/details/132836590话说现在GPT工具如此方便，简单中等题秒出答案，总感觉失去了考核的意义。就像开挂一样，在没有监管或监管不力的情况下，对于诚信者怎么不算是一种劣币驱逐良币呢。
现在这种情况，是不是某种程度上也在筛选会不会变通、会不会使用工具的候选人呢？求职者如过江之鲫，会有企业care公不公平吗?