AcWing算法基础课笔记 第一章 基础算法

简介: ​编辑快速排序算法模板 —— 模板题 AcWing 785. 快速排序归并排序算法模板 —— 模板题 AcWing 787. 归并排序整数二分算法模板 —— 模板题 AcWing 789. 数的范围浮点数二分算法模板 —— 模板题 AcWing 790. 数的三次方根高精度加法 —— 模板题 AcWing 791. 高精度加法高精度减法 —— 模板题 AcWing 792. 高精度减法高精度乘低精度 —— 模板题 AcWing 793. 高精度乘法高精度除以低精度 —— 模板题 AcWing 794. 高精度除法一维前缀和 —— 模板题 AcWing 795.


3.png

3.png

快速排序算法模板 —— 模板题 AcWing 785. 快速排序


分治的思想   (先分完再去递归两边)

4.png

较为粗暴:

5.png


优雅:


利用好两个指针来分组:6.png7.png8.png


void quick_sort(int q[], int l, int r)

{

   if (l >= r) return;

   int i = l - 1, j = r + 1, x = q[l + r >> 1];//先往中间进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);

}

归并排序算法模板 —— 模板题 AcWing 787. 归并排序


分治    先递归两边再去排3

9.png



时间复杂度:

10.png




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 = l, j = mid + 1;

   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];

}



整数二分算法模板 —— 模板题 AcWing 789. 数的范围


先用check去看mid等于什么去选择模版


11.png12.png




bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用:

int bsearch_1(int l, int r)

{

   while (l < r)

   {

       int mid = l + r >> 1;

       if (check(mid)) r = mid;    // check()判断mid是否满足性质

       else l = mid + 1;

   }

   return l;

}

// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用:

int bsearch_2(int l, int r)

{

   while (l < r)

   {

       int mid = l + r + 1 >> 1;

       if (check(mid)) l = mid;

       else r = mid - 1;

   }

   return l;

}


浮点数二分算法模板 —— 模板题 AcWing 790. 数的三次方根


bool check(double x) {/* ... */} // 检查x是否满足某种性质

double bsearch_3(double l, double r)

{

   const double eps = 1e-6;   // eps 表示精度,取决于题目对精度的要求(比要求的多2一般不会有问题)

   while (r - l > eps)

   {

       double mid = (l + r) / 2;

       if (check(mid)) r = mid;

       else l = mid;

   }

   return l;

}


高精度加法 —— 模板题 AcWing 791. 高精度加法


13.png14.png



// C = A + B, A >= 0, B >= 0

vector<int> add(vector<int> &A, vector<int> &B)

{

   if (A.size() < B.size()) return add(B, A);

   vector<int> C;

   int t = 0;

   for (int i = 0; i < A.size(); i ++ )

   {

       t += A[i];

       if (i < B.size()) t += B[i];

       C.push_back(t % 10);

       t /= 10;

   }

   if (t) C.push_back(t);

   return C;

}


高精度减法 —— 模板题 AcWing 792. 高精度减法


15.png

// C = A - B, 满足A >= B, A >= 0, B >= 0

vector<int> sub(vector<int> &A, vector<int> &B)

{

   vector<int> C;

   for (int i = 0, t = 0; i < A.size(); i ++ )

   {

       t = A[i] - t;

       if (i < B.size()) t -= B[i];

       C.push_back((t + 10) % 10);

       if (t < 0) t = 1;

       else t = 0;

   }

   while (C.size() > 1 && C.back() == 0) C.pop_back();

   return C;

}

高精度乘低精度 —— 模板题 AcWing 793. 高精度乘法

// C = A * b, A >= 0, b > 0

vector<int> mul(vector<int> &A, int b)

{

   vector<int> C;

   int t = 0;

   for (int i = 0; i < A.size() || t; i ++ )

   {

       if (i < A.size()) t += A[i] * b;

       C.push_back(t % 10);

       t /= 10;

   }

   return C;

}


高精度除以低精度 —— 模板题 AcWing 794. 高精度除法



// A / b = C ... r, A >= 0, b > 0

vector<int> div(vector<int> &A, int b, int &r)

{

   vector<int> C;

   r = 0;

   for (int i = A.size() - 1; i >= 0; i -- )

   {

       r = r * 10 + A[i];

       C.push_back(r / b);

       r %= b;

   }

   reverse(C.begin(), C.end());

   while (C.size() > 1 && C.back() == 0) C.pop_back();

   return C;

}

一维前缀和 —— 模板题 AcWing 795. 前缀和


S[i] = a[1] + a[2] + ... a[i]

a[l] + ... + a[r] = S[r] - S[l - 1]


二维前缀和 —— 模板题 AcWing 796. 子矩阵的和


S[i, j] = 第i行j列格子左上部分所有元素的和

以(x1, y1)为左上角,(x2, y2)为右下角的子矩阵的和为:

S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]


一维差分 —— 模板题 AcWing 797. 差分


给区间[l, r]中的每个数加上c:B[l] += c, B[r + 1] -= c


二维差分 —— 模板题 AcWing 798. 差分矩阵


给以(x1, y1)为左上角,(x2, y2)为右下角的子矩阵中的所有元素加上c:

S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c

位运算 —— 模板题 AcWing 801. 二进制中1的个数

求n的第k位数字: n >> k & 1

返回n的最后一位1:lowbit(n) = n & -n


双指针算法 —— 模板题 AcWIng 799. 最长连续不重复子序列, AcWing 800. 数组元素的目标和


