版本比较
比较
标识
- 该行被添加。
- 该行被删除。
- 格式已经改变。
通用变量命名
变量类型 | 变量名 |
---|---|
索引 | index,idx |
数组 | arr,array |
左、中、右 | left,mid,right,l,m,r |
和、差、商、积 | sum、diff、quot(ient)、prod(uct) |
二分查找
代码块 |
---|
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;
} |
邻接矩阵DFS代码模板
代码块 |
---|
vector<vector<int>> visited;
void dfs(vector<vector<int>> &grid, 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++) { // 遍历上下左右邻接点
int tx = x + dx[i];
int ty = y + dy[i];
if(tx < 0 || ty < 0 || tx >= grid.size() || ty >= grid[0].size() || visited[tx][ty]) {
continue; // 出界或已访问过
} else {
dfs(grid, tx, ty);
}
}
} |
邻接表BFS代码模板TODO
代码块 |
---|
vector<int> visited;
void bfs(vector<vector<int>> &graph, int start) {
queue<int> q;
q.push(start);
visited[start] = 1;
while(!q.empty()) {
int size = q.size();
while(size-- > 0) {
int cur = q.front(); q.pop();
visited[cur] = 1;
for(auto next : graph[cur]) {
if(!visited[next]) {
q.push(next);
visited[next] = 1;
}
}
}
}
} |
数组元素循环右移n个元素的方法:
先反转开头的n个元素,再反转剩下的元素,再反转整个数组。
对一维数组vector进行首尾填充:
代码块 |
---|
vector<int> nums = {1,2,3,4};
nums.insert(nums.begin(), 0);
nums.push_back(5); |
二叉树的中序遍历,一定是将所有结点按从小到大的顺序输出。
使用递归收集与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);
} |
翻转链表:
代码块 |
---|
list* reverse(list *head)
{
if(!head || !(head->next))
return head;
list *pre = head;
list *p = head->next;
list *next = NULL;
while(p)
{
next = p->next;
p->next = pre;
pre = p;
p = next;
}
head->next = NULL;
return pre;
} |
给定一个数组nums,求nums的所有排列组合,不能重复。
构造并查集时如果没有直接提供整数型编号,比如对一堆字符串建立并查集,可以先将每个字符串映射成唯一的数字,使用map<string, int>配合自增来实现。
对坐标点进行顺时针排序,参考:https://stackoverflow.com/questions/6989100/sort-points-in-clockwise-order
涉及单链表插入问题,可以先给链表补一个空的头结点,以方便处理在头结点这前进行插入的情况。
涉及链表插入,原则一定是先补全待插入结点的指针域,再调整前后结点的指针域。
空间换时间的常用技巧:
- 记录出现次数或出现位置(哈希表可以看成是O(1)复杂度)
- 查表法(打表)
数组
- 前缀和
- 双指针
- map<int, int> count;
关于数组的数量级,一些比较微妙的点如下:
- num[i] <= 10^9,如果不涉及求和,则可以用int表示,如果涉及求和,则只能用long long
- num[i] <= 10^5,k <= 10^5,k表示数组成员个数,这里如果涉及求和,则结果就是刚好int溢出,所以只能用long long。
字符串
- 分隔字符串
- 统计单词数
- 回文
除前缀后,后缀后也是可以用的,比如:https://leetcode-cn.com/problems/shifting-letters/
目录 |
---|