算法基础课——基础算法(模板整理)

这篇具有很好参考价值的文章主要介绍了算法基础课——基础算法(模板整理)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

 快速排序

快速排序

#include <iostream>
#include <algorithm>
using namespace std;
int n;
int s[100000];
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>s[i];
    }
    sort(s,s+n);
    for(int i=0;i<n;i++)
    {
        cout<<s[i]<<" ";
    }
    cout<<endl;
    return 0;
}

第K个数

#include <iostream>
#include <algorithm>
using namespace std;
int a[100005];
int main()
{
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    nth_element(a+1,a+k,a+1+n);
    cout<<a[k]<<endl;
    return 0;
}

归并排序 

归并排序

#include <iostream>
using namespace std;
const int N = 100010;
int n;
int q[N],tmp[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=1,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(int i=l,j=1;i<=r;i++,j++)
    {
        q[i]=tmp[j];
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&q[i]);
    }
    merge_sort(q,1,n);
    for(int i=1;i<=n;i++)
    {
        printf("%d ",q[i]);
    }
    return 0;
}

逆序对的数量

#include <iostream>
using namespace std;
typedef long long ll;
const int N = 100010;
int n;
int q[N],tmp[N];
ll merge_sort(int l,int r)
{
    if(l>=r)
    {
        return 0;
    }
    int mid = (l+r)>>1;
    ll res=merge_sort(l,mid)+merge_sort(mid+1,r);
    //归并的过程
    int k=1,i=l,j=mid+1;
    while(i<=mid&&j<=r)
    {
        if(q[i]<=q[j])
        {
            tmp[k++]=q[i++];
        }
        else
        {
            tmp[k++]=q[j++];
            res+=(mid-i+1);
        }
    }
    //扫尾
    while(i<=mid)
    {
        tmp[k++]=q[i++];
    }
    while(j<=r)
    {
        tmp[k++]=q[j++];
    }
    //物归原主
    for(int i=l,j=1;i<=r;i++,j++)
    {
        q[i]=tmp[j];
    }
    return res;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>q[i];
    }
    cout<<merge_sort(1,n)<<endl;
    return 0;
}

二分 

数的范围

#include <iostream>
using namespace std;
const int N = 100010;
int q[N];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        cin>>q[i];
    }
    while(m--)
    {
        int x;
        cin>>x;
        int l=0,r=n-1;
        while(l<r)
        {
            int mid=l+r>>1;
            if(q[mid]>=x)
            {
                r=mid;
            }
            else l=mid+1;
        }
        if(q[l]!=x)
        {
            cout<<"-1 -1"<<endl;
        }
        else
        {
            cout<<l<<" ";
            l=0;r=n-1;
            while(l<r)
            {
                int mid=l+r+1>>1;
                if(q[mid]<=x)
                {
                    l=mid;
                }
                else r=mid-1;
            }
            cout<<l<<endl;
        }
    }
    return 0;
}

数的三次方根

#include <iostream>
using namespace std;
int main()
{
    double n;
    cin>>n;
    double l=-10000,r=10000;
    while(r-l>1e-8)
    {
        double mid = (l+r)/2;
        if(mid*mid*mid>=n)
        {
            r=mid;
        }
        else l=mid;
    }
    printf("%.6lf\n",l);
    return 0;
}

高精度

 高精度加法

Python一行就可以解决

print(int(input())+int(input()))
#include <iostream>
#include <string>
#include <vector>
using namespace std;
vector<int> add(vector<int> &A,vector<int> &B)
{
    vector<int>C;
    int t=0;
    for(int i=0;i<A.size()||i<B.size();i++)
    {
        if(i<A.size())
        {
            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;
}
int main()
{
    string a,b;
    cin>>a>>b;
    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 = add(A,B);
    for(int i=C.size()-1;i>=0;i--)
    {
        cout<<C[i];
    }
    return 0;
}

高精度减法

#include <iostream>
#include <string>
#include <vector>
using namespace std;
//判断是否有A>=B
bool cmp(vector<int> &A,vector<int> &B)
{
    if(A.size()!=B.size())
    {
        return A.size()>B.size();
    }
    for(int i=A.size()-1;i>=0;i--)
    {
        if(A[i]!=B[i])
        {
            return A[i]>B[i];
        }
    }
    return true;
}
//C=A-B
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);
        if(t<0)
        {
            t=1;
        }
        else t=0;
    }
    while(C.size()>1&&C.back()==0)
    {
        C.pop_back();
    }
    return C;
}
int main()
{
    string a,b;
    cin>>a>>b;
    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');
    }
    if(cmp(A,B))
    {
        auto C = sub(A,B);
        for(int i=C.size()-1;i>=0;i--)
        {
            cout<<C[i];
        }
    }
    else
    {
        auto C = sub(B,A);
        cout<<"-";
        for(int i=C.size()-1;i>=0;i--)
        {
            cout<<C[i];
        }
    }
    return 0;
}

