电子商务网站的整个建设流程,精密电子东莞网站建设技术支持,2015做那个网站致富,wordpress 站长主题C 笔试常用算法模板 一、二叉树遍历DFSBFS 二、回溯模板三、动态规划01背包朴素版本滚动数组优化 完全背包朴素版本滚动数组优化 最长递增子序列朴素版本贪心二分优化 最长公共子序列最长回文子串 四、图建图邻接矩阵邻接表 图的遍历DFSBFS 拓扑排序并查集最小生成树Kruskalpri… C 笔试常用算法模板 一、二叉树遍历DFSBFS 二、回溯模板三、动态规划01背包朴素版本滚动数组优化 完全背包朴素版本滚动数组优化 最长递增子序列朴素版本贪心二分优化 最长公共子序列最长回文子串 四、图建图邻接矩阵邻接表 图的遍历DFSBFS 拓扑排序并查集最小生成树Kruskalprim 最短路径BFS迪杰斯特拉 Dijkstra朴素版本堆优化版本 弗洛伊德 Floyd-Warshall 五、数组\区间前缀和二维前缀和差分二维差分树状数组线段树滑动窗口二分查找单调栈单调队列 六、其他求质数/素数求约数快速幂离散化优先队列string 删除与分割C 进制vector计数vector逆序vector二维数组排序 去年找工作时记录的一些常用模板套路实测能应付大多笔试或面试手撕题目。使用的前提是已经理解各类算法仅做备忘和提示用。 关于面试手撕一般以简单和中等难度题为主大多都可以通过暴力求解因为通常实在本地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, vectorint vec) {if (cur NULL) return;vec.push_back(cur-val); // 中traversal(cur-left, vec); // 左traversal(cur-right, vec); // 右}vectorint preorderTraversal(TreeNode* root) {vectorint 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:vectorvectorint levelOrder(TreeNode* root) {queueTreeNode* que;if (root ! NULL) que.push(root);vectorvectorint result;while (!que.empty()) {int size que.size();vectorint 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;}
};二、回溯模板
适用场景用于解决暴力枚举的场景例如枚举组合、排列等。
回溯三步
递归函数的返回值以及参数回溯函数终止条件单层搜索的过程
vectorvectorint res;vectorint 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:vectorvectorint result; // 存放符合条件结果的集合vectorint 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:vectorvectorint 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[n1][C1]; //容器规模
//初始化 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[C1]; //容器规模
//初始化 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[C1]; //容器规模
//初始化 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(vectorint 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(vectorint nums) {vectorint 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(vectorint nums) {if (nums.size() 1) return nums.size();vectorint 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();vectorvectorint dp(len1 1, vectorint(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; // 如果是有向图则不需要建立双向边
}邻接表
vectorvectorpairint,int graph(n, vectorint(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
vectorvectorpairint,int graph;
vectorbool 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
vectorvectorpairint,int graph;
vectorbool vst;
void bfs() {queueint 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(vectorvectorint grid, vectorvectorbool 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(vectorvectorint grid) {int m grid.size(), n grid[0].size(); //m行n列vectorvectorbool visited vectorvectorbool(m, vectorbool(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;}
};拓扑排序
适用场景
求解有向图的拓扑序、有向图判断是否成环。
vectorvectorint graph;
vectorint indegre; //存储每个节点的入度
queueint 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:vectorint 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(vectorvectorint edges, int n, int m) {// edges[i] {a,b,w} 表示a和b之间存在有一条边权重为winit(n);sort(edges.begin(), edges.end(), [](const vectorint a, const vectorint 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(vectorvectorint graph, int n) {vectorint dis(n,INT_MAX);vectorbool 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, vectorvectorint graph) {queueint q;vectorbool 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, vectorvectorint graph) {vectorint dis(n, INT_MAX);vectorbool 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])) xj;}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, vectorvectorpairint,int graph) {vectorint dis(n, INT_MAX);vectorbool vst(n, false);dis[st] 0;priority_queuepairint, int, vectorpairint, 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)的时间内求出任意两个点的最短距离。
vectorvectorint 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)求出区间的和。不支持区间修改。
vectorint nums;
int n;vectorint pre_sum(n 1, 0);for (int i 1 ; i n ; i ) pre_sum[i] pre_sum[i-1] nums[i-1];//查询区间和[left, right], 其中leftright是下标。
int sum pre_sum[right1] - pre_sum[left];二维前缀和
vectorvectorint matrix;
int m matrix.size(), n matrix[0].size();
vectorvectorint pre(m 1, vectorint(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 (r1 n) diff[r1] - 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 i1 ; in ; i) res[i] res[i-1] diff[i];
}二维差分
vectorvectorint matrix; //原数组int n, m ; //长宽vectorvectorint diff(n1, vectorint(m1, 0));void insert(int x1, int y1, int x2, int y2, int d) {diff[x1][y1] d;diff[x21][y1] - d;diff[x1][y21] - d;diff[x21][y21] 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)的复杂度求解。
vectorint 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] 和 [mid1,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)。
stackint 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)。
vectorint res(nums.size() - k 1); //存储长长度为k的每一个区间的最值
dequeint 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;
vectorint 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的时间复杂度下求出一个数字的所有约数。
vectorint get_divisors(int n) {vectorint 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_queueint, vectorint, [](int a, int b) {return ab;}; // 队列存储int类型比较
priority_queueint, vectorvectorint, [](const vectorint a, const vectorint 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, vectorstring 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 bitsetusing namespace std;int main()
{int a64;cout(bitset32)aendl;//二进制32位输出coutoctaendl;//八进制coutdecaendl;//十进制couthexaendl;//十六进制return 0;
}vector计数
//记录与首元素相同的数字的个数因为数组有序并且最多出现4次所以不用遍历所有区间int cnt count(nums.begin(), nums.begin() 4, nums[0]);
vectorint 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 algorithmbool customSort(const std::vectorint a, const std::vectorint 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::vectorstd::vectorint arr) {std::sort(arr.begin(), arr.end(), customSort);
}可以打印下来笔试前可以抱抱佛脚抢记一波。 话说现在GPT工具如此方便简单中等题秒出答案总感觉失去了考核的意义。就像开挂一样在没有监管或监管不力的情况下对于诚信者怎么不算是一种劣币驱逐良币呢。 现在这种情况是不是某种程度上也在筛选会不会变通、会不会使用工具的候选人呢求职者如过江之鲫会有企业care公不公平吗?
