基础算法 - 快速排序、归并排序、二分查找、高精度模板、离散化数据

文章目录

  • 前言
  • Part 1：排序
  • Part 2：二分
    • 一、二分 - 查找左边界
    • 二、二分 - 查找右边界
  • Part 3：高精度
    • 一、高精度加法
    • 二、高精度减法
    • 三、高精度乘法
    • 四、高精度除法
  • Part 4：离散化
    • 一、区间和

前言

由于本篇博客相较而言都是算法中最基础的模板，包括快速排序、归并排序、二分、高精度加减乘除法、离散化。这些基础模板多与其他算法混合考察，这些模板是许多算法的实现基础。

Part 1：排序

快速排序和归并排序都属于分治思想，分治分为三步：

1.分成子问题
2.递归处理子问题
3.子问题合并

一、快速排序

  • 核心思想是：是将问题划分为子问题的过程中不断解决。不断根据一个分割点，交换前后数据，使得前一部分小于分割点，后一部分大于分割点，分割点在两部分中间，再根据分割位置将其分为两部分重新进行此操作，直到无法再分
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];
    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);

    //第三步：子问题合并.快排这一步不需要操作，但归并排序的核心在这一步骤
}

二、归并排序

  • 核心思想：不断将问题划分为子问题，再从子问题开始操作，累加出问题的答案。将数组不断划分为两部分，在无法划分时，将每个分治最后一次划分的两部分合并排序，重复从小问题向原问题操作，合并为排序答案
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, tmp[r - l + 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(k = 0, i = l; i <= r; k++, i++) q[i] = tmp[k];
}

Part 2：二分

一般二分应用于无非下面这四种情况:
1：找大于等于数的第一个位置 （满足某个条件的第一个数）- 左边界
2：找小于等于数的最后一个数 （满足某个条件的最后一个数）- 右边界
3.查找最大值 （满足该边界的右边界）- 右边界
4.查找最小值 (满足该边界的左边界) - 左边界

一、二分 - 查找左边界

//查找左边界 SearchLeft 简写SL
int SL(int l, int r)
{
   while (l < r)
   {
       int mid = l + r >> 1;
       if (check(mid)) r = mid; 
       else l = mid + 1; 
   }   
   return l;
}

二、二分 - 查找右边界

//查找右边界 SearchRight 简写SR 
int SR(int l, int r) 
{
    while (l < r)
    {                   
        int mid = l + r + 1 >> 1; //需要+1 防止死循环
        if (check(mid)) l = mid;
        else r = mid - 1; 
    }
    return r; 
}

总结以下记忆方式：有加必有减！！！

int mid = l + r + 1 >> 1; //+1为加
if (check(mid)) l = mid;
else r = mid - 1; //-1为减

Part 3：高精度

一、高精度加法

#include <iostream>
#include <vector>

using namespace std;

vector<int> add(vector<int> &A, vector<int> &B)
{
    //为了方便计算，让A中保存较长的数字， B中保存较短的数字
    if (A.size() < B.size()) return add(B, A);
    //保存结果的数组
    vector<int> C;
    //进位，开始时是0
    int t = 0;
    
    //依次计算每一位
    for (int i = 0; i < A.size(); i ++ )
    {
        t += A[i];//加上 A 的第 i 位上的数字
        if (i < B.size()) t += B[i];//加上 B 的第 i 位上的数字
        C.push_back(t % 10); //C 中放入结果
        t /= 10;//t 更新成进位
    }
    //最后如果进位上有数，放进结果数组
    if (t) C.push_back(t);
    
    return C;//返回结果
}

int main()
{
    string a, b;//以字符串形式保存输入的两个整数
    vector<int> A, B;//保存两个整数的数组
    cin >> a >> b;//接收输入
    
    for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');//倒序存储第一个数
    for (int i = b.size() - 1; i >= 0; i -- ) B.push_back(b[i] - '0');//倒序存储第二个数
    
    auto C = add(A, B);//调用加和函数
    for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i];//倒序输出C中的数字
    
    cout << endl;
    
    return 0;
}

二、高精度减法

#include <iostream>
#include <vector>

using namespace std;

bool cmp(vector<int>& A, vector<int> &B)
{
    if(A.size() != B.size()) return A.size() > B.size();  //直接ruturn 了就不用else

    for(int i = A.size(); i >= 0; i--)
        if(A[i] != B[i])
            return A[i] > B[i];

    return true;
}

