算法题笔记

通过不断收敛区间来锁定一个边界，判断条件为 while (L < R)：

int B_Search(int A[], int L, int R, int x){
    int mid;
    while(L < R){                        // 缩小区间直到只有一个元素
        mid = (L + R) / 2;
        if (A[mid] >= x)	R = mid;     // 第一个符合条件的元素的下标在 L~mid
        else    L = mid + 1;             // 第一个符合条件的元素的下标在 mid+1~R
    }
    return L;                            // 可能成功也可能失败，需额外判断
}

↗ 区间最值

频繁查询区间最大/最小值时，提前维护前缀最值数组。

📌 例（P2-7）：给定数组 A，对于每个 j，定义 res[j] = A[0~j] 的最大值 × A[j]。如 A = {3, 1, 2, 7, 6}，则 res = {9, 3, 6, 49, 42}。

void ans(int A[], int n) {
    int res[n], B[n];
    B[0] = INT_MIN;
    for (int i = 0; i < n; i++)
        B[i] = max(B[i-1], A[i]);
    for (int j = 0; j < n; j++)
        res[j] = B[j] * A[j];
    // 输出 res 数组
}

情形三：单个无序顺序表

无序情况下的多指针法稍复杂，考频较低。主要用于 Partition（划分） 操作，实际上就是快速排序的一趟划分。

📌 例（P2-9）：含 n 个整数的数组 A，以 A[0] 为基准，划分使得左侧全小于 pivot，右侧全大于 pivot。A[0] 不一定是最终位置。如 A={2,5,3,-1,-2} 划分后可能为 {-2,-1,2,3,5} 或 {-1,-2,2,3,5} 等。

void ans(int A[], int n) {
    int i = 0, j = n - 1;
    int pivot = A[0];                // 选第一个元素为基准
    while (i < j) {
        while (i < j && A[j] >= pivot)  j--;   // A[j] < pivot 时停
        while (i < j && A[i] <= pivot)  i++;   // A[i] > pivot 时停
        if (i < j)  swap(A[i], A[j]);          // 交换逆序对
    }
    swap(A[0], A[i]);                // 基准归位
}

4. 遍历链表

若表中元素确定就用 for 循环，否则用 while 循环。遍历中访问指针 p 每次都要后移（p = p->next）。链表一般是带头结点的，因此从 L->next 开始。

Node* p = L->next;
for (int i = 0; i < n; i++) {
    visit(p);                       // 访问 p 结点
    p = p->next;
}

Node* p = L->next;
while (p != NULL) {
    visit(p);                       // 访问 p 结点
    p = p->next;
}

遍历同时还可以统计元素个数 n：

Node* p = L->next;
int n = 0;
while (p != NULL) {
    n++;
    visit(p);                       // 访问 p 结点
    p = p->next;
}

2. 散列表

和数组中一样，额外定义数组保存中间过程。如 count[n] 表示权值为 n 的元素出现次数。

例（P2-3）：n=6, A={1, 2, 5, 2, 4, 3}，用散列表找出重复元素。

// 链表版
void Hash_Linklist(Node* L) {
    int count[n] = {0};
    Node* p = L->next;
    while (p != NULL) {
        if (count[p->data] > 0)
            cout << p->data;         // 输出重复元素
        count[p->data]++;            // 记录 p->data 出现的次数
        p = p->next;
    }
}
// 顺序表版（对照）
void Hash_Sequence(int a[], int n) {
    int count[n] = {0};
    for (int i = 0; i < n; i++) {
        if (count[a[i]] > 0)
            cout << a[i];            // 输出重复元素
        count[a[i]]++;               // 记录 a[i] 出现的次数
    }
}