做题版：[[algo/算法刷题日记基础篇]]

搜索与排序

搜索

Hello-algo

二分查找

二分查找基础

类型：分治

每轮缩小一半搜索范围，直至找到目标元素或搜索区间为空为止。

【模板】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int binarySearch(int *nums, int len, int target) {
    // 初始化双闭区间 [0, n-1] ，即 i, j 分别指向数组首元素、尾元素
    int i = 0, j = len - 1;
    // 循环，当搜索区间为空时跳出（当 i > j 时为空）
    while (i <= j) {
        int m = i + (j - i) / 2; // 计算中点索引 m
        if (nums[m] < target)    // 此情况说明 target 在区间 [m+1, j] 中
            i = m + 1;
        else if (nums[m] > target) // 此情况说明 target 在区间 [i, m-1] 中
            j = m - 1;
        else // 找到目标元素，返回其索引
            return m;
    }
    // 未找到目标元素，返回 -1
    return -1;
}

时间复杂度为 $O(log_n)$ ：在二分循环中，区间每轮缩小一半。

空间复杂度为 $O(1)$ ： 指针 i和 j 使用常数大小空间。

由于 i和 j 都是 int 类型，因此 i+j 可能会超出 int 类型的取值范围。为了避免大数越界，我们通常采用公式 $m=\lfloor i+(j-i)/2 \rfloor$ 来计算中点。

二分查找的四个基本要素|300

【局限】

  • 只限制于 有序 数组 才能使用
    • 不适合应用在链表或基于链表实现的数据结构。

二分查找的插入

搜索目标元素的插入位置

  1. 无重复元素插入

例如：给定一个长度为 n 的有序数组 nums 和一个元素 target ，数组不存在重复元素。现将 target 插入数组 nums 中，并保持其有序性。若数组中已存在元素 target ，则插入到其左方。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/* 二分查找插入点（无重复元素） */
int binarySearchInsertionSimple(int *nums, int numSize, int target) {
    int i = 0, j = numSize - 1; // 初始化双闭区间 [0, n-1]
    while (i <= j) {
        int m = i + (j - i) / 2; // 计算中点索引 m
        if (nums[m] < target) {
            i = m + 1; // target 在区间 [m+1, j] 中
        } else if (nums[m] > target) {
            j = m - 1; // target 在区间 [i, m-1] 中
        } else {
            return m; // 找到 target ，返回插入点 m
        }
    }
    // 未找到 target ，返回插入点 i
    return i;
}

题目要求将 target 插入到相等元素的左边，这意味着新插入的 target 替换了原来 target 的位置。也就是说，当数组包含 target 时，插入点的索引就是该 target 的索引。

当 nums[m] < target 时 i 移动，这意味着指针 i 在向大于等于 target 的元素靠近。同理，指针 j 始终在向小于等于 target 的元素靠近。

因此二分结束时一定有：i 指向首个大于 target 的元素，j 指向首个小于 target 的元素。易得当数组不包含 target 时，插入索引为 i 。

  1. 有重复元素插入

规定数组可能包含重复元素，其余不变。
数组中存在多个 target ，则普通二分查找只能返回其中一个 target 的索引

题目要求将目标元素插入到最左边，所以我们需要查找数组中最左一个 target 的索引

【思路一（暴力）】

  1. 执行二分查找，得到任意一个 target 的索引，记为 k 。
  2. 从索引 k开始，向左进行线性遍历，当找到最左边的 target 时返回。

【思路二（）】

  1. 当 nums[m] < target 或 nums[m] > target 时，说明还没有找到 target ，因此采用普通二分查找的缩小区间操作，从而使指针 i 和 j 向 target 靠近。
  2. 当 nums[m] == target 时，说明小于 target 的元素在区间 [i,m−1] 中，因此采用 m=j−1 来缩小区间，从而使指针 j 向小于 target 的元素靠近。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/* 二分查找插入点（存在重复元素） */
int binarySearchInsertion(int *nums, int numSize, int target) {
    int i = 0, j = numSize - 1; // 初始化双闭区间 [0, n-1]
    while (i <= j) {
        int m = i + (j - i) / 2; // 计算中点索引 m
        if (nums[m] < target) {
            i = m + 1; // target 在区间 [m+1, j] 中
        } else if (nums[m] > target) {
            j = m - 1; // target 在区间 [i, m-1] 中
        } else {
            j = m - 1; // 首个小于 target 的元素在区间 [i, m-1] 中
            /*此处有别！这里原本是找到了，但是找到的不是最左边的，所以往左移*/
        }
    }
    // 返回插入点 i
    return i;
}

二分边界查找

  1. 查找左边界

给定一个长度为 n的有序数组 nums ，其中可能包含重复元素。请返回数组中最左一个元素 target 的索引。若数组中不包含该元素，则返回 −1 。

数组中可能不包含 target ，这种情况可能导致以下两种结果。

  • 插入点的索引 i 越界。
  • 元素 nums[i] 与 target 不相等。
1
2
3
4
5
6
7
8
9
10
11
12
/* 二分查找最左一个 target */
int binarySearchLeftEdge(int *nums, int numSize, int target) {
    // 等价于查找 target 的插入点
    int i = binarySearchInsertion(nums, numSize, target);
    /*此函数见上面代码binarySearchInsertion*/
    // 未找到 target ，返回 -1
    if (i == numSize || nums[i] != target) {
        return -1;
    }
    // 找到 target ，返回索引 i
    return i;
}
  1. 查找右边界
1
2
3
4
5
6
7
8
9
10
11
12
/* 二分查找最左一个 target */
int binarySearchRightEdge(int *nums, int numSize, int target) {
    // 等价于查找 target 的插入点
    int i = binarySearchInsertionRight(nums, numSize, target);
    /*此函数见上面代码binarySearchInsertion，并把`nums[m] == target` 情况下的指针i收缩操作（=m+1）。*/
    // 未找到 target ，返回 -1
    if (i == numSize || nums[i] != target) {
        return -1;
    }
    // 找到 target ，返回索引 i
    return i;
}

Acwing模板——

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 找符合的右半区的左边界点。
int left_bound(int l, int r) {
    while (l < r) {
        int mid = (l + r) >> 1;
        if (check(mid)) r = mid;  //说明mid也符合区间
        else l = mid + 1;
    }
    return l;
}

