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

目录
相关文章
|
1月前
|
算法 索引
❤️算法笔记❤️-(每日一刷-141、环形链表)
❤️算法笔记❤️-(每日一刷-141、环形链表)
46 0
|
1月前
|
算法 API 计算机视觉
人脸识别笔记(一):通过yuface调包(参数量54K更快更小更准的算法) 来实现人脸识别
本文介绍了YuNet系列人脸检测算法的优化和使用,包括YuNet-s和YuNet-n,以及通过yuface库和onnx在不同场景下实现人脸检测的方法。
39 1
|
1月前
|
JSON 算法 数据可视化
测试专项笔记(一): 通过算法能力接口返回的检测结果完成相关指标的计算(目标检测)
这篇文章是关于如何通过算法接口返回的目标检测结果来计算性能指标的笔记。它涵盖了任务描述、指标分析(包括TP、FP、FN、TN、精准率和召回率),接口处理,数据集处理,以及如何使用实用工具进行文件操作和数据可视化。文章还提供了一些Python代码示例,用于处理图像文件、转换数据格式以及计算目标检测的性能指标。
61 0
测试专项笔记(一): 通过算法能力接口返回的检测结果完成相关指标的计算(目标检测)
|
1月前
|
算法
❤️算法笔记❤️-(每日一刷-160、相交链表)
❤️算法笔记❤️-(每日一刷-160、相交链表)
17 1
|
1月前
|
数据可视化 搜索推荐 Python
Leecode 刷题笔记之可视化六大排序算法:冒泡、快速、归并、插入、选择、桶排序
这篇文章是关于LeetCode刷题笔记,主要介绍了六大排序算法(冒泡、快速、归并、插入、选择、桶排序)的Python实现及其可视化过程。
14 0
|
1月前
|
算法
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
31 0
|
1月前
|
算法
❤️算法笔记❤️-(每日一刷-26、删除有序数组的重复项)
❤️算法笔记❤️-(每日一刷-26、删除有序数组的重复项)
23 0
|
27天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
12天前
|
算法 数据挖掘 数据安全/隐私保护
基于FCM模糊聚类算法的图像分割matlab仿真
本项目展示了基于模糊C均值(FCM)算法的图像分割技术。算法运行效果良好,无水印。使用MATLAB 2022a开发,提供完整代码及中文注释,附带操作步骤视频。FCM算法通过隶属度矩阵和聚类中心矩阵实现图像分割,适用于灰度和彩色图像,广泛应用于医学影像、遥感图像等领域。
|
13天前
|
算法 调度
基于遗传模拟退火混合优化算法的车间作业最优调度matlab仿真,输出甘特图
车间作业调度问题(JSSP)通过遗传算法(GA)和模拟退火算法(SA)优化多个作业在并行工作中心上的加工顺序和时间,以最小化总完成时间和机器闲置时间。MATLAB2022a版本运行测试,展示了有效性和可行性。核心程序采用作业列表表示法,结合遗传操作和模拟退火过程,提高算法性能。