经过千锤百炼的算法模版
2021/6/17 22:27:43
本文主要是介绍经过千锤百炼的算法模版,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
起始语
平时写算法的时候,很多时候思路有了,但是边界问题总是傻傻搞不清楚。所以找了一些经过千锤百炼的模版来帮助代码。持续更新中。。。
方便自己在通勤路上,记忆一下模版,所以发在了博客上。
算法基础
排序
快速排序
把每个比基准值大的值放到右边,比基准值小的值放到左边,再分别左右快速排序
void quick_sort(int q[], int l, int r) { if (l >= r) return; int x = q[l], i = l - 1, j = r + 1; //这里基准点l必须上取整,不然会死循环 // 假如是 1,2 进行快速排序,会出现排序一次后,左边界是 [0,-1], 右边是[0,2],会一直死循环 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); }
归并排序
- 确定分界点 mid = (l + r) / 2
- 归并排序 left right
- 归并 - 合二为一
const int N = 1000010; int n; int q[N], tem[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 k = 0, i = 1, j = mid + 1; while (i <= mid && j <= r) if (q[i] <= q[j]) tmp[k ++] = q[i ++]; else tem[k ++] = q[j ++]; while (i <= mid) tem[k ++] = q[i ++]; while (j <= r) tem[k ++] = q[j ++]; for (int i = l, j = 0; i <= r; i ++, j ++) q[i] = tem[j]; }
二分查找
int bsearch_1(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 bsearch_2(int l, int r) { while (l < r) { int mid = l + r + 1 >> 1; //除法是下取整,如果不加1 且 l = r - 1,那么区间[l, r]会变成区间[l, r]会进入死循环,因为 mid = l + r >> 1 = l + 1 + l >> 1 = l。所以当 l = mid 时,需要补偿 1 if (check(mid)) l = mid; // l = mid 的话需要 + 1 else r = mid - 1; } return l; }
这篇关于经过千锤百炼的算法模版的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-06小米11i印度快充版ROM合集:极致体验,超越期待
- 2024-10-06【ROM下载】小米11i 5G 印度版系统, 疾速跃迁,定义新速度
- 2024-10-06【ROM下载】小米 11 青春活力版,青春无极限,活力全开
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求