//并找到符合的左半区的右边界点
int right_bound(int l, int r) {
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

  • 总结
    • ①left+(right-left)/2 （求的是左小边界）②left+(right-left+1)/2（求的是靠右大边界）
    • 注意，while在这个情况下要写成l<r

哈希优化

常通过将线性查找替换为哈希查找来降低算法的时间复杂度

给定一个整数数组 nums 和一个目标元素 target ，请在数组中搜索 “和” 为 target 的两个元素，并返回它们的数组索引。返回任意一个解即可。

线性方法：暴力枚举

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/* 方法一：暴力枚举 */
int *twoSumBruteForce(int *nums, int numsSize, int target, int *returnSize) {
    for (int i = 0; i < numsSize; ++i) {
        for (int j = i + 1; j < numsSize; ++j) {
            if (nums[i] + nums[j] == target) {
                int *res = malloc(sizeof(int) * 2);
                res[0] = i, res[1] = j;
                *returnSize = 2;
                return res;
            }
        }
    }
    *returnSize = 0;
    return NULL;
}

哈希查找：以空间换时间


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/* 哈希表 */
typedef struct {
    int key;
    int val;
    UT_hash_handle hh; // 基于 uthash.h 实现
} HashTable;

/* 哈希表查询 */
HashTable *find(HashTable *h, int key) {
    HashTable *tmp;
    HASH_FIND_INT(h, &key, tmp);
    return tmp;
}

/* 哈希表元素插入 */
void insert(HashTable *h, int key, int val) {
    HashTable *t = find(h, key);
    if (t == NULL) {
        HashTable *tmp = malloc(sizeof(HashTable));
        tmp->key = key, tmp->val = val;
        HASH_ADD_INT(h, key, tmp);
    } else {
        t->val = val;
    }
}

/*辅助哈希表 */
int *twoSumHashTable(int *nums, int numsSize, int target, int *returnSize) {
    HashTable *hashtable = NULL;
    for (int i = 0; i < numsSize; i++) {
        HashTable *t = find(hashtable, target - nums[i]);
        if (t != NULL) {
            int *res = malloc(sizeof(int) * 2);
            res[0] = t->val, res[1] = i;
            *returnSize = 2;
            return res;
        }
        insert(hashtable, nums[i], i);
    }
    *returnSize = 0;
    return NULL;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/* C++版本：辅助哈希表 */
vector<int> twoSumHashTable(vector<int> &nums, int target) {
    int size = nums.size();
    // 辅助哈希表，空间复杂度为 O(n)
    unordered_map<int, int> dic;
    // 单层循环，时间复杂度为 O(n)
    for (int i = 0; i < size; i++) {
	    // 如果找到了（且没超过元素界限），那么直接返回
        if (dic.find(target - nums[i]) != dic.end()) {
            return {dic[target - nums[i]], i};
        }
        dic.emplace(nums[i], i);//添加
    }
    return {};
}

搜索总结

  • 暴力搜索：包括DS（深搜）和BS
  • 自适应搜索：使用这些算法往往需要对数据进行预处理。例如，二分查找需要预先对数组进行排序，哈希查找和树查找都需要借助额外的数据结构，维护这些数据结构也需要额外的时间和空间开销。
    • “二分查找”利用数据的有序性实现高效查找，仅适用于数组。
    • “哈希查找”利用哈希表将搜索数据和目标数据建立为键值对映射，从而实现查询操作。
    • “树查找”在特定的树结构（例如二叉搜索树）中，基于比较节点值来快速排除节点，从而定位目标元素。
线性 二分 树 哈希
数组要求 无序 有序 有序 无序
数据预处理 / 排序$O(nlogn)$ 建树$O(nlogn)$ 建立哈希$O(n)$
查找元素 $O(n)$ $O(logn)$ $O(logn)$ $O(1)$

线性搜索适用于小型或频繁更新的数据；二分查找适用于大型、排序的数据；哈希查找适用于对查询效率要求较高且无须范围查询的数据；树查找适用于需要维护顺序和支持范围查询的大型动态数据。

排序

插入排序 $O(n^2)$

但在数据量较小的情况下，插入排序通常更快。

选择一个基准元素，将该元素与其左侧已排序区间的元素逐一比较大小，并将该元素插入到正确的位置。

  1. 初始状态下，数组的第 1 个元素已完成排序。
  2. 选取数组的第 2 个元素作为 base ，将其插入到正确位置后，数组的前 2 个元素已排序。
  3. 选取第 3 个元素作为 base ，将其插入到正确位置后，数组的前 3 个元素已排序。
  4. 以此类推，在最后一轮中，选取最后一个元素作为 base ，将其插入到正确位置后，所有元素均已排序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/* 插入排序 */
void insertionSort(int nums[], int size) {
    // 外循环：已排序元素数量为 1, 2, ..., n
    for (int i = 1; i < size; i++) {
	    // 注意：i从1开始！！！！！即已经排序1个元素
        int base = nums[i]; //暂存下一个未排序元素
        int j = i - 1;// 已经排序元素为最后一个下标
        // 内循环：将 base 插入到已排序部分的正确位置
        while (j >= 0 && nums[j] > base) {
	        // 若：已经排序元素最后一个元素大于base，那么向后移，逐层往前比较
            // 将 nums[j] 向右移动一位
            nums[j + 1] = nums[j];
            j--;
        }
        // 将 base 赋值到正确位置
        nums[j + 1] = base;
    }
}

快速排序 $O(nlogn)$

基于分治策略的排序算法

哨兵划分

快速排序的核心操作是“哨兵划分”，其目标是：选择数组中的某个元素作为“基准数”，将所有小于基准数的元素移到其左侧，而大于基准数的元素移到其右侧。

  1. 选取数组最左端元素作为基准数，初始化两个指针 i 和 j 分别指向数组的两端。
  2. 设置一个循环，在每轮中使用 i（j）分别寻找第一个比基准数大（小）的元素，然后交换这两个元素。
  3. 循环执行步骤 2. ，直到 i 和 j 相遇时停止，最后将基准数交换至两个子数组的分界线。





左子数组任意元素 ≤ 基准数 ≤ 右子数组任意元素。因此，我们接下来只需对这两个子数组进行排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/* 元素交换 */
void swap(int nums[], int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

/* 快速排序类 */
// 快速排序类-哨兵划分
int partition(int nums[], int left, int right) {
    // 以 nums[left] 为基准数
    int i = left, j = right;
    while (i < j) {
        while (i < j && nums[j] >= nums[left]) {
            // 从右向左找首个小于基准数的元素
            j--;
        }
        while (i < j && nums[i] <= nums[left]) {
            // 从左向右找首个大于基准数的元素
            i++;
        }
        // 交换这两个元素
        swap(nums, i, j);
    }
    // 将基准数交换至两子数组的分界线
    swap(nums, i, left);
    // 返回基准数的索引
    return i;
}

Q：哨兵划分中“从右往左查找”与“从左往右查找”的顺序可以交换吗？

不行，当我们以最左端元素为基准数时，必须先“从右往左查找”再“从左往右查找”。这个结论有些反直觉，我们来剖析一下原因。

哨兵划分 partition() 的最后一步是交换 nums[left] 和 nums[i] 。完成交换后，基准数左边的元素都 <= 基准数，这就要求最后一步交换前 nums[left] >= nums[i] 必须成立。假设我们先“从左往右查找”，那么如果找不到比基准数更大的元素，则会在 i == j 时跳出循环，此时可能 nums[j] == nums[i] > nums[left]。也就是说，此时最后一步交换操作会把一个比基准数更大的元素交换至数组最左端，导致哨兵划分失败。

举个例子，给定数组 [0, 0, 0, 0, 1] ，如果先“从左向右查找”，哨兵划分后数组为 [1, 0, 0, 0, 0] ，这个结果是不正确的。

开始排序

  1. 首先，对原数组执行一次“哨兵划分”，得到未排序的左子数组和右子数组。
  2. 然后，对左子数组和右子数组分别递归执行“哨兵划分”。
  3. 持续递归，直至子数组长度为 1 时终止，从而完成整个数组的排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
/* 快速排序类 */
// 快速排序类-快速排序
void quickSort(int nums[], int left, int right) {
    // 子数组长度为 1 时终止递归
    if (left >= right) {
        return;
    }
    // 哨兵划分
    int pivot = partition(nums, left, right);
    // 递归左子数组、右子数组
    quickSort(nums, left, pivot - 1);
    quickSort(nums, pivot + 1, right);
}

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/* 合并左子数组和右子数组 */
void merge(int *nums, int left, int mid, int right) {
    // 左子数组区间为 [left, mid], 右子数组区间为 [mid+1, right]
    // 创建一个临时数组 tmp ，用于存放合并后的结果
    int tmpSize = right - left + 1; //合并区段的长度
    int *tmp = (int *)malloc(tmpSize * sizeof(int));
    // 初始化左子数组和右子数组的起始索引
    int i = left, j = mid + 1, k = 0;
    // i是合并区段左区段的起点，j是合并区段右区段的起点
    // 当左右子数组都还有元素时，进行比较并将较小的元素复制到临时数组中
    while (i <= mid && j <= right) {
    //终止条件，i到达左区段终点（mid），j到底右区段终点（right）
        if (nums[i] <= nums[j]) {
            tmp[k++] = nums[i++];
        } else {
            tmp[k++] = nums[j++];
        }
    }
    // 将左子数组和右子数组的剩余元素复制到临时数组中
    while (i <= mid) {
        tmp[k++] = nums[i++];
    }
    while (j <= right) {
        tmp[k++] = nums[j++];
    }
    // 将临时数组 tmp 中的元素复制回原数组 nums 的对应区间
    for (k = 0; k < tmpSize; ++k) {
        nums[left + k] = tmp[k];
    }
    // 释放内存
    free(tmp);
}

/* 归并排序 */
void mergeSort(int *nums, int left, int right) {
    // 终止条件
    if (left >= right)
        return; // 当子数组长度为 1 时终止递归
    // 划分阶段
    int mid = (left + right) / 2;    // 计算中点
    mergeSort(nums, left, mid);      // 递归左子数组
    mergeSort(nums, mid + 1, right); // 递归右子数组
    // 合并阶段
    merge(nums, left, mid, right);
}

堆排序 $O(nlogn)$

认识堆

堆基本概念

  • 「小顶堆 min heap」：任意节点的值 ≤ 其子节点的值。
  • 「大顶堆 max heap」：任意节点的值 ≥ 其子节点的值。

堆的常用操作

操作 说明 复杂度
push() 元素入堆 $O(logn)$
pop() 出堆 $O(logn)$
peek 访问堆顶元素（大堆最大值，小堆最小值） $O(1)$
size() 元素数量
empty() 是否为空 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/* 初始化堆 */
// 初始化小顶堆
priority_queue<int, vector<int>, greater<int>> minHeap;
// 初始化大顶堆
priority_queue<int, vector<int>, less<int>> maxHeap;

/* 元素入堆 */
maxHeap.push(1);
maxHeap.push(3);
maxHeap.push(2);
maxHeap.push(5);
maxHeap.push(4);

/* 获取堆顶元素 */
int peek = maxHeap.top(); // 5

/* 堆顶元素出堆 */
// 出堆元素会形成一个从大到小的序列
maxHeap.pop(); // 5
maxHeap.pop(); // 4
maxHeap.pop(); // 3
maxHeap.pop(); // 2
maxHeap.pop(); // 1

/* 获取堆大小 */
int size = maxHeap.size();

/* 判断堆是否为空 */
bool isEmpty = maxHeap.empty();

/* 输入列表并建堆 */
vector<int> input{1, 3, 2, 5, 4};
priority_queue<int, vector<int>, greater<int>> minHeap(input.begin(), input.end());

堆的表示

堆正是一种完全二叉树，因此我们将采用数组来存储堆。

给定索引$i$，那么左子结点为$2i+1$,右子结点为$2i+2$
其父结点为$\lfloor (i-1)/2 \rfloor$ (当索引越界时，表示空节点或节点不存在。)

建立堆

初始建立

1
2
3
4
5
6
7
//逆序重建堆
    void buildMaxHeap(vector<int>& arr, int heapSize) {
        // heapSize/2将刚好按非叶结点最底层的哪个结点开始依次逆序重建堆
        for (int i = heapSize / 2; i >= 0; --i) {
            maxHeapify(arr, i, heapSize);
        }
    }

比如在这里，从heapSize/2开始建立堆，那么将从5号结点开始，逆序往前建立。（heapSize/2）即最后一个非叶结点的序号

出入平安

  1. 入堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/* 元素入堆 */
void push(MaxHeap *maxHeap, int val) {
    // 默认情况下，不应该添加这么多节点
    if (maxHeap->size == MAX_SIZE) {
        printf("heap is full!");
        return;
    }
    // 添加节点
    maxHeap->data[maxHeap->size] = val;
    maxHeap->size++;

    // 从底至顶堆化
    siftUp(maxHeap, maxHeap->size - 1);
}

/* 从节点 i 开始，从底至顶堆化 */
void siftUp(MaxHeap *maxHeap, int i) {
    while (true) {
        // 获取节点 i 的父节点
        int p = parent(maxHeap, i);
        // 当“越过根节点”或“节点无须修复”时，结束堆化[重要条件！]
        if (p < 0 || maxHeap->data[i] <= maxHeap->data[p]) {
            break;
        }
        // 交换两节点
        swap(maxHeap, i, p);
        // 循环向上堆化
        i = p;
    }
}
  1. 出堆
  • 先将元素与末尾交换，然后以该元素的堆迭代

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    /* 元素出堆 */
    int pop(MaxHeap *maxHeap) {
        // 判空处理
        if (isEmpty(maxHeap)) {
            printf("heap is empty!");
            return INT_MAX;
        }
        // 交换根节点与最右叶节点（交换首元素与尾元素）
        swap(maxHeap, 0, size(maxHeap) - 1);
        // 删除节点
        int val = maxHeap->data[maxHeap->size - 1];
        maxHeap->size--;
        // 从顶至底堆化
        siftDown(maxHeap, 0);

        // 返回堆顶元素
        return val;
    }

    /* 从节点 i 开始，从顶至底堆化 */
    void siftDown(MaxHeap *maxHeap, int i) {
        while (true) {
            // 判断节点 i, l, r 中值最大的节点，记为 max
            int l = left(maxHeap, i);
            int r = right(maxHeap, i);
            int max = i;
            if (l < size(maxHeap) && maxHeap->data[l] > maxHeap->data[max]) {
                max = l;
            }
            if (r < size(maxHeap) && maxHeap->data[r] > maxHeap->data[max]) {
                max = r;
            }
            // 若节点 i 最大或索引 l, r 越界，则无须继续堆化，跳出
            if (max == i) {
                break;
            }
            // 交换两节点
            swap(maxHeap, i, max);
            // 循环向下堆化
            i = max;
        }
    }

套路：我们将堆中所有元素取反，从而用大顶堆来模拟小顶堆

桶排序 $O(n+k)$

「桶排序 bucket sort」是分治策略的一个典型应用。它通过设置一些具有大小顺序的桶，每个桶对应一个数据范围，将数据平均分配到各个桶中；然后，在每个桶内部分别执行排序；最终按照桶的顺序将所有数据合并。

  1. 初始化 k 个桶，将 n 个元素分配到 k 个桶中。
  2. 对每个桶分别执行排序（这里采用编程语言的内置排序函数）。
  3. 按照桶从小到大的顺序合并结果。


考虑一个长度为 n的数组，其元素是范围 $[0,1)$ 内的浮点数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/* 桶排序 */
void bucketSort(vector<float> &nums) {
    // 初始化 k = n/2 个桶，预期向每个桶分配 2 个元素
    int k = nums.size() / 2;
    vector<vector<float>> buckets(k);
    // 1. 将数组元素分配到各个桶中
    for (float num : nums) {
        // 输入数据范围为 [0, 1)，使用 num * k 映射到索引范围 [0, k-1]
        int i = num * k;
        // 将 num 添加进桶 bucket_idx
        buckets[i].push_back(num);
    }
    // 2. 对各个桶执行排序
    for (vector<float> &bucket : buckets) {
        // 使用内置排序函数，也可以替换成其他排序算法
        sort(bucket.begin(), bucket.end());
    }
    // 3. 遍历桶合并结果
    int i = 0;
    for (vector<float> &bucket : buckets) {
        for (float num : bucket) {
            nums[i++] = num;
        }
    }
}

如何实现平均分配

桶排序的时间复杂度理论上可以达到 $O(n)$ ，关键在于将元素均匀分配到各个桶中，因为实际数据往往不是均匀分布的。例如，我们想要将淘宝上的所有商品按价格范围平均分配到 10 个桶中，但商品价格分布不均，低于 100 元的非常多，高于 1000 元的非常少。若将价格区间平均划分为 10 个，各个桶中的商品数量差距会非常大。

思路：将数据粗略地分到 3 个桶中。分配完毕后，再将商品较多的桶继续划分为 3 个桶，直至所有桶中的元素数量大致相等。


如果我们提前知道商品价格的概率分布，则可以根据数据概率分布设置每个桶的价格分界线。值得注意的是，数据分布并不一定需要特意统计，也可以根据数据特点采用某种概率模型进行近似。

小结

分治、广搜与回溯

分治

「分治 divide and conquer」，全称分而治之

  1. 分（划分阶段）：递归地将原问题分解为两个或多个子问题，直至到达最小子问题时终止。
  2. 治（合并阶段）：从已知解的最小子问题开始，从底至顶地将子问题的解进行合并，从而构建出原问题的解。

一个问题是否适合使用分治解决，通常可以参考以下几个判断依据。

  1. 问题可以分解：原问题可以分解成规模更小、类似的子问题，以及能够以相同方式递归地进行划分。
  2. 子问题是独立的：子问题之间没有重叠，互不依赖，可以独立解决。
  3. 子问题的解可以合并：原问题的解通过合并子问题的解得来。

归并排序满足以上三个判断依据。

  1. 问题可以分解：递归地将数组（原问题）划分为两个子数组（子问题）。
  2. 子问题是独立的：每个子数组都可以独立地进行排序（子问题可以独立进行求解）。
  3. 子问题的解可以合并：两个有序子数组（子问题的解）可以合并为一个有序数组（原问题的解）。

分治搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/* 二分查找：问题 f(i, j) */
int dfs(int nums[], int target, int i, int j) {
    // 返回条件1：若区间为空，代表无目标元素，则返回 -1
    if (i > j) {
        return -1;
    }
    // 计算中点索引 m
    int m = (i + j) / 2;
    if (nums[m] < target) {
        // 递归子问题 f(m+1, j)
        return dfs(nums, target, m + 1, j);
    } else if (nums[m] > target) {
        // 递归子问题 f(i, m-1)
        return dfs(nums, target, i, m - 1);
    } else {
        // 找到目标元素，返回其索引
        //返回条件2：找到了
        return m;
    }
}

/* 二分查找 */
int binarySearch(int nums[], int target, int numsSize) {
    int n = numsSize;
    // 求解问题 f(0, n-1)
    return dfs(nums, target, 0, n - 1);
}

构建树

已经知道前序遍历和后序遍历，构建树拆解子问题就是构建每颗子树

  • 前序遍历：[ 根节点 | 左子树 | 右子树 ]
  • 中序遍历：[ 左子树 | 根节点 ｜ 右子树 ]


根结点在前序索引 树中序索引的范围
当前树 i [l,r]
左子树 i+1 [l,m]
右子树 i+(m-l)+1
【m-l：表示左子树的长度】		 [m+1,r] 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/* 构建二叉树：分治 */
// 前序数组、中序数组
TreeNode *dfs(vector<int> &preorder, unordered_map<int, int> &inorderMap, int i, int l, int r) {
    // 子树区间为空时终止
    if (r - l < 0)
        return NULL;
    // 初始化根节点
    TreeNode *root = new TreeNode(preorder[i]);
    // 查询 m ，从而划分左右子树
    int m = inorderMap[preorder[i]];
    //索引是树值，i（val）是中序编号下标。即找到这个子树根节点对应的中序遍历的下标
    // 子问题：构建左子树
    root->left = dfs(preorder, inorderMap, i + 1, l, m - 1);
    // 子问题：构建右子树
    root->right = dfs(preorder, inorderMap, i + 1 + m - l, m + 1, r);
    // 返回根节点
    return root;
}

/* 构建二叉树 */
TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
    // 初始化哈希表，存储 inorder 元素到索引的映射
    unordered_map<int, int> inorderMap;
    for (int i = 0; i < inorder.size(); i++) {
    //哈希表用于快速访问m
        inorderMap[inorder[i]] = i;
        //索引是树值，i（val）是编号下标。
    }
    TreeNode *root = dfs(preorder, inorderMap, 0, 0, inorder.size() - 1);
    return root;
}

结束时刻：构建的树这个结点为根节点

汉诺塔问题：分类分治

给定三根柱子，记为 A、B 和 C 。起始状态下，柱子 A 上套着 n 个圆盘，它们从上到下按照从小到大的顺序排列。我们的任务是要把这 n 个圆盘移到柱子 C 上，并保持它们的原有顺序不变（如图 12-10 所示）。在移动圆盘的过程中，需要遵守以下规则。

  1. 圆盘只能从一根柱子顶部拿出，从另一根柱子顶部放入。
  2. 每次只能移动一个圆盘。
  3. 小圆盘必须时刻位于大圆盘之上。

我们将规模为 $i$ 的汉诺塔问题记作 $f(i)$。

  • 对于$f(1)$问题，直接移动即可
  • 对于$f(2)$问题，需要借助中间柱子B移动
  • 当$f(3)$时，把最上面两个看作一个整体。拆解为2个$f(2)$和一个$f(1)$问题

类推得到——

  1. 将 $(n-1)$ 个圆盘借助 C 从 A 移至 B 。
  2. 将剩余 1 个圆盘从 A 直接移至 C 。
  3. 将 $(n-1)$个圆盘借助 A 从 B 移至 C 。


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/* 移动一个圆盘 */
void move(vector<int> &src, vector<int> &tar) {
    // 从 src 顶部拿出一个圆盘
    int pan = src.back();
    src.pop_back();
    // 将圆盘放入 tar 顶部
    tar.push_back(pan);
}

/* 求解汉诺塔问题 f(i) */
void dfs(int i, vector<int> &src, vector<int> &buf, vector<int> &tar) {
    // 若 src 只剩下一个圆盘，则直接将其移到 tar
    if (i == 1) {
        move(src, tar);
        return;
    }
    // 子问题 f(i-1) ：将 src 顶部 i-1 个圆盘借助 tar 移到 buf
    dfs(i - 1, src, tar, buf);
    // 子问题 f(1) ：将 src 剩余一个圆盘移到 tar
    move(src, tar);
    // 子问题 f(i-1) ：将 buf 顶部 i-1 个圆盘借助 src 移到 tar
    dfs(i - 1, buf, src, tar);
}

/* 求解汉诺塔问题 */
void solveHanota(vector<int> &A, vector<int> &B, vector<int> &C) {
    int n = A.size();
    // 将 A 顶部 n 个圆盘借助 B 移到 C
    dfs(n, A, B, C);
}

广度搜索BFS

参考：Leetcode文章

适用于：「层序遍历」、「最短路径」

层序遍历


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/* 层序遍历 */
vector<int> levelOrder(TreeNode *root) {
    // 初始化队列，加入根节点
    queue<TreeNode *> queue;
    queue.push(root);
    // 初始化一个列表，用于保存遍历序列
    vector<int> vec;
    while (!queue.empty()) {
        TreeNode *node = queue.front();
        queue.pop();              // 队列出队
        vec.push_back(node->val); // 保存节点值
        if (node->left != nullptr)
            queue.push(node->left); // 左子节点入队
        if (node->right != nullptr)
            queue.push(node->right); // 右子节点入队
    }
    return vec;
}

若要判断当前结点在那一层？见leetcode 102. 二叉树的层序遍历

最短路径

用 BFS 的话，距离源点更近的点会先被遍历到，这样就能找到到某个点的最短路径了。

回溯

「回溯算法 backtracking algorithm」是一种通过穷举来解决问题的方法，它的核心思想是从一个初始状态出发，暴力搜索所有可能的解决方案，当遇到正确的解则将其记录，直到找到解或者尝试了所有可能的选择都无法找到解为止。

通常采用“深度优先搜索”来遍历解空间

解法套路

记录解

给定一棵二叉树，搜索并记录所有值为 7 的节点，请返回节点列表。

1
2
3
4
5
6
7
8
9
10
11
12
/* 前序遍历：例题一 */
void preOrder(TreeNode *root) {
    if (root == nullptr) {
        return;
    }
    if (root->val == 7) {
        // 记录解
        res.push_back(root);
    }
    preOrder(root->left);
    preOrder(root->right);
}

尝试与回退

当算法在搜索过程中遇到某个状态无法继续前进或无法得到满足条件的解时，它会撤销上一步的选择，退回到之前的状态，并尝试其他可能的选择。

对于例题一，访问每个节点都代表一次“尝试”，而越过叶节点或返回父节点的 return 则表示“回退”。

在二叉树中搜索所有值为 7 的节点，请返回根节点到这些节点的路径。

在例题一代码的基础上，我们需要借助一个列表 path 记录访问过的节点路径。当访问到值为 7 的节点时，则复制 path 并添加进结果列表 res 。遍历完成后，res 中保存的就是所有的解。代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/* 前序遍历：例题二 */
void preOrder(TreeNode *root) {
    if (root == nullptr) {
        return;
    }
    // 尝试
    path.push_back(root);
    if (root->val == 7) {
        // 记录解
        res.push_back(path);
    }
    preOrder(root->left);
    preOrder(root->right);
    // 回退
    path.pop_back();
}


……


剪枝

复杂的回溯问题通常包含一个或多个约束条件，约束条件通常可用于“剪枝”。

在二叉树中搜索所有值为 7 的节点，请返回根节点到这些节点的路径，并要求路径中不包含值为 3 的节点。

为了满足以上约束条件，我们需要添加剪枝操作：在搜索过程中，若遇到值为 3 的节点，则提前返回，不再继续搜索。代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/* 前序遍历：例题三 */
void preOrder(TreeNode *root) {
    // 剪枝
    if (root == nullptr || root->val == 3) {
        return;
    }
    // 尝试
    path.push_back(root);
    if (root->val == 7) {
        // 记录解
        res.push_back(path);
    }
    preOrder(root->left);
    preOrder(root->right);
    // 回退
    path.pop_back();
}

框架代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/* 回溯算法框架 */
void backtrack(State *state, vector<Choice *> &choices, vector<State *> &res) {
    // 判断是否为解
    if (isSolution(state)) {
        // 记录解
        recordSolution(state, res);
        // 不再继续搜索???看题目意思
        return;
    }
    // 遍历所有选择
    for (Choice choice : choices) {
        // 剪枝：判断选择是否合法
        if (isValid(state, choice)) {
            // 尝试：做出选择，更新状态
            makeChoice(state, choice);
            backtrack(state, choices, res);
            
            // 回退：撤销选择，恢复到之前的状态
            undoChoice(state, choice);
        }
    }
}

找到值为 7 的节点后应该继续搜索，因此需要将记录解之后的 return 语句删除。图对比了保留或删除 return 语句的搜索过程。

以找7为例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/* 判断当前状态是否为解 */
bool isSolution(vector<TreeNode *> &state) {
	// state即树的结点
    return !state.empty() && state.back()->val == 7;
}

/* 记录解 */
void recordSolution(vector<TreeNode *> &state, vector<vector<TreeNode *>> &res) {
    res.push_back(state);
}

/* 判断在当前状态下，该选择是否合法 */
bool isValid(vector<TreeNode *> &state, TreeNode *choice) {
    return choice != NULL && choice->val != 3;
}

/* 更新状态 */
void makeChoice(vector<TreeNode *> &state, TreeNode *choice) {
    state.push_back(choice);
}

/* 恢复状态 */
void undoChoice(vector<TreeNode *> &state, TreeNode *choice) {
    state.pop_back();
}

/* 回溯算法：例题三 */
void backtrack(vector<TreeNode *> &state, vector<TreeNode *> &choices, vector<vector<TreeNode *>> &res) {
    // 检查是否为解
    if (isSolution(state)) {
        // 记录解
        recordSolution(state, res);
    }
    // 遍历所有选择
    for (TreeNode *choice : choices) {
        // 剪枝：检查选择是否合法
        if (isValid(state, choice)) {
            // 尝试：做出选择，更新状态
            makeChoice(state, choice);
            // 进行下一轮选择
            vector<TreeNode *> nextChoices{choice->left, choice->right};
            backtrack(state, nextChoices, res);
            // 回退：撤销选择，恢复到之前的状态
            undoChoice(state, choice);
        }
    }
}

回溯的开销较大，BUT
回溯算法仍然是某些搜索问题和约束满足问题的最佳解决方案。对于这些问题，由于无法预测哪些选择可生成有效的解，因此我们必须对所有可能的选择进行遍历。在这种情况下，关键是如何优化效率，常见的效率优化方法有两种。

  • 剪枝：避免搜索那些肯定不会产生解的路径，从而节省时间和空间。
  • 启发式搜索：在搜索过程中引入一些策略或者估计值，从而优先搜索最有可能产生有效解的路径。

回溯典型例题

搜索问题：这类问题的目标是找到满足特定条件的解决方案。

  • 全排列问题：给定一个集合，求出其所有可能的排列组合。
  • 子集和问题：给定一个集合和一个目标和，找到集合中所有和为目标和的子集。
  • 汉诺塔问题：给定三根柱子和一系列大小不同的圆盘，要求将所有圆盘从一根柱子移动到另一根柱子，每次只能移动一个圆盘，且不能将大圆盘放在小圆盘上。

约束满足问题：这类问题的目标是找到满足所有约束条件的解。

  • N 皇后：在棋盘上放置 N 个皇后，使得它们互不攻击。
  • 数独：在 9×9 的网格中填入数字 1 ~ 9 ，使得每行、每列和每个 3×3 子网格中的数字不重复。
  • 图着色问题：给定一个无向图，用最少的颜色给图的每个顶点着色，使得相邻顶点颜色不同。

组合优化问题：这类问题的目标是在一个组合空间中找到满足某些条件的最优解。

  • 0-1 背包问题：给定一组物品和一个背包，每个物品有一定的价值和重量，要求在背包容量限制内，选择物品使得总价值最大。
  • 旅行商问题：在一个图中，从一个点出发，访问所有其他点恰好一次后返回起点，求最短路径。
  • 最大团问题：给定一个无向图，找到最大的完全子图，即子图中的任意两个顶点之间都有边相连。

请注意，对于许多组合优化问题，回溯不是最优解决方案。

  • 0-1 背包问题通常使用动态规划解决，以达到更高的时间效率。
  • 旅行商是一个著名的 NP-Hard 问题，常用解法有遗传算法和蚁群算法等。
  • 最大团问题是图论中的一个经典问题，可用贪心算法等启发式算法来解决。

全排列问题

定义是在给定一个集合（如一个数组或字符串）的情况下，找出其中元素的所有可能的排列。

无相等元素的情况

将搜索过程展开成一棵递归树，树中的每个节点代表当前状态 state 。从根节点开始，经过三轮选择后到达叶节点，每个叶节点都对应一个排列。

重复选择剪枝

为了实现每个元素只被选择一次，我们考虑引入一个布尔型数组 selected ，其中 selected[i] 表示 choices[i] 是否已被选择，并基于它实现以下剪枝操作。

  • 在做出选择 choice[i] 后，我们就将 selected[i] 赋值为 True ，代表它已被选择。
  • 遍历选择列表 choices 时，跳过所有已被选择的节点，即剪枝。

如图 13-6 所示，假设我们第一轮选择 1 ，第二轮选择 3 ，第三轮选择 2 ，则需要在第二轮剪掉元素 1 的分支，在第三轮剪掉元素 1 和元素 3 的分支。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/* 回溯算法：全排列 I */
void backtrack(vector<int> &state, const vector<int> &choices, vector<bool> &selected, vector<vector<int>> &res) {
    // 当状态长度等于元素数量时，记录解 isSolution [重复元素判断在剪枝过程完成]
    if (state.size() == choices.size()) {
        res.push_back(state);
        return;
    }

    // 遍历同一级别的所有选项
    for (int i = 0; i < choices.size(); i++) {
        int choice = choices[i];
        
        // 剪枝：不允许重复选择元素
        if (!selected[i]) {
        
            // 尝试：做出选择，更新状态
            selected[i] = true;
            state.push_back(choice);
            
            // 进行下一轮选择
            backtrack(state, choices, selected, res);
            
            // 回退：撤销选择，恢复到之前的状态
            selected[i] = false;
            state.pop_back();
        }
    }
}

/* 全排列 I */
vector<vector<int>> permutationsI(vector<int> nums) {
    vector<int> state;
    vector<bool> selected(nums.size(), false);// 设定nums.size个初始值，初始值均为false
    vector<vector<int>> res;
    backtrack(state, nums, selected, res);
    return res;
}

考虑相等元素的情况

因为生成重复排列的搜索分支没有必要，应当提前识别并剪枝.从本质上看，我们的目标是在某一轮选择中，保证多个相等的元素仅被选择一次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/* 回溯算法：全排列 II */
void backtrack(vector<int> &state, const vector<int> &choices, vector<bool> &selected, vector<vector<int>> &res) {
    // 当状态长度等于元素数量时，记录解
    if (state.size() == choices.size()) {
        res.push_back(state);
        return;
    }
    // 遍历所有选择
    unordered_set<int> duplicated;// 引入哈希表记录重复，哈希表在同一级别中起作用
    // 遍历同一级别的所有选项
    for (int i = 0; i < choices.size(); i++) {
        int choice = choices[i];
        
        // 剪枝：不允许重复选择元素 且 不允许重复选择相等元素
        
        if (!selected[i] && duplicated.find(choice) == duplicated.end()) {
            // 尝试：做出选择，更新状态
            duplicated.emplace(choice); // 记录选择过的元素值
            selected[i] = true;
            state.push_back(choice);
            // 进行下一轮选择
            backtrack(state, choices, selected, res);
            
            // 回退：撤销选择，恢复到之前的状态
            selected[i] = false;
            state.pop_back();
            // 因为每次backtrack（即递归下一级）的时候，duplicated都会被重新初始化，所以不用管duplicated的回退情况。
        }
    }
}

/* 全排列 II */
vector<vector<int>> permutationsII(vector<int> nums) {
    vector<int> state;
    vector<bool> selected(nums.size(), false);
    vector<vector<int>> res;
    backtrack(state, nums, selected, res);
    return res;
}

区别两种剪枝条件

子集

求子集

遍历这个树的时候，把所有节点都记录下来，就是要求的子集集合。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    void backtracking(vector<int>& nums, int startIndex,
                      vector<vector<int>>& result, vector<int>& path) {
        result.push_back(path);
        // 收集子集，每遍历一步要放在终止添加的上面，否则会漏掉自己!!!!首次加入时，会加入空集合

        if (startIndex >= nums.size()) { // 终止条件
            return;
        }
        
        for (int i = startIndex; i < nums.size(); i++) {
	        // 尝试
            path.push_back(nums[i]);
            backtracking(nums, i + 1, result, path);
            // 回溯
            path.pop_back();
        }
    }

    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> path;

        backtracking(nums, 0, result, path);
        return result;
    }
};