高精度乘法

#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() || t; i++)
    {
        if (i < A.size())
        {
            t += A[i] * b;
        }
        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;
}

高精度除法

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
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;
}
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');
    }
    int r;
    auto C = div(A, b,r);
    for (int i = C.size() - 1; i >= 0; i--)
    {
        cout << C[i];
    }
    cout<<endl<<r<<endl;
    return 0;
}

前缀和与差分

前缀和

#include <iostream>
using namespace std;
const int N = 100005;
int a[N],s[N];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=n;i++)
    {
        s[i]=s[i-1]+a[i];
    }
    while(m--)
    {
        int l,r;
        cin>>l>>r;
        cout<<s[r]-s[l-1]<<endl;
    }
    return 0;
}

子矩阵的和

#include <iostream>
using namespace std;
const int N = 1010;
int a[N][N], s[N][N];
int main() 
{
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            scanf("%d", &a[i][j]);
            s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + a[i][j]; // 求前缀和
        }
    while (q--) 
    {
        int x1,y1,x2,y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        // 算子矩阵的和
        printf("%d\n", s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]); 
    }
    return 0;
}

差分

#include <iostream>
using namespace std;
const int N = 100010;
int n,m;
int a[N],b[N];
void insert(int l,int r,int c)
{
    b[l]+=c;
    b[r+1]-=c;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=n;i++)
    {
        insert(i,i,a[i]);
    }
    while(m--)
    {
        int l,r,c;
        cin>>l>>r>>c;
        insert(l,r,c);
    }
    for(int i=1;i<=n;i++)
    {
        b[i]+=b[i-1];
    }
    for(int i=1;i<=n;i++)
    {
        cout<<b[i]<<" ";
    }
    return 0;
}

差分矩阵

#include <iostream>
using namespace std;
const int N = 1010;
int n,m,q;
int a[N][N],b[N][N];
void insert(int x1,int y1,int x2,int y2,int c)
{
    b[x1][y1]+=c;
    b[x2+1][y1]-=c;
    b[x1][y2+1]-=c;
    b[x2+1][y2+1]+=c;
}
int main()
{
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            insert(i,j,i,j,a[i][j]);
        }
    }
    while(q--)
    {
        int x1,y1,x2,y2,c;
        cin>>x1>>y1>>x2>>y2>>c;
        insert(x1,y1,x2,y2,c);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1];
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cout<<b[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

双指针算法

最长连续不重复子序列

#include <iostream>
using namespace std;
const int N = 100010;
int n;
int a[N],s[N];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    int res=0;
    for(int i=1,j=1;i<=n;i++)
    {
        s[a[i]]++;
        while(s[a[i]]>1)
        {
            s[a[j]]--;
            j++;
        }
        res=max(res,i-j+1);
    }
    cout<<res<<endl;
    return 0;
}

数组元素的目标和

#include <iostream>
using namespace std;
const int N = 100005;
int n,m,x;
int a[N],b[N];
int main()
{
    cin>>n>>m>>x;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=m;i++)
    {
        cin>>b[i];
    }
    for(int i=1,j=m;i<=n;i++)
    {
        while(j>=1&&a[i]+b[j]>x) j--;
        if(a[i]+b[j]==x)
        {
            cout<<i-1<<" "<<j-1<<endl;
            break;
        }
    }
    return 0;
}

判断子序列

#include <iostream>
using namespace std;
const int N = 100005;
int n,m;
int a[N],b[N];
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    for(int i=0;i<m;i++)
    {
        cin>>b[i];
    }
    int i=0,j=0;
    while(i<n&&j<m)
    {
        if(a[i]==b[j])i++;
        j++;
    }
    if(i==n)
    {
        cout<<"Yes"<<endl;
    }
    else
    {
        cout<<"No"<<endl;
    }
    return 0;
}

位运算

二进制中1的个数

#include <iostream>
using namespace std;
int lowbit(int x)
{
    return x & -x;
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int x;
        cin>>x;
        int res=0;
        while(x)
        {
            x-=lowbit(x);
            res++;
        }
        cout<<res<<" ";
    }
    return 0;
}

离散化

区间和

#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;
}

区间和并文章来源地址https://www.toymoban.com/news/detail-660497.html

区间和并

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int,int>pii;
const int N = 100010;
int n;
vector<pii>segs;
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(ed!=-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});
    cout<<res.size()<<endl;
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int l,r;
        cin>>l>>r;
        segs.push_back({l,r});
    }
    merge(segs);
    return 0;
}

