算法设计题解题框架

// 模板：排序 + 双指针
qsort(a, n, sizeof(int), cmp);
int left = 0, right = n - 1;
while (left < right) {
    // 根据题意移动指针
    if (condition) left++;
    else right--;
}

int findMissMin(int a[], int n) {
    // 第一遍：把 [1,n] 范围外的元素置 0（不关心）
    for (int i = 0; i < n; i++)
        if (a[i] <= 0 || a[i] > n) a[i] = 0;
    // 第二遍：用下标 a[i]-1 处的符号标记 a[i] 出现过
    for (int i = 0; i < n; i++) {
        int v = abs(a[i]);
        if (v >= 1 && v <= n && a[v-1] > 0)
            a[v-1] = -a[v-1];
        // v==0 说明原来就是"不关心"值，跳过
    }
    // 第三遍：第一个正数位置就是答案
    for (int i = 0; i < n; i++)
        if (a[i] > 0) return i + 1;
    return n + 1;
}

void calMulMax(int A[], int res[], int n) {
    int maxVal = INT_MIN, minVal = INT_MAX;
    // 从右向左维护后缀最大值和最小值
    for (int i = n - 1; i >= 0; i--) {
        if (A[i] > maxVal) maxVal = A[i];
        if (A[i] < minVal) minVal = A[i];
        // 正数乘以最大值，负数乘以最小值
        res[i] = (A[i] >= 0) ? A[i] * maxVal : A[i] * minVal;
    }
}

int majority(int a[], int n) {
    int num = a[0], cnt = 1;
    // 第一遍：筛选候选元素（对消法）
    for (int i = 1; i < n; i++) {
        if (a[i] == num) cnt++;
        else if (--cnt == 0) { num = a[i]; cnt = 1; }
    }
    // 第二遍：验证候选元素是否真的超过半数
    int m = 0;
    for (int i = 0; i < n; i++) if (a[i] == num) m++;
    return (m > n / 2) ? num : -1;
}

// 三指针分别指向三个升序数组头部
// 每次移动三者中最小值对应的指针
// 因为移动最大值只会让距离更大
int i = 0, j = 0, k = 0;
while (i < n1 && j < n2 && k < n3) {
    int D = calc_D(S1[i], S2[j], S3[k]);
    ans = min(ans, D);
    int minVal = min(S1[i], min(S2[j], S3[k]));
    if (S1[i] == minVal) i++;
    else if (S2[j] == minVal) j++;
    else k++;
}

// 找中间结点（慢指针到中间时快指针到末尾）
NODE *slow = head->next, *fast = head->next;
while (fast != NULL && fast->next != NULL) {
    slow = slow->next;
    fast = fast->next->next;
}
// slow 此时指向中间结点

// 找倒数第 k 个（快指针先走 k 步）
NODE *p = head->next, *q = head->next;
for (int i = 0; i < k; i++) {
    if (p == NULL) return 0;  // k 超出链表长度
    p = p->next;
}
while (p != NULL) { p = p->next; q = q->next; }
// q 即为倒数第 k 个结点

// 将 start 及之后的链表原地逆置，返回新头
NODE *reverse(NODE *start) {
    NODE *prev = NULL, *cur = start;
    while (cur != NULL) {
        NODE *next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;  // 新头
}

NODE *p = headA, *q = headB;
while (p != q) {
    p = (p != NULL) ? p->next : headB;
    q = (q != NULL) ? q->next : headA;
}
return p;  // NULL（无公共结点）或公共结点

// 中序遍历框架
void inorder(BTNode *root) {
    if (!root) return;
    inorder(root->left);
    visit(root);       // 处理当前结点
    inorder(root->right);
}

// 用队列实现层序遍历
Queue Q; enqueue(Q, root);
while (!isEmpty(Q)) {
    BTNode *node = dequeue(Q);
    visit(node);
    if (node->left)  enqueue(Q, node->left);
    if (node->right) enqueue(Q, node->right);
}

// DFS（邻接矩阵）
int visited[MAXV] = {0};
void DFS(MGraph G, int v) {
    visited[v] = 1;
    visit(v);
    for (int w = 0; w < G.numVertices; w++)
        if (G.Edge[v][w] && !visited[w])
            DFS(G, w);
}

// BFS（邻接矩阵）
void BFS(MGraph G, int v) {
    int visited[MAXV] = {0};
    Queue Q; enqueue(Q, v); visited[v] = 1;
    while (!isEmpty(Q)) {
        int u = dequeue(Q); visit(u);
        for (int w = 0; w < G.numVertices; w++)
            if (G.Edge[u][w] && !visited[w]) {
                visited[w] = 1; enqueue(Q, w);
            }
    }
}

// 基于入度数组的拓扑排序
int indegree[MAXV] = {0};
// 初始化入度...
Queue Q;
for (int v = 0; v < n; v++)
    if (indegree[v] == 0) enqueue(Q, v);
int count = 0;
while (!isEmpty(Q)) {
    int u = dequeue(Q); count++;
    for each neighbor w of u:
        if (--indegree[w] == 0) enqueue(Q, w);
}
return (count == n);  // true 说明无环

// 邻接矩阵中，第 v 行非零元素个数即为 v 的度
int degree(MGraph G, int v) {
    int d = 0;
    for (int w = 0; w < G.numVertices; w++)
        d += (G.Edge[v][w] != 0);
    return d;
}

// 关键变量含义要注释，e.g.
int cnt = 1;   // 候选主元素的"计数器"，cnt>0 时 num 为候选

// 循环不变量要注释，e.g.
// 循环结束后，a[0..i-1] 中所有正整数已被标记

// 非显然的下标计算要注释，e.g.
a[v-1] = -a[v-1];  // 用 v-1 位置的符号记录"v 出现过"