子集和

无重复元素

给定一个正整数数组 nums 和一个目标正整数 target ，请找出所有可能的组合，使得组合中的元素和等于 target 。给定数组无重复元素，每个元素可以被选取多次。请以列表形式返回这些组合，列表中不应包含重复组合。 再次注意：输入集合中的元素可以被无限次重复选取。子集不区分元素顺序

本题集合中的元素可以被无限次选取，因此无须借助 selected 布尔列表来记录元素是否已被选择。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/* 回溯算法：子集和 I */
void backtrack(vector<int> &state, int target, int total, vector<int> &choices, vector<vector<int>> &res) {
    // 子集和等于 target 时，记录解
    if (total == target) {
        res.push_back(state);
        return;
    }
    // 遍历所有选择
    for (size_t i = 0; i < choices.size(); i++) {
        // 剪枝：若子集和超过 target ，则跳过该选择
        if (total + choices[i] > target) {
            continue;
        }
        // 尝试：做出选择，更新元素和 total
        state.push_back(choices[i]);
        // 进行下一轮选择
        backtrack(state, target, total + choices[i], choices, res);
        // 回退：撤销选择，恢复到之前的状态
        state.pop_back();
    }
}

/* 求解子集和 I（包含重复子集） */
vector<vector<int>> subsetSumINaive(vector<int> &nums, int target) {
    vector<int> state;       // 状态（子集）
    int total = 0;           // 子集和
    vector<vector<int>> res; // 结果列表（子集列表）
    backtrack(state, target, total, nums, res);
    return res;
}

