通用变量命名

变量类型变量名
索引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


涉及单链表插入问题，可以先给链表补一个空的头结点，以方便处理在头结点这前进行插入的情况。

涉及链表插入，原则一定是先补全待插入结点的指针域，再调整前后结点的指针域。


空间换时间的常用技巧：

  1. 记录出现次数或出现位置（哈希表可以看成是O(1)复杂度）
  2. 查表法（打表）

数组

  1. 前缀和
  2. 双指针
  3. map<int, int> count;

关于数组的数量级，一些比较微妙的点如下：

  1. num[i] <= 10^9，如果不涉及求和，则可以用int表示，如果涉及求和，则只能用long long
  2. num[i] <= 10^5，k <= 10^5，k表示数组成员个数，这里如果涉及求和，则结果就是刚好int溢出，所以只能用long long。

字符串

  1. 分隔字符串
  2. 统计单词数
  3. 回文

除前缀后，后缀后也是可以用的，比如：https://leetcode-cn.com/problems/shifting-letters/