常用变量命名

变量类型变量名
索引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(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);
            }
        }
    }
}