重复子集剪枝
  1. 当第一轮和第二轮分别选择 3 和 4 时，会生成包含这两个元素的所有子集，记为 [3,4,…] 。
  2. 之后，当第一轮选择 4 时，则第二轮应该跳过 3 ，因为该选择产生的子集 [4,3,…] 和第 1. 步中生成的子集完全重复。

在搜索过程中，每一层的选择都是从左到右被逐个尝试的，因此越靠右的分支被剪掉的越多。

hl:"start"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/* 回溯算法：子集和 I */
void backtrack(vector<int> &state, int target, vector<int> &choices, int start, vector<vector<int>> &res) {
    // 子集和等于 target 时，记录解
    if (target == 0) {
        res.push_back(state);
        return;
    }
    // 遍历所有选择
    // 剪枝二：从 start 开始遍历，避免生成重复子集
    for (int i = start; i < choices.size(); i++) {
        // 剪枝一：若子集和超过 target ，则直接结束循环
        // 这是因为数组已排序，后边元素更大，子集和一定超过 target
        if (target - choices[i] < 0) {
            break;
        }
        // 尝试：做出选择，更新 target, start
        state.push_back(choices[i]);
        // 进行下一轮选择
        backtrack(state, target - choices[i], choices, i, res);
        // 回退：撤销选择，恢复到之前的状态
        state.pop_back();
    }
}

/* 求解子集和 I */
vector<vector<int>> subsetSumI(vector<int> &nums, int target) {
    vector<int> state;              // 状态（子集）
    sort(nums.begin(), nums.end()); // 对 nums 进行排序
    int start = 0;                  // 遍历起始点
    vector<vector<int>> res;        // 结果列表（子集列表）
    backtrack(state, target, nums, start, res);
    return res;
}
考虑重复元素的情况

给定一个正整数数组 nums 和一个目标正整数 target ，请找出所有可能的组合，使得组合中的元素和等于 target 。给定数组可能包含重复元素，每个元素只可被选择一次。请以列表形式返回这些组合，列表中不应包含重复组合。

本题规定每个数组元素只能被选择一次。幸运的是，我们也可以利用变量 start 来满足该约束：当做出选择 $X_i$ 后，设定下一轮从索引 $i+1$ 开始向后遍历。这样既能去除重复子集，也能避免重复选择元素。

前提：由于数组是已排序的，因此相等元素都是相邻的。这意味着在某轮选择中，若当前元素与其左边元素相等，则说明它已经被选择过，因此直接跳过当前元素。

hl:"start","sort"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/* 回溯算法：子集和 II */
void backtrack(vector<int> &state, int target, vector<int> &choices, int start, vector<vector<int>> &res) {
    // 子集和等于 target 时，记录解
    if (target == 0) {
        res.push_back(state);
        return;
    }
    // 遍历所有选择
    // 剪枝二：从 start 开始遍历，避免生成重复子集
    // 剪枝三：从 start 开始遍历，避免重复选择同一元素
    for (int i = start; i < choices.size(); i++) {
        // 剪枝一：若子集和超过 target ，则直接结束循环
        // 这是因为数组已排序，后边元素更大，子集和一定超过 target
        if (target - choices[i] < 0) {
            break;
        }
        // 剪枝四：如果该元素与左边元素相等，说明该搜索分支重复，直接跳过
        if (i > start && choices[i] == choices[i - 1]) {
            continue;
        }
        // 尝试：做出选择，更新 target, start
        state.push_back(choices[i]);
        // 进行下一轮选择
        backtrack(state, target - choices[i], choices, i + 1, res);
        // 回退：撤销选择，恢复到之前的状态
        state.pop_back();
    }
}

/* 求解子集和 II */
vector<vector<int>> subsetSumII(vector<int> &nums, int target) {
    vector<int> state;              // 状态（子集）
    sort(nums.begin(), nums.end()); // 对 nums 进行排序
    int start = 0;                  // 遍历起始点
    vector<vector<int>> res;        // 结果列表（子集列表）
    backtrack(state, target, nums, start, res);
    return res;
}

N皇后

根据国际象棋的规则，皇后可以攻击与同处一行、一列或一条斜线上的棋子。给定 $n$ 个皇后和一个 $n×n$ 大小的棋盘，寻找使得所有皇后之间无法相互攻击的摆放方案。

多个皇后不能在同一行、同一列、同一条对角线上。值得注意的是，对角线分为主对角线 \ 和次对角线 / 两种。

剪枝1：逐行放置

从第一行开始，在每行放置一个皇后，直至最后一行结束。

剪枝2：列和对角

  • 列

布尔型数组 cols 记录每一列是否有皇后。在每次决定放置前，我们通过 cols 将已有皇后的列进行剪枝，并在回溯中动态更新 cols 的状态。

  • 对角

设棋盘中某个格子的行列索引为$(row,col)$，选定矩阵中的某条主对角线，我们发现该对角线上所有格子的行索引减列索引都相等，即对角线上所有格子的 $(row,col)$ 为恒定值。

如果两个格子满足 $row_1-col_1=row_2-col_2$ ，则它们一定处在同一条主对角线上

次对角线上的所有格子的 $row+col$ 是恒定值。

$row-col$的范围是$[0-(n-1),(n-1)-0]=[-n+1,n-1]$
$row+col$的范围是$[0,(n-1)+(n-1)]=[0,2n-2]$
数量均为$2n-1$

hl:"row 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/* 回溯算法：n 皇后 */
void backtrack(int row, int n, vector<vector<string>> &state, vector<vector<vector<string>>> &res, vector<bool> &cols,
               vector<bool> &diags1, vector<bool> &diags2) {
    // 当放置完所有行时，记录解
    // isSolution:所有行都放置完了
    if (row == n) {
        res.push_back(state);
        return;
    }
    // 遍历所有列
    for (int col = 0; col < n; col++) {
        // 计算该格子对应的主对角线和次对角线
        int diag1 = row - col + n - 1;
        int diag2 = row + col;
        // 剪枝：不允许该格子所在列、主对角线、次对角线上存在皇后
        if (!cols[col] && !diags1[diag1] && !diags2[diag2]) {
            // 尝试：将皇后放置在该格子
            state[row][col] = "Q";
            // 改变col\diag1\diag2的状态
            cols[col] = diags1[diag1] = diags2[diag2] = true;
            
            // 放置下一行
            backtrack(row + 1, n, state, res, cols, diags1, diags2);
            // 回退：将该格子恢复为空位
            state[row][col] = "#";
            cols[col] = diags1[diag1] = diags2[diag2] = false;
        }
    }
}

/* 求解 n 皇后 */
vector<vector<vector<string>>> nQueens(int n) {
    // 初始化 n*n 大小的棋盘，其中 'Q' 代表皇后，'#' 代表空位
    vector<vector<string>> state(n, vector<string>(n, "#"));
    vector<bool> cols(n, false);           // 记录列是否有皇后
    vector<bool> diags1(2 * n - 1, false); // 记录主对角线上是否有皇后
    vector<bool> diags2(2 * n - 1, false); // 记录次对角线上是否有皇后
    vector<vector<vector<string>>> res;

    backtrack(0, n, state, res, cols, diags1, diags2);

    return res;
}

动态规划

「动态规划 dynamic programming」是一个重要的算法范式，它将一个问题分解为一系列更小的子问题，并通过存储子问题的解来避免重复计算，从而大幅提升时间效率。

初探动态规划

给定一个共有 $n$ 阶的楼梯，你每步可以上 1 阶或者 2 阶，请问有多少种方案可以爬到楼顶？