for (int i = 0, j = 0; i < n; i ++ )

{

   while (j < i && check(i, j)) j ++ ;

   // 具体问题的逻辑

}

常见问题分类:

   (1) 对于一个序列,用两个指针维护一段区间

   (2) 对于两个序列,维护某种次序,比如归并排序中合并两个有序序列的操作

离散化 —— 模板题 AcWing 802. 区间和

vector<int> alls; // 存储所有待离散化的值

sort(alls.begin(), alls.end()); // 将所有值排序

alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素

// 二分求出x对应的离散化的值

int find(int x) // 找到第一个大于等于x的位置

{

   int l = 0, r = alls.size() - 1;

   while (l < r)

   {

       int mid = l + r >> 1;

       if (alls[mid] >= x) r = mid;

       else l = mid + 1;

   }

   return r + 1; // 映射到1, 2, ...n

}

区间合并 —— 模板题 AcWing 803. 区间合并


// 将所有存在交集的区间合并

void merge(vector<PII> &segs)

{

   vector<PII> res;

   sort(segs.begin(), segs.end());

   int st = -2e9, ed = -2e9;

   for (auto seg : segs)

       if (ed < seg.first)

       {

           if (st != -2e9) res.push_back({st, ed});

           st = seg.first, ed = seg.second;

       }

       else ed = max(ed, seg.second);

   if (st != -2e9) res.push_back({st, ed});

   segs = res;

}

111.jpg112.jpg

目录
相关文章
|
4月前
|
JSON 算法 数据可视化
测试专项笔记(一): 通过算法能力接口返回的检测结果完成相关指标的计算(目标检测)
这篇文章是关于如何通过算法接口返回的目标检测结果来计算性能指标的笔记。它涵盖了任务描述、指标分析(包括TP、FP、FN、TN、精准率和召回率),接口处理,数据集处理,以及如何使用实用工具进行文件操作和数据可视化。文章还提供了一些Python代码示例,用于处理图像文件、转换数据格式以及计算目标检测的性能指标。
110 0
测试专项笔记(一): 通过算法能力接口返回的检测结果完成相关指标的计算(目标检测)
|
4月前
|
算法 API 计算机视觉
人脸识别笔记(一):通过yuface调包(参数量54K更快更小更准的算法) 来实现人脸识别
本文介绍了YuNet系列人脸检测算法的优化和使用,包括YuNet-s和YuNet-n,以及通过yuface库和onnx在不同场景下实现人脸检测的方法。
140 1
|
4月前
|
数据可视化 搜索推荐 Python
Leecode 刷题笔记之可视化六大排序算法:冒泡、快速、归并、插入、选择、桶排序
这篇文章是关于LeetCode刷题笔记,主要介绍了六大排序算法(冒泡、快速、归并、插入、选择、桶排序)的Python实现及其可视化过程。
42 0
|
4月前
|
算法
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
47 0
|
4月前
|
算法
❤️算法笔记❤️-(每日一刷-26、删除有序数组的重复项)
❤️算法笔记❤️-(每日一刷-26、删除有序数组的重复项)
54 0
|
4月前
|
算法
❤️算法笔记❤️-(每日一刷-160、相交链表)
❤️算法笔记❤️-(每日一刷-160、相交链表)
33 1
|
4月前
|
算法 索引
❤️算法笔记❤️-(每日一刷-141、环形链表)
❤️算法笔记❤️-(每日一刷-141、环形链表)
71 0
|
1天前
|
传感器 算法
基于GA遗传算法的多机无源定位系统GDOP优化matlab仿真
本项目基于遗传算法(GA)优化多机无源定位系统的GDOP,使用MATLAB2022A进行仿真。通过遗传算法的选择、交叉和变异操作,迭代优化传感器配置,最小化GDOP值,提高定位精度。仿真输出包括GDOP优化结果、遗传算法收敛曲线及三维空间坐标点分布图。核心程序实现了染色体编码、适应度评估、遗传操作等关键步骤,最终展示优化后的传感器布局及其性能。
|
2天前
|
机器学习/深度学习 算法 安全
基于深度学习的路面裂缝检测算法matlab仿真
本项目基于YOLOv2算法实现高效的路面裂缝检测,使用Matlab 2022a开发。完整程序运行效果无水印,核心代码配有详细中文注释及操作视频。通过深度学习技术,将目标检测转化为回归问题,直接预测裂缝位置和类别,大幅提升检测效率与准确性。适用于实时检测任务,确保道路安全维护。 简介涵盖了算法理论、数据集准备、网络训练及检测过程,采用Darknet-19卷积神经网络结构,结合随机梯度下降算法进行训练。
|
3天前
|
算法 数据可视化 数据安全/隐私保护
一级倒立摆平衡控制系统MATLAB仿真,可显示倒立摆平衡动画,对比极点配置,线性二次型,PID,PI及PD五种算法
本课题基于MATLAB对一级倒立摆控制系统进行升级仿真,增加了PI、PD控制器,并对比了极点配置、线性二次型、PID、PI及PD五种算法的控制效果。通过GUI界面显示倒立摆动画和控制输出曲线,展示了不同控制器在偏转角和小车位移变化上的性能差异。理论部分介绍了倒立摆系统的力学模型,包括小车和杆的动力学方程。核心程序实现了不同控制算法的选择与仿真结果的可视化。
31 15

热门文章

最新文章