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月前
|
算法 索引
❤️算法笔记❤️-(每日一刷-141、环形链表)
❤️算法笔记❤️-(每日一刷-141、环形链表)
71 0
|
4月前
|
算法 API 计算机视觉
人脸识别笔记(一):通过yuface调包(参数量54K更快更小更准的算法) 来实现人脸识别
本文介绍了YuNet系列人脸检测算法的优化和使用,包括YuNet-s和YuNet-n,以及通过yuface库和onnx在不同场景下实现人脸检测的方法。
140 1
|
4月前
|
算法
❤️算法笔记❤️-(每日一刷-160、相交链表)
❤️算法笔记❤️-(每日一刷-160、相交链表)
33 1
|
4月前
|
JSON 算法 数据可视化
测试专项笔记(一): 通过算法能力接口返回的检测结果完成相关指标的计算(目标检测)
这篇文章是关于如何通过算法接口返回的目标检测结果来计算性能指标的笔记。它涵盖了任务描述、指标分析(包括TP、FP、FN、TN、精准率和召回率),接口处理,数据集处理,以及如何使用实用工具进行文件操作和数据可视化。文章还提供了一些Python代码示例,用于处理图像文件、转换数据格式以及计算目标检测的性能指标。
110 0
测试专项笔记(一): 通过算法能力接口返回的检测结果完成相关指标的计算(目标检测)
|
4月前
|
数据可视化 搜索推荐 Python
Leecode 刷题笔记之可视化六大排序算法:冒泡、快速、归并、插入、选择、桶排序
这篇文章是关于LeetCode刷题笔记,主要介绍了六大排序算法(冒泡、快速、归并、插入、选择、桶排序)的Python实现及其可视化过程。
42 0
|
4月前
|
算法
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
47 0
|
4月前
|
算法
❤️算法笔记❤️-(每日一刷-26、删除有序数组的重复项)
❤️算法笔记❤️-(每日一刷-26、删除有序数组的重复项)
54 0
|
4天前
|
算法 数据安全/隐私保护 计算机视觉
基于FPGA的图像双线性插值算法verilog实现,包括tb测试文件和MATLAB辅助验证
本项目展示了256×256图像通过双线性插值放大至512×512的效果,无水印展示。使用Matlab 2022a和Vivado 2019.2开发,提供完整代码及详细中文注释、操作视频。核心程序实现图像缩放,并在Matlab中验证效果。双线性插值算法通过FPGA高效实现图像缩放,确保质量。
|
1月前
|
算法 数据安全/隐私保护 计算机视觉
基于Retinex算法的图像去雾matlab仿真
本项目展示了基于Retinex算法的图像去雾技术。完整程序运行效果无水印,使用Matlab2022a开发。核心代码包含详细中文注释和操作步骤视频。Retinex理论由Edwin Land提出,旨在分离图像的光照和反射分量,增强图像对比度、颜色和细节,尤其在雾天条件下表现优异,有效解决图像去雾问题。
|
1月前
|
算法 数据可视化 安全
基于DWA优化算法的机器人路径规划matlab仿真
本项目基于DWA优化算法实现机器人路径规划的MATLAB仿真,适用于动态环境下的自主导航。使用MATLAB2022A版本运行,展示路径规划和预测结果。核心代码通过散点图和轨迹图可视化路径点及预测路径。DWA算法通过定义速度空间、采样候选动作并评估其优劣(目标方向性、障碍物距离、速度一致性),实时调整机器人运动参数,确保安全避障并接近目标。
148 68

热门文章

最新文章