版本比较
比较
标识
- 该行被添加。
- 该行被删除。
- 格式已经改变。
常用变量命名
变量类型 | 变量名 |
---|---|
索引 | index,idx |
数组 | arr,array |
左、中、右 | left,mid,right,l,m,r |
和、差、商、积 | sum、diff、quot(ient)、prod(uct) |
边的起点、终点、权值 | u、v、w |
图、队列、栈等命名 | 单大写字母,比如G、Q、S。 |
二分查找
代码块 |
---|
int binary_search(int a[], int n, int val) { int ret = -1; // 查找失败返回-1 int left = 0; int right = n - 1; int mid; while(left <= right) { mid = left + (right - left) / 2; // 防止直接平均可能的溢出问题 if(a[mid] < val) { left = mid + 1; } else if(a[mid] > val) { right = mid - 1; } else { // 相等情况放到最后,减少分支预测,因为多数搜索情况不是大于就是小于 ret = mid; break; } } return ret; } |
二维前缀和
代码块 |
---|
sum[x][y] = grid[x][y] + sum[x-1][y] + sum[x][y-1] - sum[x-1][y-1] area(x1,y1,x2,y2) = sum[x2][y2] - sum[x2][y1-1] - sum[x1-1][y2] + sum[x1-1][y1-1] |
邻接矩阵DFS & BFS
代码块 |
---|
#define MAXN 1005 int G[MAXN][MAXN]; // 邻接矩阵 int n; // 顶点数 bool visited[MAXN]; // 记录顶点是否已访问 void DFS_AM(int u) { cout << u << " "; visited[u] = true; for(int i = 0; i < n; i++) { if(G[u][i] && !visited[i]) { DFS_AM(i); } } } void BFS_AM(int u) { queue<int> Q; cout << u << " "; visited[u] = true; Q.push(u); while(!Q.empty()) { int v = Q.front(); Q.pop(); for(int i = 0; i < n; i++) { // 依次检查v的所有邻接点 if(G[v][i] && !visited[i]) { // v、i相邻且i未被访问 cout << i << " "; visited[i] = true; Q.push(i); } } } } |
邻接表DFS & BFS
代码块 |
---|
#define MAXN 1000
vector<int> G[MAXN]; // 邻接表
int n; // 顶点数
bool visited[MAXN]; // 记录顶点是否已访问
void DFS_AL(int u) {
cout << u << " ";
visited[u] = true;
for(auto &i : G[u]) {
if(!visited[i]) {
DFS_AL(i);
}
}
}
void BFS_AL(int u) { // 邻接表BFS,起点为u
queue<int> Q;
cout << u << " ";
visited[u] = true;
Q.push(u);
while(!Q.empty()) {
int v = Q.front();
Q.pop();
for(auto &i : G[v]) { // 依次检查v的所有邻接点
if(!visited[i]) {
cout << i << " ";
visited[i] = true;
Q.push(i);
}
}
}
} |
链表
反转单链表
代码块 |
---|
ListNode* reverseList(ListNode* head) { if(!head || !(head->next)) { return head; } ListNode *pre = head; ListNode *p = head->next; ListNode *next; while(p) { next = p->next; p->next = pre; pre = p; p = next; } head->next = nullptr; return pre; } |
二叉树
结点定义
递归遍历
非递归遍历
层次遍历
构建
使用递归收集与root距离为d的结点
代码块 |
---|
void collect(TreeNode *root, int d) { if(root == nullptr || d < 0) { return; } if(d == 0) { ans.push_back(root->val); } collect(root->left, d - 1); collect(root->right, d - 1); } |
目录 |
---|