到了这里,关于算法基础课——基础算法(模板整理)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • acwing算法基础课(第三讲 搜索与图论)

    void dfs(int u){ if(n == u){ for(int i = 0;i n;i++) puts(g[i]); puts(“”); return; } for(int i = 0;i n;i++){ if(!col[i] !dg[u+i] !udg[n - u + i]){ g[u][i] = ‘Q’; col[i] = dg[u+i] = udg[n - u + i] = true; dfs(u+1); col[i] = dg[u+i] = udg[n - u + i] = false; g[u][i] = ‘.’; } } } int main(){ scanf(“%d”,n); for(int i = 0;i n;i++){ for(int j = 0;j

    2024年04月10日
    浏览(54)
  • 假期学习资源:WEB网页网站开发入门基础课

    HTML入门到精通视频教程免费下载  链接: https://pan.baidu.com/s/1NyBZOgy6Iyolo2qXL819vg?pwd=adfc 提取码: adfc HTML5基础知识教程视频教程免费下载 链接: https://pan.baidu.com/s/129pvlmnYdMyT9FhWd14KEw?pwd=icbv 提取码: icbv CSS零基础入门到精通视频教程免费下载  链接: https://pan.baidu.com/s/1VbZONTL9Ez-ZDyZnC

    2024年02月13日
    浏览(42)
  • 【AcWing算法基础课】第三章 搜索与图论

    本专栏文章为本人AcWing算法基础课的学习笔记,课程地址在这。如有侵权,立即删除。 特点 :尽可能先向 纵深方向 搜索。使用 stack 实现。所需空间 O(h) (h为深度)。不具有“最短性”。 题目链接 :842. 排列数字 1.1题目描述 给定一个整数 n,将数字 1∼n 排成一排,将会有

    2024年02月12日
    浏览(68)
  • 【AcWing算法基础课】第五章 动态规划(未完待续)

    本专栏文章为本人AcWing算法基础课的学习笔记,课程地址在这。如有侵权,立即删除。 dp问题的优化 :在基本形式dp上作等价变形。 dp问题的解题方法 : 1)状态表示 集合 属性:最大值/最小值/数量。 2)状态计算 集合划分(不重不漏) 题目链接: 2. 01背包问题 - AcWing题库

    2024年02月12日
    浏览(73)
  • 【AcWing算法基础课】第二章 数据结构(部分待更)

    本专栏文章为本人AcWing算法基础课的学习笔记,课程地址在这。如有侵权,立即删除。 邻接表 :存储图和树 e数组存储每个结点的值,ne数组存储每个结点的指向的下一个结点。 数组模拟链表比较快,指针模拟会涉及到new操作,比较慢。 题目链接 :826. 单链表 1.1题目描述

    2024年02月13日
    浏览(50)
  • AcWing 算法基础课二 数据结构 链表 栈 队列 并查集 哈希表

    链表题目:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 AcWing. 826.单链表 双链表 AcWing 827.双链表 AcWing 828.模拟栈 AcWing 3302.表达式求值 AcWing 829. 模拟队列 AcWing 830.单调栈 AcWing 154.滑动窗口 AcWing 831. KMP字符串 AcWing 835. Trie字符串统计 AcWing 143. 最大异或对 AcWing 836.合并集合

    2024年02月15日
    浏览(50)
  • 基础课14——语音识别

    ASR 是自动语音识别 (Automatic Speech Recognition)的缩写,是一种将 人类语音转换为文本的技术 。ASR 系统可以处理实时音频流或已录制的音频文件,并将其转换为文本。它是一种自然语言处理技术, 广泛应用于许多领域, 包括电话语音助手、语音转文本、语音搜索等。 ASR 的工

    2024年02月03日
    浏览(59)
  • 基础课21——知识库管理

    智能客服中的知识库是一个以知识为基础的系统,可以明确地表达与实际问题相对应的知识,并构成相对独立的程序行为主体,有利于有效、准确地解决实际问题。它储存着机器人对所有信息的认知概念和理解,这些信息以数据的形式储存在数据库中,在需要的时候匹配地调

    2024年02月05日
    浏览(46)
  • java基础课后习题答案

    一、 1.对象 2.面向对象、跨平台性 3.javac 4.Java虚拟机(或JVM) 5.JRE 二、 1.错 2.错 3.错 4.对 5.对 三、 1.C 2.ABCD 3.D 4.ABD 5.D 四、 1.简答性、面向对象、安全性、跨平台性、支持多线程、分布性。 2. Java程序运行时,必须经过编译和运行两个步骤。首先将后

    2024年01月21日
    浏览(47)
  • Hadoop大数据开发基础课后答案

    本书为中国工信出版集团的《Hadoop大数据开发基础》 一、选择题 1.HDFS中的文件块默认保存(C)份。 B.2 A.1 C.3 D.不确定 2.启动集群的顺序为(A) ① start-dfs.sh ② start-yarn.sh ③ mr-jobhistory-daemon.sh start historyserver A.① ② ③ B.② ① ③ C.③ ② ① D.③ ① ② 3.关闭集群的顺序为(B)

    2024年02月07日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包