一个重要推论：爬到第 $n−1$ 阶的方案数加上爬到第$n−2$ 阶的方案数就等于爬到第 $n$ 阶的方案数。

hl:"dfs(i - 1)" title
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/* 搜索 */
int dfs(int i) {
    // 已知 dp[1] 和 dp[2] ，返回之
    if (i == 1 || i == 2)
        return i;
    // dp[i] = dp[i-1] + dp[i-2]
    int count = dfs(i - 1) + dfs(i - 2);
    return count;
}

/* 爬楼梯：搜索 */
int climbingStairsDFS(int n) {
    return dfs(n);
}

指数阶的时间复杂度是“重叠子问题”导致的。例如 $dp[9]$ 被分解为 $dp[8]$ 和 $dp[7]$ ，$dp[8]$ 被分解为 $dp[7]$ 和 $dp[6]$ ，两者都包含子问题$dp[7]$ 。

为了提升算法效率，我们希望所有的重叠子问题都只被计算一次。为此，我们声明一个数组 mem 来记录每个子问题的解，并在搜索过程中将重叠子问题剪枝。

  1. 当首次计算$dp[i]$时，我们将其记录至 mem[i] ，以便之后使用。
  2. 当再次需要计算 $dp[i]$ 时，我们便可直接从 mem[i] 中获取结果，从而避免重复计算该子问题。

代码如下所示：

title
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/* 记忆化搜索 */
int dfs(int i, vector<int> &mem) {
    // 已知 dp[1] 和 dp[2] ，返回之
    if (i == 1 || i == 2)
        return i;
    // 若存在记录 dp[i] ，则直接返回之
    if (mem[i] != -1)
        return mem[i];
    // dp[i] = dp[i-1] + dp[i-2]
    int count = dfs(i - 1, mem) + dfs(i - 2, mem);
    // 记录 dp[i]
    mem[i] = count;
    return count;
}

/* 爬楼梯：记忆化搜索 */
int climbingStairsDFSMem(int n) {
    // mem[i] 记录爬到第 i 阶的方案总数，-1 代表无记录
    vector<int> mem(n + 1, -1);
    return dfs(n, mem);
}

记忆化搜索是一种“从顶至底”的方法：我们从原问题（根节点）开始，递归地将较大子问题分解为较小子问题，直至解已知的最小子问题（叶节点）。之后，通过回溯逐层收集子问题的解，构建出原问题的解。

与之相反，动态规划是一种“从底至顶”的方法：从最小子问题的解开始，迭代地构建更大子问题的解，直至得到原问题的解。

由于动态规划不包含回溯过程，因此只需使用循环迭代实现，无须使用递归。

title
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/* 爬楼梯：动态规划 */
int climbingStairsDP(int n) {
    if (n == 1 || n == 2)
        return n;
    // 初始化 dp 表，用于存储子问题的解
    vector<int> dp(n + 1);
    // 初始状态：预设最小子问题的解
    dp[1] = 1;
    dp[2] = 2;
    // 状态转移：从较小子问题逐步求解较大子问题
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

但其实，我们不必专门开辟一个数组记录n个子问题的答案，只需两个变量滚动前进即可

title
1
2
3
4
5
6
7
8
9
10
11
12
/* 爬楼梯：空间优化后的动态规划 */
int climbingStairsDPComp(int n) {
    if (n == 1 || n == 2)
        return n;
    int a = 1, b = 2;
    for (int i = 3; i <= n; i++) {
        int tmp = b;
        b = a + b;
        a = tmp;
    }
    return b;
}

只保留必要的状态，通过“降维”来节省内存空间。这种空间优化技巧被称为“滚动变量”或“滚动数组”。

动态规划的特性

VS回溯、分治、动态规划

  • 分治算法递归地将原问题划分为多个相互独立的子问题，直至最小子问题，并在回溯中合并子问题的解，最终得到原问题的解。
  • 回溯算法在尝试和回退中穷举所有可能的解，并通过剪枝避免不必要的搜索分支。原问题的解由一系列决策步骤构成，我们可以将每个决策步骤之前的子序列看作一个子问题。
  • 动态规划也对问题进行递归分解，但与分治算法的主要区别是，动态规划中的子问题是相互依赖的，在分解过程中会出现许多重叠子问题。

    最优子结构

给定一个楼梯，你每步可以上 1 阶或者 2 阶，每一阶楼梯上都贴有一个非负整数，表示你在该台阶所需要付出的代价。给定一个非负整数数组 $cost$ ，其中 $cost[i]$ 表示在第 $i$ 个台阶需要付出的代价，$cost[0]$ 为地面（起始点）。请计算最少需要付出多少代价才能到达顶部？

为了尽可能减少代价，我们应该选择两者中较小的那一个：

原问题的最优解是从子问题的最优解构建得来的。本题显然具有最优子结构：我们从两个子问题最优解 $dp[i-1$ 和 $dp[i-2]$ 中挑选出较优的那一个，并用它构建出原问题 $dp[i]$的最优解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/* 爬楼梯最小代价：动态规划 */
int minCostClimbingStairsDP(vector<int> &cost) {
    int n = cost.size() - 1;
    if (n == 1 || n == 2)
        return cost[n];
    // 初始化 dp 表，用于存储子问题的解
    vector<int> dp(n + 1);
    // 初始状态：预设最小子问题的解
    dp[1] = cost[1];
    dp[2] = cost[2];
    // 状态转移：从较小子问题逐步求解较大子问题
    for (int i = 3; i <= n; i++) {
        dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];
    }
    return dp[n];
}

上一个求爬楼梯方案总数的问题，虽然看似是个记数问题，但是最优子结构浮现 可以堪称：第 $i$ 阶最大方案数量(最优子结构)等于第 $i-1$ 阶和第 $i-2$阶最大方案数量(最优子结构)之和。

无后效性

无后效性：给定一个确定的状态，它的未来发展只与当前状态有关，而与过去经历的所有状态无关

以爬楼梯问题为例，给定状态 $i$，它会发展出状态 $i+1$ 和状态 $i+2$ ，分别对应跳 1 步和跳 2 步。在做出这两种选择时，我们无须考虑状态 $i$ 之前的状态，它们对状态 $i$ 的未来没有影响。

给定一个共有 $n$ 阶的楼梯，你每步可以上 1 阶或者 2 阶，但不能连续两轮跳 1 阶，请问有多少种方案可以爬到楼顶？

在该问题中，如果上一轮是跳 1 阶上来的，那么下一轮就必须跳 2 阶。这意味着，下一步选择不能由当前状态（当前所在楼梯阶数）独立决定，还和前一个状态（上一轮所在楼梯阶数）有关。——无后效性 不行

扩展状态定义：状态 $[i,j]$ 表示处在第 $i$ 阶并且上一轮跳了 $j$ 阶，

最终返回$dp[n,1]+dp[n,2]$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/* 带约束爬楼梯：动态规划 */
int climbingStairsConstraintDP(int n) {
    if (n == 1 || n == 2) {
        return 1;
    }
    // 初始化 dp 表，用于存储子问题的解
    vector<vector<int>> dp(n + 1, vector<int>(3, 0));
    // 初始状态：预设最小子问题的解
    dp[1][1] = 1;
    dp[1][2] = 0;
    dp[2][1] = 0;
    dp[2][2] = 1;
    // 状态转移：从较小子问题逐步求解较大子问题
    for (int i = 3; i <= n; i++) {
        dp[i][1] = dp[i - 1][2];
        dp[i][2] = dp[i - 2][1] + dp[i - 2][2];
    }
    return dp[n][1] + dp[n][2];
}

动态规划解题思路

如何判断一个问题可否用动态规划

总的来说，如果一个问题包含重叠子问题、最优子结构，并满足无后效性，那么它通常适合用动态规划求解。

  • Step 1：决策树模型

    • 适合用回溯解决的问题通常满足“决策树模型”，这种问题可以使用树形结构来描述，其中每一个节点代表一个决策，每一条路径代表一个决策序列。
    • 换句话说，如果问题包含明确的决策概念，并且解是通过一系列决策产生的，那么它就满足决策树模型，通常可以使用回溯来解决。判断下面的加减分，决定具体是回溯还是动态规划

  • Step 2：加减分

    • 加分项
      • 问题包含最大（小）或最多（少）等最优化描述。
      • 问题的状态能够使用一个列表、多维矩阵或树来表示，并且一个状态与其周围的状态存在递推关系。
    • 减分项
      • 问题的目标是找出所有可能的解决方案，而不是找出最优解。
      • 问题描述中有明显的排列组合的特征，需要返回具体的多个方案。

解题思路

通常遵循以下步骤：描述决策，定义状态，建立$dp$表，推导状态转移方程，确定边界条件等。

给定一个 $n\times m$ 的二维网格 grid ，网格中的每个单元格包含一个非负整数，表示该单元格的代价。机器人以左上角单元格为起始点，每次只能向下或者向右移动一步，直至到达右下角单元格。请返回从左上角到右下角的最小路径和。

第一步：思考每轮的决策，定义状态，从而得到dp表

本题的每一轮的决策就是从当前格子向下或向右走一步

状态 $[i,j]$对应的子问题为：从起始点 $[0,0]$ 走到$[i,j]$的最小路径和，解记为$dp[i,j]$ 。

第二步：找出最优子结构，进而推导出状态转移方程

第三步：确定边界条件和状态转移顺序

处在首行的状态只能从其左边的状态得来，处在首列的状态只能从其上边的状态得来，因此首行 $i=0$和首列 $j=0$ 是边界条件。

title
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/* 最小路径和：暴力搜索 */
int minPathSumDFS(vector<vector<int>> &grid, int i, int j) {
    // 若为左上角单元格，则终止搜索
    if (i == 0 && j == 0) {
        return grid[0][0];
    }
    // 若行列索引越界，则返回 +∞ 代价
    if (i < 0 || j < 0) {
        return INT_MAX;
    }
    // 计算从左上角到 (i-1, j) 和 (i, j-1) 的最小路径代价
    int up = minPathSumDFS(grid, i - 1, j);
    int left = minPathSumDFS(grid, i, j - 1);
    // 返回从左上角到 (i, j) 的最小路径代价
    return min(left, up) != INT_MAX ? min(left, up) + grid[i][j] : INT_MAX;
}

上述方案造成重叠子问题的原因为：存在多条路径可以从左上角到达某一单元格。

title
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/* 最小路径和：记忆化搜索 */
int minPathSumDFSMem(vector<vector<int>> &grid, vector<vector<int>> &mem, int i, int j) {
    // 若为左上角单元格，则终止搜索
    if (i == 0 && j == 0) {
        return grid[0][0];
    }
    // 若行列索引越界，则返回 +∞ 代价
    if (i < 0 || j < 0) {
        return INT_MAX;
    }
    // 若已有记录，则直接返回
    if (mem[i][j] != -1) {
        return mem[i][j];
    }
    // 左边和上边单元格的最小路径代价
    int up = minPathSumDFSMem(grid, mem, i - 1, j);
    int left = minPathSumDFSMem(grid, mem, i, j - 1);
    // 记录并返回左上角到 (i, j) 的最小路径代价
    mem[i][j] = min(left, up) != INT_MAX ? min(left, up) + grid[i][j] : INT_MAX;
    return mem[i][j];
}
title
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* 最小路径和：动态规划 */
int minPathSumDP(vector<vector<int>> &grid) {
    int n = grid.size(), m = grid[0].size();
    // 初始化 dp 表
    vector<vector<int>> dp(n, vector<int>(m));
    // 边界条件
    dp[0][0] = grid[0][0];
    // 边界状态转移：首行
    for (int j = 1; j < m; j++) {
        dp[0][j] = dp[0][j - 1] + grid[0][j];
    }
    // 边界状态转移：首列
    for (int i = 1; i < n; i++) {
        dp[i][0] = dp[i - 1][0] + grid[i][0];
    }
    // 状态转移：其余行和列
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j];
        }
    }
    return dp[n - 1][m - 1];
}

由于每个格子只与其左边和上边的格子有关，因此我们可以只用一个单行数组来实现

title
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/* 最小路径和：空间优化后的动态规划 */
int minPathSumDPComp(vector<vector<int>> &grid) {
    int n = grid.size(), m = grid[0].size();
    // 初始化 dp 表
    vector<int> dp(m);
    // 状态转移：首行
    dp[0] = grid[0][0];
    for (int j = 1; j < m; j++) {
        dp[j] = dp[j - 1] + grid[0][j];
    }
    // 状态转移：其余行
    for (int i = 1; i < n; i++) {
        // 状态转移：首列
        dp[0] = dp[0] + grid[i][0];
        // 状态转移：其余列
        for (int j = 1; j < m; j++) {
            dp[j] = min(dp[j - 1], dp[j]) + grid[i][j];
        }
    }
    return dp[m - 1];
}

背包问题

