Acwing - 算法基础课 - 笔记（一） àì夳堔傛蜴生んèń 2022-10-21 03:43 183阅读 0赞 ### 文章目录 ### * * 基础算法（一） * * 排序 * * 快排 * * 衍生题目：求第k个数 * 归并 * * 衍生题目：逆序对的数量 * 二分 * * 整数二分 * 浮点数二分 ## 基础算法（一） ## 本节讲解的是排序和二分，排序讲解了**快排**和**归并**，二分讲解了**整数二分**和**浮点数二分**。 ### 排序 ### #### 快排 #### `quick_sort(int q[], int l, int r)` `q`是待排序数组，`l`是待排序区间的左边界，`r`是右边界 * 基本思路 1. 选取一个基准值`x` 可以取左边界的值`q[l]`，或右边界的值`q[r]`，或者中间位置的值`q[l + r >> 1]` 2. ⭐️根据基准值，调整区间，使得左半边区间的值全都`≤x`，右半边区间的值全都`≥x` 采用双指针，左指针`i`从左边界`l`开始，往右扫描，右指针`j`从右边界`r`开始，往左扫描。 当满足条件`q[i] < x`时，`i`右移；直到不满足条件时，`i`停下；开始移动`j` 当满足条件`q[j] > x`时，`j`左移；直到不满足条件时，`j`停下；交换`q[i]`和`q[j]`； 将`i`右移一位，`j`左移一位。 重复上面的操作，直到`i`和`j`相遇。此时左半区间的数都满足`≤x`，且左半区间的最后一个数的下标为`j`，右半区间的数都满足`≥x`，且右半区间的第一个数的下标为`i`。`i`和`j`之间的关系为：`i = j + 1`或`i = j` 3. 对左右两边的区间，做递归操作 递归操作`[l, j]`，`[j + 1, r]`区间，或者`[l, i - 1]`，`[i, r]`区间即可 * 算法题目 [Acwing - 785 快速排序][Acwing - 785] #include<iostream> using namespace std; const int N = 100010; int n; int q[N]; void quick_sort(int q[], int l, int r) { if(l >= r) return; // 递归退出条件, 不要写成 l == r, 可能会出现 l > r 的情况，可以尝试用例[1,2] int x = q[l + r >> 1], i = l - 1, j = r + 1; // 这里 i 置为 l - 1, j 置为 r + 1, 是因为下面更新i, j 时采用了do while循环, while(i < j) { // 这里不要写成 i <= j do i++; while(q[i] < x);// 不能写为 <= x , 那样写 i 可能会越界, 考虑 [1,1,1]。 // 因为基准值x是数组中的一个数，i从左往右移动的过程中，一定会遇到这个数x，此时不满足小于条件, i 一定会停下，也就变相保证了 i 不会越界。 do j--; while(q[j] > x);// 不能写为 >= x , 因为 j 可能会越界, 原因同上 if(i < j) swap(q[i], q[j]); // 若 i 和 j 还未相遇, 则交换2个数 } quick_sort(q, l, j); quick_sort(q, j + 1, r); } int main() { scanf("%d", &n); for(int i = 0; i < n; i++) scanf("%d", &q[i]); quick_sort(q, 0, n - 1); for(int i = 0; i < n; i++) printf("%d ", q[i]); } * 注意要点 当区间划分结束后，左指针`i`和右指针`j`的相对位置，只有2种情况 * `i` = `j + 1` * `i` = `j`（此时`i`和`j`指向的元素，恰好等于基准值`x`） 若用`j`来作为区间的分界，则`[l, j]` 都是`≤x`，`[j + 1, r]`都是`≥x` 若用`i`来作为区间的分界，则`[l, i - 1]`都是`≤x`，`[i, r]`都是`≥x` 当取`i`作为分界的话，基准值`x`不能取到左边界`q[l]`，否则会出现死循环，比如用例`[1,2]`。此时基准值可以取`q[r]`，或者`q[l + r + 1 >> 1]`，注意取中间位置的数时，要加个`1`，避免`l + r >> 1`的结果为`l` 当取`j`作为分界的话，基准值`x`不能取到右边界`q[r]`，否则会出现死循环。此时基准值可以取`q[l]`，或者`q[l + r >> 1]` * 算法模板 // 任选一种模板进行记忆即可, 下面采用: 基准值取中间位置, 递归时使用j作分界 void quick_sort(int q[], int l, int r) { if(l >= r) return; int x = q[l + r >> 1], i = l - 1, j = r + 1; while(i < j) { do i++; while(q[i] < x); do j--; while(q[j] > x); if(i < j) swap(q[i], q[j]); } quick_sort(q, l, j); quick_sort(q, j + 1, r); } * 思想总结 1. 选一个值`x` 2. 以该值为分界点，将数组分为左右两部分，左边的全都`≤x`，右边的全都`≥x` 3. 对左右两部分进行递归操作 ##### 衍生题目：求第k个数 ##### 练习题：[Acwing - 786 第k个数][Acwing - 786 _k] #include<iostream> using namespace std; const int N = 1e5 +10; int n, k; int q[N]; // 选取[l, r]区间内数组q第k小的数 int quick_select(int q[], int l, int r, int k) { if(l == r) return q[l]; // 找到答案 int x = q[l + r >> 1], i = l - 1, j = r + 1; while(i < j) { while(q[++i] < x); while(q[--j] > x); if(i < j) swap(q[i], q[j]); } int left = j - l + 1; if(k <= left) return quick_select(q, l, j, k); else return quick_select(q, j + 1, r, k - left); } int main() { scanf("%d%d", &n, &k); for(int i = 0; i < n; i++) scanf("%d", &q[i]); printf("%d", quick_select(q, 0, n - 1, k)); return 0; } #### 归并 #### `merge_sort(int q[], int l, int r)` * 基本思路 1. 确定分界点，一般是中间位置 2. 从分界点将数组切成两半，对左右两部分做递归排序 3. ⭐️将左右两部分区间合并成一个区间（将2个有序数组，合并成1个有序数组，使用双指针即可） * 算法题目 [Acwing - 787 归并排序][Acwing - 787] #include<iostream> using namespace std; const int N = 1e6 + 10; int n; int q[N], tmp[N]; void merge_sort(int q[], int l, int r) { if(l >= r) return; int mid = l + r >> 1; merge_sort(q, l, mid); merge_sort(q, mid + 1, r); // 合并 int i = l, j = mid + 1, k = 0; while(i <= mid && j <= r) { if(q[i] <= q[j]) tmp[k++] = q[i++]; else tmp[k++] = q[j++]; } while(i <= mid) tmp[k++] = q[i++]; while(j <= r) tmp[k++] = q[j++]; for(i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j]; } int main() { scanf("%d", &n); for(int i = 0; i < n; i++) scanf("%d", &q[i]); merge_sort(q, 0, n - 1); for(int i = 0; i < n; i++) printf("%d ", q[i]); } ##### 衍生题目：逆序对的数量 ##### 练习题：[Acwing - 788: 逆序对的数量][Acwing - 788_] #include<iostream> using namespace std; typedef long long LL; const int N = 1e5 + 10; int n; int q[N], tmp[N]; // 返回区间[l, r]中的逆序对的数量 LL merge_sort(int q[], int l, int r) { if(l >= r) return 0; int mid = l + r >> 1; LL cnt = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r); // 计算左右区间内各自的逆序对数量 // 合并时, 计算左右两个区间中的数组成的逆序对 int i = l, j = mid + 1, k = 0; while(i <= mid && j <= r) { if(q[i] <= q[j]) tmp[k++] = q[i++]; else { cnt += mid - i + 1; tmp[k++] = q[j++]; } } while(i <= mid) tmp[k++] = q[i++]; while(j <= r) tmp[k++] = q[j++]; for(int i = l, k = 0; i <= r; i++, k++) q[i] = tmp[k]; return cnt; } int main() { scanf("%d", &n); for(int i = 0; i < n; i++) scanf("%d", &q[i]); LL cnt = merge_sort(q, 0, n - 1); printf("%lld", cnt); return 0; } ### 二分 ### #### 整数二分 #### * 算法模板 int binary_search_1(int l, int r) { while(l < r) { int mid = l + r >> 1; if(check(mid)) r = mid; else l = mid + 1; } return l; } int binary_search_2(int l, int r) { while(l < r) { int mid = l + r + 1 >> 1; // 当下面是 l = mid 这样来更新的话，这里计算mid时要多加1，否则会出现边界问题 if(check(mid)) l = mid; else r = mid - 1; } return l; } * 二分的本质 注意：**二分的本质不是单调性**。单调性可以理解为函数单调性，如一个数组是升序排列或降序排列，此时可以用二分来查找某一个数的位置。 有单调性一定可以二分，但没有单调性，也有可能能够二分。 **二分的本质是边界**。假设给定一个区间，如果能够根据某个条件，将区间划分为左右两部分，使得左半边满足这个条件，右半边不满足这个条件（或者反之）。此时就可以用二分来查找左右两部分的边界点。 ![20210503142141251.png][] 注意左右两半部分的边界不是同一个点，而是相邻的2个点，因为是整数二分（离散的）。上面的2个算法模板，就分别对应了**求左半部分的边界**（上图红色区域最右边的点），和**求右半部分的边界**（上图绿色区域最左边的点） 比如，我们要找上图中左边红色部分的边界点，我们取`mid = l + r >> 1`，判断一下`q[mid]`是否满足条件x，若满足，说明`mid`位置在红色区域内，我们的答案在`mid`右侧（可以取到`mid`），即`[mid, r]`，则此时更新`l = mid`；若`q[mid]`不满足条件x，则说明`mid`位置在右边的绿色区域，我们的答案在`mid`左侧（不能取到`mid`），即`[l, mid - 1]`，此时更新`r = mid - 1`。 注意，当采用`l = mid`和`r = mid - 1`这种更新方式时，计算`mid`时，要加上1（向上取整），即`mid = l + r + 1 >> 1`。否则，在`l = r - 1`时，计算`mid`时若不加1，则`mid = l + r >> 1 = l`，这样更新`l = mid`，就是`l = l`，会导致死循环。所以要向上取整，采用`mid = l + r + 1 >> 1`。 同理，当采用`r = mid` 和 `l = mid + 1`这种更新方式时，计算`mid`时不能加1，在`l = r - 1`时，若计算`mid`时加1，则`mid = l + r + 1 >> 1 = r`，这样更新`r = mid`。就是`r = r`，会导致死循环。 简单的记忆就是，仅当采用`l = mid`这种更新方式时，计算`mid`时需要加1。 练习题：[Acwing-789:数的范围][Acwing-789] #include<iostream> using namespace std; const int N = 100010; int arr[N]; int n,q; int main() { scanf("%d%d", &n, &q); for(int i = 0; i < n; i++) scanf("%d", &arr[i]); while(q--) { int k; scanf("%d", &k); int l = 0, r = n - 1; while(l < r) { int mid = l + r >> 1; if(arr[mid] >= k) r = mid; else l = mid + 1; } if(arr[l] != k) printf("-1 -1\n"); else { printf("%d ", l); l = 0, r = n - 1; while(l < r) { int mid = l + r + 1 >> 1; if(arr[mid] <= k) l = mid; else r = mid - 1; } printf("%d\n", l); } } } #### 浮点数二分 #### 相比**整数二分**，**浮点数二分**无需考虑边界问题，比较简单。 当二分的区间足够小时，可以认为已经找到了答案，如当`r - l < 1e-6`，停止二分。 或者直接迭代一定的次数，比如循环100次后停止二分。 练习题：[Acwing-790:数的三次方根][Acwing-790] #include<iostream> using namespace std; int main() { double n; scanf("%lf", &n); double l = -10000, r = 10000; while(r - l > 1e-8) { double mid = (l + r) / 2; if(mid * mid * mid >= n) r = mid; else l = mid; } printf("%.6f", l); } [Acwing - 785]: https://www.acwing.com/problem/content/787/ [Acwing - 786 _k]: https://www.acwing.com/problem/content/description/788/ [Acwing - 787]: https://www.acwing.com/problem/content/789/ [Acwing - 788_]: https://www.acwing.com/problem/content/790/ [20210503142141251.png]: /images/20221021/41d7a5b796dd438fb6963eb2d065c2cb.png [Acwing-789]: https://www.acwing.com/problem/content/791/ [Acwing-790]: https://www.acwing.com/problem/content/792/
相关 Acwing - 算法基础课 - 笔记（五） 文章目录 数据结构（二） Trie树 练习题：\[Acwing - 835: Trie字符串统计\](http 约定不等于承诺〃/ 2022年10月06日 04:59/ 0 赞/ 151 阅读
冷不防
àì夳堔傛蜴生んèń
今天药忘吃喽~
还没有评论，来说两句吧...