版本比较
比较
标识
- 该行被添加。
- 该行被删除。
- 格式已经改变。
常用变量命名
变量类型 | 变量名 |
---|---|
索引 | 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) {
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);
}
}
}
} |
网格图的DFS
代码块 |
---|
vector<vector<int>> grid;
vector<vector<int>> visited;
void dfs( |
邻接矩阵的DFS遍历代码模板:
...
int x, int y) {
static int dx[] = {-1, 0, 1, 0};
static int dy[] = {0, 1, 0, -1};
|
...
visited[x][y] = |
...
true; // 标记已访问 for(int i = 0; i < 4; i++) { // 对上下左右四个邻接点进行递归dfs int tx = x + dx[i]; int ty = y + dy[i]; if(tx < 0 || ty < 0 || tx >= grid.size() || ty >= grid[0].size() || visited[x][y]) { continue; // |
...
出界或已访问过
} else {
dfs(tx, ty);
}
}
} |
链表
链表定义
代码块 |
---|
// 单向链表
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
// 双向链表
struct Node {
int val;
Node *prev;
Node *next;
}; |
反转单链表
代码块 |
---|
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;
} |
二叉树
结点定义
代码块 |
---|
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
}; |
构建
代码块 |
---|
// 从数组v的cur位置开始构建二叉树
// 数组v代表对应的满二叉树的层次遍历结果,节点编号从0开始,如果某个结点为空,则用'#'填充
TreeNode* createTree(vector<int> &v, int cur) {
if(v[cur] == '#') return nullptr;
TreeNode *root = new TreeNode(v[cur]);
int left = cur * 2 + 1; // 满二叉树层次遍历,节点i的左孩子编号必为2i+1
int right = cur * 2 + 2; // 右孩子的编号为2i+2
if(left <= v.size() - 1) {
root->left = createTree(v, left);
} else {
root->left = nullptr;
}
if(right <= v.size() - 1) {
root->right = createTree(v, right);
} else {
root->right = nullptr;
}
return root;
} |
递归遍历
代码块 |
---|
void preorder(TreeNode *root) {
if(!root) return;
cout << root->val << " ";
preorder(root->left);
preorder(root->right);
}
void inorder(TreeNode *root) {
if(!root) return;
preorder(root->left);
cout << root->val << " ";
preorder(root->right);
}
void postorder(TreeNode *root) {
if(!root) return;
preorder(root->left);
preorder(root->right);
cout << root->val << " ";
} |
非递归遍历
代码块 |
---|
void preorder(TreeNode *root) {
stack<TreeNode*> stk;
TreeNode *cur = root;
while(cur || !stk.empty()) {
while(cur) {
cout << cur->val << " ";
stk.push(cur);
cur = cur->left;
}
cur = stk.top();
stk.pop();
cur = cur->right;
}
}
void inorder(TreeNode *root) {
stack<TreeNode*> stk;
TreeNode *cur = root;
while(cur || !stk.empty()) {
while(cur) {
stk.push(cur);
cur = cur->left;
}
cur = stk.top();
stk.pop();
cout << cur->val << " ";
cur = cur->right;
}
}
void postorder(TreeNode *root) {
stack<TreeNode*> stk;
TreeNode *cur = root;
TreeNode *prev = nullptr;
while(cur || !stk.empty()) {
while(cur) {
stk.push(cur);
cur = cur->left;
}
cur = stk.top();
if(cur->right && cur->right != prev) {
cur = cur->right;
} else {
stk.pop();
cout << cur->val << " ";
prev = cur;
cur = nullptr;
}
}
} |
层次遍历
代码块 |
---|
void levelorder(TreeNode *root) { if(!root) return; queue<TreeNode*> q; q.push(root); while(!q.empty()) { int size = q.size(); for(int i = 0; i < size; i++) { TreeNode *node = q.front(); q.pop(); cout << node->val << " "; if(node->left) { q.push(node->left); } if(node->right) { q.push(node->right); } } } } |
目录 |
---|