0-1背包

给定 $i$ 个物品，第 $i$ 个物品的重量为 $wgt[i-1]$ 、价值为 $val[i-1]$ ，和一个容量为$cap$背包。每个物品只能选择一次，问在限定背包容量下能放入物品的最大价值。

我们可以将 0-1 背包问题看作一个由 $n$ 轮决策组成的过程，对于每个物体都有不放入和放入两种决策，因此该问题满足决策树模型。

第一步：思考每轮的决策，定义状态，从而得到 $dp$ 表

不放入背包，背包容量不变；放入背包，背包容量减小。由此可得状态定义：当前物品编号 $i$ 和剩余背包容量 $c$ ，记为 $[i,c]$ 。

状态$[i,c]$ 对应的子问题为：前 $i$ 个物品在剩余容量为 $c$ 的背包中的最大价值，记为 $dp[i,c]$ 。

第二步：找出最优子结构，进而推导出状态转移方程

即放入物品$i$和放入物品$i$的价值取最大

若当前物品的容量超过背包容量，则只能不放入。

我们以c=cap为例子
完全背包理解-1

完全背包理解-2

第三步：确定边界条件和状态转移顺序

当无物品或无剩余背包容量时最大价值为 0，两层循环正序遍历整个 dp 表即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/* 0-1 背包：暴力搜索 */
int knapsackDFS(vector<int> &wgt, vector<int> &val, int i, int c) {
    // 若已选完所有物品或背包无剩余容量，则返回价值 0
    if (i == 0 || c == 0) {
        return 0;
    }
    // 若超过背包容量，则只能选择不放入背包
    if (wgt[i - 1] > c) {
        return knapsackDFS(wgt, val, i - 1, c);
    }
    // 计算不放入和放入物品 i 的最大价值
    int no = knapsackDFS(wgt, val, i - 1, c);
    int yes = knapsackDFS(wgt, val, i - 1, c - wgt[i - 1]) + val[i - 1];
    // 返回两种方案中价值更大的那一个
    return max(no, yes);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/* 0-1 背包：记忆化搜索 */
int knapsackDFSMem(vector<int> &wgt, vector<int> &val, vector<vector<int>> &mem, int i, int c) {
    // 若已选完所有物品或背包无剩余容量，则返回价值 0
    if (i == 0 || c == 0) {
        return 0;
    }
    // 若已有记录，则直接返回
    if (mem[i][c] != -1) {
        return mem[i][c];
    }
    // 若超过背包容量，则只能选择不放入背包
    if (wgt[i - 1] > c) {
        return knapsackDFSMem(wgt, val, mem, i - 1, c);
    }
    // 计算不放入和放入物品 i 的最大价值
    int no = knapsackDFSMem(wgt, val, mem, i - 1, c);
    int yes = knapsackDFSMem(wgt, val, mem, i - 1, c - wgt[i - 1]) + val[i - 1];
    // 记录并返回两种方案中价值更大的那一个
    mem[i][c] = max(no, yes);
    return mem[i][c];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/* 0-1 背包：动态规划 */
int knapsackDP(vector<int> &wgt, vector<int> &val, int cap) {
    int n = wgt.size();
    // 初始化 dp 表
    vector<vector<int>> dp(n + 1, vector<int>(cap + 1, 0));
    // 状态转移
    for (int i = 1; i <= n; i++) {
        for (int c = 1; c <= cap; c++) {
            if (wgt[i - 1] > c) {
                // 若超过背包容量，则不选物品 i
                dp[i][c] = dp[i - 1][c];
            } else {
                // 不选和选物品 i 这两种方案的较大值
                dp[i][c] = max(dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] + val[i - 1]);
            }
        }
    }
    return dp[n][cap];
}

完全背包

基础版

给定 $i$ 个物品，第 $i$ 个物品的重量为 $wgt[i-1]$ 、价值为 $val[i-1]$ ，和一个容量为$cap$背包。每个物品可以重复选取，问在限定背包容量下能放入物品的最大价值。

在完全背包问题中，每种物品的数量是无限的，因此将物品 i放入背包后，仍可以从前 � 个物品中选择。

在完全背包问题的规定下，状态$[i,c]$的变化分为两种情况。

  • 不放入物品 i ：与 0-1 背包问题相同，转移至 $[i-1,c]$ 。
  • 放入物品 i ：与 0-1 背包问题不同，转移至$[i,c-wgt[i-1]]$。
hl:"dp[i][c -"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/* 完全背包：动态规划 */
int unboundedKnapsackDP(vector<int> &wgt, vector<int> &val, int cap) {
    int n = wgt.size();
    // 初始化 dp 表
    vector<vector<int>> dp(n + 1, vector<int>(cap + 1, 0));
    // 状态转移
    for (int i = 1; i <= n; i++) {
        for (int c = 1; c <= cap; c++) {
            if (wgt[i - 1] > c) {
                // 若超过背包容量，则不选物品 i
                dp[i][c] = dp[i - 1][c];
            } else {
                // 不选和选物品 i 这两种方案的较大值
                dp[i][c] = max(dp[i - 1][c], dp[i][c - wgt[i - 1]] + val[i - 1]);
            }
        }
    }
    return dp[n][cap];
}

零钱兑换I

给定 $n$ 种硬币，第 $i$ 种硬币的面值为 $coin[i-1]$ ，目标金额为 $amt$ ，每种硬币可以重复选取，问能够凑出目标金额的最少硬币数量。如果无法凑出目标金额，则返回 −1 。

  • 两道题可以相互转换，“物品”对应“硬币”、“物品重量”对应“硬币面值”、“背包容量”对应“目标金额”。
    • 有点难以理解，换个角度，背包重量要不超过限定，面值要不超过目标金额。
    • 价值要最大，数量要最少。【最优化价值/数量——目标】
  • 优化目标相反，完全背包问题是要最大化物品价值，零钱兑换问题是要最小化硬币数量。
  • 完全背包问题是求“不超过”背包容量下的解，零钱兑换是求“恰好”凑到目标金额的解。

即$dp[i,c]$表示的是放入第$i$硬币后的最少硬币数量

当目标金额为 0 时，凑出它的最少硬币数量为 0 ，即首列所有 $dp[i,0]$ 都等于 0 。

  • 边界
    • 当无硬币时，无法凑出任意 >0 的目标金额，即是无效解。$dp[0,a]=MAX$
    • 首行
title
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/* 零钱兑换：动态规划 */
int coinChangeDP(vector<int> &coins, int amt) {
    int n = coins.size();
    int MAX = amt + 1;
	// MAX——表示无效解

    // 初始化 dp 表
    vector<vector<int>> dp(n + 1, vector<int>(amt + 1, 0));
    // 状态转移：首行首列
    for (int a = 1; a <= amt; a++) {
        dp[0][a] = MAX;
        //当无硬币时，**无法凑出任意 >0 的目标金额**，即是无效解。
    }
    // 状态转移：其余行和列
    for (int i = 1; i <= n; i++) {
        for (int a = 1; a <= amt; a++) {
            if (coins[i - 1] > a) {
                // 若超过目标金额，则不选硬币 i
                dp[i][a] = dp[i - 1][a];
            } else {
                // 不选和选硬币 i 这两种方案的较小值
                dp[i][a] = min(dp[i - 1][a], dp[i][a - coins[i - 1]] + 1);
            }
        }
    }
    return dp[n][amt] != MAX ? dp[n][amt] : -1;
}

零钱兑换II

给定 $i$ 种硬币，第$i$ 种硬币的面值为 $coins[i-1]$ ，目标金额为 $amt$ ，每种硬币可以重复选取，问凑出目标金额的硬币组合数量。

  • 类比：“物品”对应“硬币”、“物品重量”对应“硬币面值”、“背包容量”对应“目标金额”。
    • 有点难以理解，换个角度，背包重量要不超过限定，面值要不超过目标金额。
    • 价值要最大，组合数量要最少（最多）。【最优化价值/数量——目标】

当前状态的组合数量等于不选当前硬币与选当前硬币这两种决策的组合数量之和。状态转移方程为：

当目标金额为 0 时，无须选择任何硬币即可凑出目标金额，因此应将首列所有$dp[a,0]$ 都初始化为 1 。当无硬币时，无法凑出任何 >0 的目标金额，因此首行所有$dp[0,a]$ 都等于 0 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* 零钱兑换 II：动态规划 */
int coinChangeIIDP(vector<int> &coins, int amt) {
    int n = coins.size();
    // 初始化 dp 表
    vector<vector<int>> dp(n + 1, vector<int>(amt + 1, 0));
    // 初始化首列
    for (int i = 0; i <= n; i++) {
        dp[i][0] = 1;
    }
    // 状态转移
    for (int i = 1; i <= n; i++) {
        for (int a = 1; a <= amt; a++) {
            if (coins[i - 1] > a) {
                // 若超过目标金额，则不选硬币 i
                dp[i][a] = dp[i - 1][a];
            } else {
                // 不选和选硬币 i 这两种方案之和
                dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1]];
            }
        }
    }
    return dp[n][amt];
}

编辑距离

指两个字符串之间互相转换的最少修改次数，通常用于在信息检索和自然语言处理中度量两个序列的相似度。

输入两个字符串 s 和 t ，返回将 s 转换为 t 所需的最少编辑步数。
你可以在一个字符串中进行三种编辑操作：插入一个字符、删除一个字符、将字符替换为任意一个字符。

从决策树的角度看，本题的目标是求解节点 hello 和节点 algo 之间的最短路径。

【思路】
第一步：思考每轮的决策，定义状态，从而得到dp表

设字符串 s 和 t 的长度分别为 m 和 n ，我们先考虑两字符串尾部的字符 $s[m-1]$ 和 $t[n-1]$ 。

  • 若 $s[m-1]$ 和 $t[n-1]$ 相同，我们可以跳过它们，直接考虑 $s[m-2]$ 和 $t[n-2]$ 。
  • -若 $s[m-1]$ 和 $t[n-1]$ 不同，我们需要对 s 进行一次编辑（插入、删除、替换），使得两字符串尾部的字符相同，从而可以跳过它们，考虑规模更小的问题。

在字符串 s 中进行的每一轮决策（编辑操作），都会使得 s 和 t 中剩余的待匹配字符发生变化。因此，状态为当前在 s 和 t 中考虑的第 i 和第 j 个字符，记为 [i,j] 。

状态 $[i,j]$对应的子问题：将 s 的前 i 个字符更改为 t 的前 j 个字符所需的最少编辑步数。

第二步：找出最优子结构，进而推导出状态转移方程

根据不同编辑操作分为三种情况。

  1. 在 $s[i-1]$ 之后添加 $t[j-1]$ ，则剩余子问题 $dp[i,j-1]$ 。
    • t向前走了一个，所以为-1
  2. 删除 $s[i-1]$ ，则剩余子问题 $dp[i-1,j]$ 。
  3. 将 $s[i-1]$ 替换 $t[j-1]$ ，则剩余子问题$dp[i-1,j-1]$。

状态转移方程为：

注意：要加上本次的编辑步数 1
当 $s[i-1]$ 和 $t[j-1]$ 相同时，无须编辑当前字符

第三步，确定边界
当两字符串都为空时，编辑步数为 0 $dp[0,0]=0$
s空t不为空 $dp[0,j]=j$
s不空t空 $dp[i,0]=i$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/* 编辑距离：动态规划 */
int editDistanceDP(string s, string t) {
    int n = s.length(), m = t.length();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    // 状态转移：首行首列
    for (int i = 1; i <= n; i++) {
        dp[i][0] = i;
    }
    for (int j = 1; j <= m; j++) {
        dp[0][j] = j;
    }
    // 状态转移：其余行和列
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s[i - 1] == t[j - 1]) {
                // 若两字符相等，则直接跳过此两字符
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                // 最少编辑步数 = 插入、删除、替换这三种操作的最少编辑步数 + 1
                dp[i][j] = min(min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
            }
        }
    }
    return dp[n][m];
}

最长子序列 LIS与公共子序列

公共子序列

即求两个序列的并集，但是并集内的元素相对顺序要和原始数据相同

详见——蓝桥杯-1030-蓝肽

dp[i][j]标识第一条序列i和第二序列j的子序列最长

状态转移为

1
2
3
4
5
6
7
if (sta[i] == stb[j])
              // 相同的时候= 前一个匹配+1
              dp[i][j] = dp[i - 1][j - 1] + 1;
          else
              // 否则：为前i-1和前j个字符串重合的最大子串 或者 前i和前j-1个字符串重合的最大子串
              // 注意这里要考虑两方面的内容
              dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

如果需要求连续的最长——只保留第一个if

