Acwing - 算法基础课 - 笔记(一) àì夳堔傛蜴生んèń 2022-10-21 03:43 200阅读 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 赞/ 162 阅读
还没有评论,来说两句吧...