vector <int> sub(vector<int>& A, vector<int> &B)
{
    vector<int> C;
    int t = 0;
    for(int i = 0; i < A.size(); i++)
    {
        t = A[i] - t;
        if(i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10 ); // 合而为1
        if(t < 0)  t = 1;
        else t = 0;

    }

    while(C.size() > 1 && C.back() == 0) C.pop_back();  //去掉前导0

    return C;
}

int main()
{
    string a ,b;
    vector<int> A, B;

    cin >> a >> b ;

    for(int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    for(int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');

    if (cmp(A,B)) 
    {
        auto C = sub(A, B);
        for(int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
        return 0;
    }
    else
    {
        auto C = sub(B, A);
        printf("-");
        for(int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
        return 0;
    }
}

三、高精度乘法

高精度 X 低精度

#include <iostream>
#include <vector>

using namespace std;

vector <int> mul(vector <int> & A, int b) 
{
    vector <int> C;

    int t = 0;
    for (int i = 0; i < A.size(); i ++) 
    {
        t += A[i] * b;       // t + A[i] * b = 7218
        C.push_back(t % 10); // 只取个位 8
        t /= 10;             // 721 看作 进位
    }

	// 处理最后剩余的 t
    while (t) 
    {            
        C.push_back(t % 10);
        t /= 10;
    }

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

    return C;
}

int main() {
    string a;
    int b;
    cin >> a >> b;

    vector <int> A;
    for (int i = a.size() - 1; i >= 0; i --) A.push_back(a[i] - '0');

    auto C = mul(A, b);

    for (int i = C.size() - 1; i >= 0; i --) 
    {
        cout << C[i];
    }

    return 0;
}

高精度 X 高精度

#include <iostream>
#include <vector>

using namespace std;

vector<int> mul(vector<int> &A, vector<int> &B) 
{
    vector<int> C(A.size() + B.size() + 7, 0); // 初始化为 0，C的size可以大一点

    for (int i = 0; i < A.size(); i++)
        for (int j = 0; j < B.size(); j++)
            C[i + j] += A[i] * B[j];

    int t = 0;
    for (int i = 0; i < C.size(); i++) // i = C.size() - 1时 t 一定小于 10
    {
        t += C[i];
        C[i] = t % 10;
        t /= 10;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back(); // 必须要去前导 0，因为最高位很可能是 0
    return C;
}

int main() 
{
    string a, b;
    cin >> a >> b; // a = "1222323", b = "2323423423"

    vector<int> A, B;
    for (int i = a.size() - 1; i >= 0; i--)
        A.push_back(a[i] - '0');
    for (int i = b.size() - 1; i >= 0; i--)
        B.push_back(b[i] - '0');

    auto C = mul(A, B);

    for (int i = C.size() - 1; i >= 0; i--)
        cout << C[i];

    return 0;
}

大数相加A+B和大数相乘A*B通用模板

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> add(vector<int> A, vector<int> B) 
{
    // A: 4 3 2 1
    // B: 6 5
    vector<int> C(max(A.size(), B.size()) + 7, 0);  // 数组C开大一点没事，反正可以去前导零的
    for (int i = 0; i < A.size(); i ++) C[i] += A[i];
    for (int i = 0; i < B.size(); i ++) C[i] += B[i];

    // 处理进位
    for (int i = 0; i + 1 < C.size(); i ++) 
    {
        C[i + 1] += C[i] / 10;
        C[i] %= 10;
    }

    // 处理前导零
    while (C.size() > 1 && C.back() == 0) C.pop_back();

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

vector<int> mul(vector<int> A, vector<int> B) 
{
    // A: 4 3 2 1
    // B: 6 5
    vector<int> C(A.size() + B.size() + 7, 0);  // 数组C开大一点没事，反正可以去前导零的
    for (int i = 0; i < A.size(); i ++) 
    {
        for (int j = 0; j < B.size(); j ++) 
        {
            C[i + j] += A[i] * B[j];
        }
    }

    // 处理进位
    for (int i = 0; i + 1 < C.size(); i ++) 
    {
        C[i + 1] += C[i] / 10;
        C[i] %= 10;
    }

    // 处理前导零 "0000" 去掉前导零
    while (C.size() > 1 && C.back() == 0) C.pop_back();

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

int main() 
{
    string s1 = "9899", s2 = "100";

    vector<int> A, B;
    for (int i = s1.size() - 1; i >= 0; i --) A.push_back(s1[i] - '0');
    for (int i = s2.size() - 1; i >= 0; i --) B.push_back(s2[i] - '0');

    vector<int> C = add(A, B);
    cout << s1 << "+" << s2 << "=";
    for (int i = 0; i < C.size(); i ++) cout << C[i];
    cout << endl;

    C = mul(A, B);
    cout << s1 << "*" << s2 << "=";
    for (int i = 0; i < C.size(); i ++) cout << C[i];
    cout << endl;

    return 0;
}

四、高精度除法

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

//int r=0;
vector<int> div(vector<int> &A,int B,int &r)//r传入r的地址，便于直接对余数r进行修改
{
    vector<int> C;

	//对A从最高位开始处理
    for(int i=0;i<A.size();i++)
    {
        r=r*10+A[i];//将上次的余数*10在加上当前位的数字，便是该位需要除的被除数
        C.push_back(r/B);//所得即为商在这一位的数字
        r=r%B;
    }
    //由于在除法运算中，高位到低位运算，因此C的前导零都在vector的前面而不是尾部，vector只有删除最后一个数字pop_back是常数复杂度，而对于删除第一位没有相应的库函数可以使用，而且删除第一位，其余位也要前移，
    //因此我们将C翻转，这样0就位于数组尾部，可以使用pop函数删除前导0
    reverse(C.begin(),C.end());
    while(C.size()>1&&C.back()==0) C.pop_back();
    
    return C;
}

int main()
{
    string a;
    int B,r=0; //代表余数
    cin>>a>>B;
    
    vector<int> A;
    for(int i=0;i<a.size();i++) A.push_back(a[i]-'0');//注意这次的A是由高为传输至低位，由于在除法的手算过程中，发现从高位进行处理
    //for(int i=0;i<A.size();i++) cout<<A[i];
    //cout<<B;
    auto C = div(A,B,r);
    for(int i=C.size()-1;i>=0;i--) cout<<C[i];//将C从最高位传给最低位
    
    cout<<endl<<r;//输出余数
    cout<<endl;
    
    return 0;
}

Part 4：离散化

一、区间和

题目描述：假定有一个无限长的数轴，数轴上每个坐标上的数都是 0。现在，我们首先进行 n 次操作，每次操作将某一位置 x 上的数加 c。接下来，进行 m 次询问，每个询问包含两个整数 l 和 r，你需要求出在区间 [l,r] 之间的所有数的和。

输入：第一行包含两个整数 n 和 m。接下来 n 行，每行包含两个整数 x 和 c。再接下来 m 行，每行包含两个整数 l 和 r。
输出：共 m 行，每行输出一个询问中所求的区间内数字和。

  • 离散化的本质，是映射，将间隔很大的点，映射到相邻的数组元素中。减少对空间的需求，也减少计算量
  • 该题解决办法就是开辟额外的数组存放原来的数组下标，或者说下标标志，本文是原来上的数轴上的非连续点的横坐标。此处的做法是是对原来的数轴下标进行排序，再去重，根据二分得到该数在开辟的连续数组中的位置
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 300010; //n次插入和m次查询相关数据量的上界

int n, m;
int a[N];//存储坐标插入的值
int s[N];//存储数组a的前缀和
vector<int> alls;  //存储（所有与插入和查询有关的）坐标
vector<pair<int, int>> add, query; //存储插入和询问操作的数据

//返回的是输入的坐标的离散化下标
int find(int 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;
}

int main() 
{
    scanf("%d%d", &n, &m);
    
    for (int i = 1; i <= n; i++) 
    {
        int x, c;
        scanf("%d%d", &x, &c);
        add.push_back({x, c});
        alls.push_back(x);
    }
    for (int i = 1; i <= m; i++) 
    {
        int l , r;
        scanf("%d%d", &l, &r);
        query.push_back({l, r});
        alls.push_back(l);
        alls.push_back(r);
    }
    
   //排序，去重
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());
    
    //执行前n次插入操作
    for (auto item : add) 
    {
        int x = find(item.first);
        a[x] += item.second;
    }
    //前缀和
    for (int i = 1; i <= alls.size(); i++) s[i] = s[i-1] + a[i];
    
    //处理后m次询问操作
    for (auto item : query) 
    {
        int l = find(item.first);
        int r = find(item.second);
        printf("%d\n", s[r] - s[l-1]);
    }

    return 0;
}

http://www.niftyadmin.cn/n/5405326.html

相关文章

算法D27｜回溯算法4｜ 93.复原IP地址 78.子集 90.子集II

算法D27｜回溯算法4｜ 93.复原IP地址 78.子集 90.子集II

93.复原IP地址 本期本来是很有难度的&#xff0c;不过 大家做完 分割回文串 之后&#xff0c;本题就容易很多了 题目链接/文章讲解&#xff1a;代码随想录 视频讲解&#xff1a;回溯算法如何分割字符串并判断是合法IP&#xff1f;| LeetCode&#xff1a;93.复原IP地址_哔哩哔…
阅读更多...
2024高频前端面试题 HTML 和 CSS 篇

2024高频前端面试题 HTML 和 CSS 篇

JS和ES6 篇&#xff1a; ​​​​​​​2024高频前端面试题 JavaScript 和 ES6 篇-CSDN博客 一 . HTML 篇 1. H5有什么新特性 1) 语义化标签 用正确的标签做正确的事情。 html 语义化让页面的内容结构化&#xff0c;结构更清晰&#xff0c;便于对浏览器、搜索引擎解析&…
阅读更多...
Linux中docker项目提示No such file or directory

Linux中docker项目提示No such file or directory

本来以为是文件权限问题&#xff0c;后来发现是个非常蠢的问题 文件没有映射到容器中 docker文件映射语法 Docker 使用 -v 或 --volume 参数来指定文件映射。 增加在运行命令后 -v <宿主机目录>:<容器目录> 其中&#xff0c;宿主机目录 是指要映射的宿主机上的…
阅读更多...
[C++核心编程]（七）：类和对象——运算符重载*

[C++核心编程]（七）：类和对象——运算符重载*

目录 四则运算符重载 左移运算符重载 递增运算符重载 赋值运算符重载 关系运算符重载 函数调用运算符重载 对已有的运算符重新进行定义&#xff0c;赋予其另一种功能&#xff0c;以适应不同的数据类型 四则运算符重载 对自定义数据类型实现四则运算&#xff08;加减乘除&…
阅读更多...
AI大预言模型——ChatGPT在地学、GIS、气象、农业、生态、环境应用

AI大预言模型——ChatGPT在地学、GIS、气象、农业、生态、环境应用

原文链接&#xff1a;AI大预言模型——ChatGPT在地学、GIS、气象、农业、生态、环境应用 一开启大模型 1 开启大模型 1)大模型的发展历程与最新功能 2)大模型的强大功能与应用场景 3)国内外经典大模型&#xff08;ChatGPT、LLaMA、Gemini、DALLE、Midjourney、Stable Diff…
阅读更多...
韦东山嵌入式Liunx入门驱动开发五

韦东山嵌入式Liunx入门驱动开发五

文章目录 一、驱动程序基石1-1 休眠与唤醒1-2 POLL机制1-3 异步通知(1) 异步通知程序解析(2) 异步通知机制内核代码详解 1-4 阻塞与非阻塞1-5 定时器(1) 内核函数(2) 定时器时间单位 1-6 中断下半部 tasklet 本人学习完韦老师的视频&#xff0c;因此来复习巩固&#xff0c;写以…
阅读更多...
模型部署 - BevFusion - (1) - 思路总结

模型部署 - BevFusion - (1) - 思路总结

模型部署实践 - BevFusion 思路总结一、网络结构 - 总结1.1、代码1.2、网络流程图1.3、模块大致梳理 二、Onnx 的导出 -总体思路分析三、优化思路总结 学习 BevFusion 的部署&#xff0c;看了很多的资料&#xff0c;这篇博客进行总结和记录自己的实践 思路总结 对于一个模型我…
阅读更多...
LeetCode 100231.超过阈值的最少操作数 I

LeetCode 100231.超过阈值的最少操作数 I

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。 一次操作中&#xff0c;你可以删除 nums 中的最小元素。 你需要使数组中的所有元素都大于或等于 k &#xff0c;请你返回需要的 最少 操作次数。 示例 1&#xff1a; 输入&#xff1a;nums [2,11,10,1,3], k 10 输…
阅读更多...
最新文章

Copyright @ 2022~2023