需要遍历找最大的，最后一个不一定是最大的！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int max_=0;
for (int i = 1; i <= m; i++)
    {
        // 注意这里m还是i好像都可以
        for (int j = 1; j <= i; j++)
        {
            if (s[idx_i][i] == s[idx_j][j])
            {
                dp[i][j] = min(m, dp[i - 1][j - 1] + 1);
                max_ = max(max_, dp[i][j]);
            }
        }
	}
return max_;// 需要遍历找最大的，最后一个不是最大的！

仅需输出长度数

问题描述

给你一个整数数组nums，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例：
输入：nums = [2,1,6,3,5,4]
输出：3
解释：最长递增子序列是 [1,3,4]，因此长度为 3。

分析问题——

对于以第i个数字结尾的最长递增之序列的长度来说，它等于以第j个数字结尾的最长递增子序列的长度的最大值+1，其中 0<j<i，并且nums[j] < nums[i]。

例如，对于以5结尾的最长递增子序列的长度，他等于以3结尾的最长递增子序列的长度+1。

整个数组的最长递增子序列的长度为数组dp中的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = (int)nums.size();
        if (n == 0) {
            return 0;
        }
        vector<int> dp(n, 0);
        for (int i = 0; i < n; ++i) {
            dp[i] = 1;
            for (int j = 0; j < i; ++j) {
                if (nums[j] < nums[i]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }
        return *max_element(dp.begin(), dp.end());
    }
};


优化一下——

可以使用贪心的思想来解决。由于题目是求最长的递增子序列，要想使得递增子序列的长度足够长，就需要让序列上升的尽可能的慢，因此我们希望每次在上升子序列最后加上的那个数尽可能的小。

我们依次遍历数组中的元素，并更新数组d和len的值。如果nums[i] > d[len]，则len=len+1，否则在数组d中，找到第一个比nums[i]小的数d[k]，并更新d[k+1]=nums[i]。

d[i]表示长度为i的递增子序列的末尾元素的最小值,数组d是单调递增的;更新数组d时，我们采用二分查找的方式来定位要更新的位置

你绝对会好奇，如果比如这个改成[2,1,6,0,5,4]，那么d就不是子序列了啊（因为他会把0放到首位去），别急，这里球的是最长递增子序列的长度。因此，即便0替换了1，但是前面一定有一个位置仍然存在，无论0或1，所以递增性质不会被破坏。我们只需要返回方案数量而不是具体方案。

可以通过二分查找找替换的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def lengthOfLIS(nums):
    d = []
    #遍历数组中的元素
    for n in nums:
        #如果n比数组d的最后一个元素大，则加入数组中
        #否则，在d中寻找第一个小于n的元素的位置
        if not d or n > d[-1]:
            d.append(n)
        else:
            l = 0
            r = len(d) - 1
            k = r
            while l <= r:
                mid = (l + r) // 2
                if d[mid] >= n:
                    k = mid
                    r = mid - 1
                else:
                    l = mid + 1
            d[k] = n
    return len(d)

进阶：输出字典序最小

下面我们把题目再修改一下，给定数组nums，设长度为n，输出nums的最长递增子序列。（如果有多个答案，请输出其中按数值进行比较的字典序最小的那个）。

示例：

输入：[1,2,8,6,4]

返回值：[1,2,4]

说明：其最长递增子序列有3个，（1，2，8）、（1，2，6）、（1，2，4）其中第三个按数值进行比较的字典序最小，故答案为（1，2，4）

这里引入一个数组maxlen，用来记录以元素nums[i]结尾的最长递增子序列的长度。从后遍历数组maxlen，如果maxlen[i]=len(d)，我们将对于元素返回结果res中，依次类推，直到遍历完成。

为什么要从后往前遍历数组maxlen呢？
假设我们得到的maxlen为[1,2,3,3,3]，最终的输出结果为res（字典序最小的最长递增子序列），那么res的最后一个元素在nums中位置为maxlen(i)==3
对于的下标i，此时数组nums中有三个元素对应的最长递增子序列的长度为3，即nums[2]、nums[3]和nums[4]，那到底是哪一个呢？
如果是nums[2]，那么nums[2] < nums[4] ，则maxlen[4]=4，与已知条件相悖，
因此我们应该取nums[4]放在res的最后一个位置。所以需要从后先前遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
def lengthOfLIS(nums):
    #最长递增子序列
    d = []
    #记录以nums[i]结尾的最长递增子序列的长度
    maxlen = []
    #遍历数组中的元素
    for n in nums:
        #如果n比数组d的最后一个元素大，则加入数组中
        #否则，在d中寻找第一个小于n的元素的位置
        if not d or n > d[-1]:
            #更新最长递增子序列
            d.append(n)
            #更新以n为结尾元素的最长递增子序列
            maxlen.append(len(d))
        else:
            l = 0
            r = len(d) - 1
            k = r
            while l <= r:
                mid = (l + r) // 2
                if d[mid] >= n:
                    k = mid
                    r = mid - 1
                else:
                    l = mid + 1
            #更新最长递增子序列
            d[k] = n
            #更新以n为结尾元素的最长递增子序列
            maxlen.append(k+1)

    #求解按字典序最小的结果
    #此时我们知道最长长度为len(d)，从后向前遍历maxLen，
    #遇到第一个maxLen[i]==len(d)的下标i处元素arr[i]即为所求
    lens = len(d)
    res = [0] * lens
    for i in range(len(maxlen)-1,-1,-1):
        if maxlen[i]==lens:
            res[lens-1]=nums[i]
            lens=lens-1
    return res

print(lengthOfLIS([1,2,8,6,4]))

贪心

贪心算法 greedy algorithm是一种常见的解决优化问题的算法，其基本思想是在问题的每个决策阶段，都选择当前看起来最优的选择，即贪心地做出局部最优的决策，以期获得全局最优解。

  • 动态规划会根据之前阶段的所有决策来考虑当前决策，并使用过去子问题的解来构建当前子问题的解。
  • 贪心算法不会考虑过去的决策，而是一路向前地进行贪心选择，不断缩小问题范围，直至问题被解决。

贪心不一定最优

再看零钱对换，注意：题目要求，你只要找出一个可行解即可，而非最优解


给定目标金额，我们贪心地选择不大于且最接近它的硬币，不断循环该步骤，直至凑出目标金额为止。

hl:有序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/* 零钱兑换：贪心 */
int coinChangeGreedy(vector<int> &coins, int amt) {
    // 假设 coins 列表有序
    int i = coins.size() - 1;
    int count = 0;
    // 循环进行贪心选择，直到无剩余金额
    while (amt > 0) {
        // 找到小于且最接近剩余金额的硬币
        while (i > 0 && coins[i] > amt) {
            i--;
        }
        // 选择 coins[i]
        amt -= coins[i];
        count++;
    }
    // 若未找到可行方案，则返回 -1
    return amt == 0 ? count : -1;
}

然而，对于某些硬币面值组合，贪心算法并不能找到最优解

贪心算法的适用情况分以下两种。

  1. 可以保证找到最优解：贪心算法在这种情况下往往是最优选择，因为它往往比回溯、动态规划更高效。
  2. 可以找到近似最优解：贪心算法在这种情况下也是可用的。对于很多复杂问题来说，寻找全局最优解非常困难，能以较高效率找到次优解也是非常不错的。

贪心特征

相较于动态规划，贪心算法的使用条件更加苛刻，其主要关注问题的两个性质。

  • 贪心选择性质：只有当局部最优选择始终可以导致全局最优解时，贪心算法才能保证得到最优解。
  • 最优子结构：原问题的最优解包含子问题的最优解。

贪心例题

贪心算法常常应用在满足贪心选择性质和最优子结构的优化问题中，以下列举了一些典型的贪心算法问题。

  • 硬币找零问题：在某些硬币组合下，贪心算法总是可以得到最优解。
    • 人民币对应这些面额的纸币可以贪心！（不考虑分、角）
  • 区间调度问题：假设你有一些任务，每个任务在一段时间内进行，你的目标是完成尽可能多的任务。如果每次都选择结束时间最早的任务，那么贪心算法就可以得到最优解。
  • 分数背包问题：给定一组物品和一个载重量，你的目标是选择一组物品，使得总重量不超过载重量，且总价值最大。如果每次都选择性价比最高（价值 / 重量）的物品，那么贪心算法在一些情况下可以得到最优解。
  • 股票买卖问题：给定一组股票的历史价格，你可以进行多次买卖，但如果你已经持有股票，那么在卖出之前不能再买，目标是获取最大利润。
  • 霍夫曼编码：霍夫曼编码是一种用于无损数据压缩的贪心算法。通过构建霍夫曼树，每次选择出现频率最低的两个节点合并，最后得到的霍夫曼树的带权路径长度（编码长度）最小。
  • Dijkstra 算法：它是一种解决给定源顶点到其余各顶点的最短路径问题的贪心算法。

分数背包问题

给定 $i$ 个物品，第 $i$ 个物品的重量为 $wgt[i-1]$ 、价值为 $val[i-1]$ ，和一个容量为$cap$背包。每个物品只能选择一次，但可以选择物品的一部分，价值根据选择的重量比例计算 问在限定背包容量下能放入物品的最大价值。

我们可以对物品任意地进行切分，并按照重量比例来计算相应价值。

贪心策略：最大化背包内物品总价值，本质上是最大化 单位重量下 的物品价值。

  1. 将物品按照单位价值从高到低进行排序。
  2. 遍历所有物品，每轮贪心地选择单位价值最高的物品。
  3. 若剩余背包容量不足，则使用当前物品的一部分填满背包。
hl:若剩余容量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/* 物品 */
class Item {
  public:
    int w; // 物品重量
    int v; // 物品价值

    Item(int w, int v) : w(w), v(v) {
    }
};

/* 分数背包：贪心 */
double fractionalKnapsack(vector<int> &wgt, vector<int> &val, int cap) {
    // 创建物品列表，包含两个属性：重量、价值
    vector<Item> items;
    for (int i = 0; i < wgt.size(); i++) {
        items.push_back(Item(wgt[i], val[i]));
    }
    // 按照单位价值 item.v / item.w 从高到低进行排序
    sort(items.begin(), items.end(), [](Item &a, Item &b) { return (double)a.v / a.w > (double)b.v / b.w; });
    // 循环贪心选择
    double res = 0;
    for (auto &item : items) {
        if (item.w <= cap) {
            // 若剩余容量充足，则将当前物品整个装进背包
            res += item.v;
            cap -= item.w;
        } else {
            // 若剩余容量不足，则将当前物品的一部分装进背包
            res += (double)item.v / item.w * cap;
            // 已无剩余容量，因此跳出循环
            break;
        }
    }
    return res;
}

最大容量问题

输入一个数组 $ht$ ，其中的每个元素代表一个垂直隔板的高度。数组中的任意两个隔板，以及它们之间的空间可以组成一个容器。

容器的容量等于高度和宽度的乘积（面积），其中高度由较短的隔板决定，宽度是两个隔板的数组索引之差。请在数组中选择两个隔板，使得组成的容器的容量最大，返回最大容量。

长板 向短板 靠近，则容量一定变小。

我们只有向内收缩短板 i ，才有可能使容量变大。因为虽然宽度一定变小，但高度可能会变大（移动后的短板可能会变长）。例如在图 15-10 中，移动短板后面积变大。

  1. 初始状态下，指针 $i$和 $j$ 分列数组两端。
  2. 计算当前状态的容量 $cap[i,j]$ ，并更新最大容量。
  3. 比较板 $i$ 和 板 $j$ 的高度，并将短板向内移动一格。
  4. 循环执行第 2. 步和第 3. 步，直至 $i$ 和 $j$ 相遇时结束。
hl:直至两板相遇,向内移动短板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/* 最大容量：贪心 */
int maxCapacity(vector<int> &ht) {
    // 初始化 i, j，使其分列数组两端
    int i = 0, j = ht.size() - 1;
    // 初始最大容量为 0
    int res = 0;
    // 循环贪心选择，直至两板相遇
    while (i < j) {
        // 更新最大容量
        int cap = min(ht[i], ht[j]) * (j - i);
        res = max(res, cap);
        // 向内移动短板
        if (ht[i] < ht[j]) {
            i++;
        } else {
            j--;
        }
    }
    return res;
}

之所以贪心比穷举更快，是因为每轮的贪心选择都会“跳过”一些状态。

最大切分乘积问题

给定一个正整数 $n$ ，将其切分为至少两个正整数的和，求切分后所有整数的乘积最大是多少

两个整数的乘积往往比它们的加和更大。假设从 n 中分出一个因子 2 ，则它们的乘积为 $2\times (n−2)$。我们将该乘积与 $n$ 作比较：

当 $n\geq 4$ 时，切分出一个 2 后乘积会变大，这说明大于等于 4 的整数都应该被切分。

接下来思考哪个因子是最优的。在 1、2、3 这三个因子中，显然 1 是最差的，因为切分出 1 反而会导致乘积减小。
同时，在切分方案中，最多只应存在两个 2 。因为三个 2 总是可以替换为两个 3 ，从而获得更大的乘积。

综上所述，可推理出以下贪心策略。

  1. 输入整数 n，从其不断地切分出因子 3 ，直至余数为 0、1、2 。
  2. 当余数为 0 时，代表 n 是 3 的倍数，因此不做任何处理。
  3. 当余数为 2 时，不继续划分，保留。
  4. 当余数为 1 时，由于 2×2>1×3 ，因此应将最后一个 3 替换为 2 。
hl:切分
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/* 最大切分乘积：贪心 */
int maxProductCutting(int n) {
    // 当初始给出的 n <= 3 时，必须切分出一个 1
    if (n <= 3) {
        return 1 * (n - 1);
    }
    // 贪心地切分出 3 ，a 为 3 的个数，b 为余数
    int a = n / 3;// a代表有几个3
    int b = n % 3;
    if (b == 1) {
        // 当余数为 1 时，将一对 1 * 3 转化为 2 * 2
        return (int)pow(3, a - 1) * 2 * 2;
    }
    if (b == 2) {
        // 当余数为 2 时，不做处理
        return (int)pow(3, a) * 2;
    }
    // 当余数为 0 时，不做处理
    return (int)pow(3, a);
}

图论

图的遍历

拓扑排序

拓扑排序是一个有向无环图（DAG）的所有顶点的线性序列。而且该序列必须满足下面两个条件：

  • 每个顶点只能出现一次。 即如果存在一条A到B的路径，那么A节点在B节点前面，那么B节点不能在A节点前面。
  • 只有有向无环图才有拓扑排序，如果不是DAG图的话就没有拓扑排序。

思路——

  1. 从 DAG 图中选择入度为1的顶点（即没有节点指向该节点）并输出。
  2. 从图中删除这个节点以及由他发出的有向边，同时针对该节点指向的子节点的入度减一。
  3. 重复第一步和第二步，直到当前的 DAG 图为空或当前图中不存在无前驱的顶点为止。

【基于DFS的拓扑排序】

对于图中的任意一个节点，它在搜索的过程中有三种状态，即：

  • 「未搜索」：我们还没有搜索到这个节点；
  • 「搜索中」：我们搜索过这个节点，但还没有回溯到该节点，即该节点还没有入栈，还有相邻的节点没有搜索完成）；
  • 「已完成」：我们搜索过并且回溯过这个节点，即该节点已经入栈，并且所有该节点的相邻节点都出现在栈的更底部的位置，满足拓扑排序的要求。

我们将当前搜索的节点 $u$ 标记为「搜索中」，遍历该节点的每一个相邻节点$ v$：

  • 如果 $v$为「未搜索」，那么我们开始搜索 $v$，待搜索完成回溯到 $u$；
  • 如果 $v$为「搜索中」，那么我们就找到了图中的一个环，因此是不存在拓扑排序的；
    • 两个都在搜索中，那就是环

  • 如果 $v$ 为「已完成」，那么说明 $v$ 已经在栈中了，而 $u$ 还不在栈中，因此 $u$ 无论何时入栈都不会影响到 $(u, v)$之前的拓扑关系，以及不用进行任何操作。

    当 u 的所有相邻节点都为「已完成」时，我们将 u 放入栈中，并将其标记为「已完成」。

图解——

注意结果是从stack底部到上面读取，底部是（课程）最先学的，（做事）最优先的

数论

  • 同模余
    • 如果 a≡x(mod d),b≡m(mod d),则
      1) $a+b≡x+m （mod d）$
      2) $a-b≡x-m(mod d)$
      3) $ab≡xm(mod d )$

中国剩余定理

中国剩余定理（Chinese Remainder Theorem, CRT）是数论中的一个重要定理，它涉及同余方程组的求解。CRT指出，如果有一组两两互质的模数$n_1, n_2, …, n_k$，那么对于任意的整数$a_1, a_2, …, a_k$，同余方程组

都有一个唯一解模$N = n_1n_2…n_k$。换句话说，这个方程组在模$N$下有解，并且这个解是唯一的。
CRT的解法通常包括以下步骤：

  1. 计算乘积：首先计算所有模数的乘积$N = n_1n_2…n_k$。
  2. 求逆元：对于每个i从1到k，计算$M_i = N / n_i$和$M_i$关于$n_i$的乘法逆元$M_i^{-1}$。
  3. 合成解：最后，合成方程组的解为CRT在密码学中有着重要的应用，例如在RSA累加器中，它可以用来提高计算效率。通过CRT，可以将模$n$（其中$n$是两个大质数的乘积）的运算分解为模这两个质数的运算，这样可以减少计算量，因为直接在大数上操作通常非常耗时。

假设我们有两个同余方程：

  1. $x \equiv 2 \pmod{3}$
  2. $x \equiv 3 \pmod{5}$
    我们想要找到一个数$x$，它同时满足这两个条件。
    首先，我们找到两个模数的乘积：$N = 3 \times 5 = 15$。
    接下来，我们为每个模数计算乘积 $N$ 除以该模数的结果，并找到这个结果的乘法逆元：
  3. 对于 $n_1 = 3$，$M_1 = N / n_1 = 15 / 3 = 5$。我们需要找到 $5$ 关于 $3$ 的乘法逆元，即 $5 \times ? \equiv 1 \pmod{3}$。在这个例子中，逆元是 $2$，因为 $5 \times 2 = 10 \equiv 1 \pmod{3}$。
  4. 对于 $n_2 = 5$，$M_2 = N / n_2 = 15 / 5 = 3$。我们需要找到 $3$ 关于 $5$ 的乘法逆元，即 $3 \times ? \equiv 1 \pmod{5}$。在这个例子中，逆元是 $2$，因为 $3 \times 2 = 6 \equiv 1 \pmod{5}$。
    现在我们有了所有需要的部分，我们可以计算 $x$：所以，$x = 7$ 是满足这两个同余方程的最小非负整数解。这意味着 $7$ 除以 $3$ 的余数是 $2$，且 $7$ 除以 $5$ 的余数是 $2$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
int n,a[11],b[11];
ull sum=1,t[11],ans; 
int main()
{
	cin>>n;
	for(int i=1; i<=n; i++) {
		cin>>a[i]>>b[i];// 模a余b
		sum*=a[i];
	} 
	for(int i=1; i<=n; i++) t[i]=sum/a[i];
	for(int i=1; i<=n; i++) 
		for(ull j=t[i]; j<=0x7f7f7f7f7f7f; j+=t[i]) 
		    if(j%a[i]==1) {
		    // 没懂
			    ans+=j*b[i]%sum;
			    break;
			}
	cout<<ans%sum;
	return 0;
}

代码2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod[15],yu[15],M = 1,ans;//mod[i]即为mi,yu[i]存放模后余数

void exGcd(ll a,ll b,ll &x,ll &y){   //求解 ax+by = gcd(a,b)，注意是传引用
    if(b == 0) { x = 1,y = 0; return;}         // b = 0时,a = gcd(原a,原b)
    exGcd(b,a%b,x,y);
    ll temX = x;
    x = y,y = temX - a/b * y;   //x = y', y = x' - a/b * y' (x'和y'是递归下一层返回后的x和y)
}
/*void exGcd(ll a,ll b,ll &x,ll &y){  //更简洁的写法
    if(b == 0) { x = 1,y = 0; return;}
    exGcd(b,a%b,y,x);           //x和y换位
    y = y- a/b*x;
}*/
int main() {
    int n;
    cin>>n;       //方程组数
    for (int i = 1; i <= n ; ++i) {
        scanf("%ld %ld",&mod[i],&yu[i]);  //模数和余数，模数互质
        M*=mod[i];
    }
    for (int i = 1; i <= n ; ++i) {
        ll Mi = M / mod[i],inv,y; // Mi为所有模数乘积除以第i个模数，inv为Mi在模mi意义下的逆元
        exGcd(Mi, mod[i], inv, y);
        inv = inv % mod[i];
        ans = (ans + yu[i] * Mi * inv) % M;
    }
    cout<< (ans + M) % M;          //保证结果不出现负数
    return 0;
}

最大公约数

如果是分数化简，每个数字还要除以公约数

1
2
3
4
5
6
7
8
9
10
int gcd(int a,int b){
// 辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。
	if(a%b!=0){
		gcd(b,a%b);
	}
	else {
		return b;
	}

}

最小公倍数

$LCM(x,y)=x*y/gcd(x,y)$

素数筛

前置：判断素数

1
2
3
4
5
6
7
8
9
for (int j = 2; j <= sqrt(i); j++) 
{
	// i是要测的树
	if (i % j == 0) {
	//如果找到了约数
	flag = 1;//说明不是素数
	break;
	}
}

欧拉线性筛

对于每个数删掉他的倍数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void EulerSevie(int n)
{
    for(int i = 2;i <= n; ++i)//老规矩，遍历区间
    {
        if(isVisit[i] == false) //如果这个数未被访问，则是素数
            prime[++c] = i;     //将素数保存在素数数组里面，计数+1
        //下面for循环及里面的语句才是这个算法的精髓，我们下面细讲
        for(int j = 1;j <= c && i * prime[j] <= n; ++j)
        {
            isVisit[i * prime[j] ] = true;
            if (i % prime[j] == 0)
                break;
        }
    }
}

快速幂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
typedef long long ll;//命别名，方便书写
ll qspow(ll a,ll b){      //递归写法
     if(b==0)return 1;
     ll res=qspow(a*a,(b>>1));   //对正整数右移，等效于/2
     if(b&1) res=res*a;        //b&1,b为奇数则结果为true
     // 在快速幂算法中，当 𝑏b 为奇数时，会额外乘以一次 𝑎a。
     return res;               //为偶数则为false
}

// 第二种写法
long long quickPow(int base, int exponent) {
    long long result = 1;
    while (exponent > 0) {
        // 如果指数是奇数，那么最后乘以基数，最后会*此
        if (exponent % 2 == 1) {
            result *= base;
        }
        // 基数平方，指数减半
        base *= base;
        exponent /= 2; // 使用整除得到下一个指数
    }
    return result;
}

扩展欧几里得算法

求解$ax+by=gcd(a,b)$

https://blog.csdn.net/H_Elden/article/details/132221322

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;
int exgcd(int a, int b, int &x, int &y) {		//以传址的方式返回两个参数
	if (!b) {
		x = 1, y = 0;
		return a;
	}
	int d = exgcd(b, a % b, y, x);
	y -= a / b * x;
	return d;
}
int main() {
	int a, b, x, y;
	scanf("%d%d", &a, &b);
	exgcd(a, b, x, y);
	printf("%d %d\n", x, y);
	return 0;
}

数字特征

最大公约数与互质

1
2
3
4
5
6
7
int gcd(int x, int y)
{
    if (x % y == 0)
        return y; // 如果 x 可以被 y 整除，则 y 是最大公约数
    else
        return gcd(y, x % y); // 否则，递归地计算 y 和 x%y 的最大公约数
}

如果互质，即判断gcd==1即可

一维数组中到各点最短的

是中位数！不是平均数！

一维数组中到各个点最短的是中位数

数字各位数字之和

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * 计算各位数字的和
 */
int SumOfEveryPosition(int n)
{
    int t = 0;
    while (n)
    {
        t = t + n % 10; // 计算位数之和
        n /= 10;
    }
    return t;
}

进制转换

10转换X

1
2
3
4
5
6
7
8
9
10
//H是一个数组，转为二进制
while(n){ 
    char w=n%x+'0';
    if(w<10)
		H.push_back(w); 
	else
		H.push_back(w-10+'A').
	n/ =2;
}
// 记得反序输出！！！

X转10

1
2
3
4
5
6
7
for (int i = 0; i < len; i++) 
{
	ans = ans * x;
	if (s[i] >= '0' && s[i] <= '9') 
		ans += (s[i] - '0');
	else ans += (s[i] - 'A') + 10;
}

计算组合数

1
2
3
4
5
6
7
8
9
// 计算组合数 C(n, k)
unsigned long long comb(int n, int k) {
    unsigned long long result = 1;
    for (int i = 1; i <= k; ++i) {
        result *= n - i + 1;
        result /= i;
    }
    return result;
}

字符串

  • 字符串/字符转数字
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
s[s.size() - 1] - '0'// 字符转数字


//字符串转为整数,通过减'0'字符,底层用ASCII码相减 
void myAtoi(char str[],long long& m){  
	int i(0);
	int temp = 0;
	while(str[i] != '\0'){
		temp = temp*10 + (str[i] -'0');
		++i;
	}
	m = temp; //转换后赋值给m
} 



//or
for (char c : sum) 
	result = (result * 10 + (c - '0')) % MOD;