头像

康泰克斯特很重要


访客:511

离线:2天前



常用的排序算法

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin>>n;
    vector<int> nums;
    for(int i=0;i<n;i++)
    {
        int c;
        cin>>c;
        nums.push_back(c);
    }

    count_sort(nums,0,n-1);
    for(auto c:nums)
    {
        cout<<c<<' ';
    }
    return 0;
}

快速排序

void quick_sort(vector<int>&nums,int l,int r)
{
    if(l>=r) return;
    int mid=nums[(l+r)>>1];
    int i=l-1,j=r+1;
    while(i<j)
    {
        do i++;while(nums[i]<mid);
        do j--;while(nums[j]>mid);
        if(i<j) swap(nums[i],nums[j]);
    }
    quick_sort(nums,l,j);
    quick_sort(nums,j+1,r);
}

归并排序

const int N=100010;
vector<int> a(N);
void merge_sort(vector<int>& nums,int l,int r)
{
    if(l>=r) return;
    int mid=(l+r)>>1;
    merge_sort(nums,l,mid),merge_sort(nums,mid+1,r);
    int i=l,j=mid+1;
    int k=0;
    while(i<=mid&&j<=r)
    {
        if(nums[i]<nums[j]) a[k++]=nums[i++];
        else a[k++]=nums[j++];
    }
    while(i<=mid)  a[k++]=nums[i++];
    while(j<=r) a[k++]=nums[j++];
    for(int i=l,j=0;i<=r;i++,j++) nums[i]=a[j];

}

冒泡排序

void bubble_sort(vector<int>&nums,int l,int r)
{
    for(int i=0;i<nums.size();i++)
    {
        int l=0;
        while(++l<=r)
        {
            if(nums[l-1]>nums[l]) swap(nums[l-1],nums[l]);
        }
        r--;
    }
}

选择排序

void select_sort(vector<int>&nums,int l,int r)
{
    for(int i=0;i<nums.size();i++)
    {
        int min_v=INT_MAX,no=0;
        for(int j=i;j<=r;j++)
        {
            if(nums[j]<min_v)
            {
                min_v=nums[j];
                no=j;
            }
        }
        swap(nums[i],nums[no]);
    }
}

插入排序

void insert_sort(vector<int>&nums, int l, int r)
{
    for (int i = 0; i<nums.size(); i++)
    {
        int cur = nums[i];
        int j = i;
        while (j >= 0 && nums[j]>=cur) j--;
        nums.erase(nums.begin() + i);
        nums.insert(nums.begin() + 1+j, cur);
    }
}


新鲜事 原文

各位大佬,基于比较的查找,最好的性能上logn,还有什么查找能突破这个限制?



题目描述

实现函数double Power(double base, int exponent),求base的exponent次方。不得使用库函数,同时不需要考虑大数问题。

在LeectCode中,
对于样例3如果O(n)会TLE,可以使用快速幂,由于不存在大数,因此不需要long long。
但是指数输入 存在-2147483648 ,虽然不超过int范围(int -2147483648 ~ 2147483647),但是需要取个abs,因此需要对指数定义long long。

样例

样例1

输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25
样例2

输入: 2.00000, 10
输出: 1024.00000
样例3

输入:1.00000,2147483647

C++ 代码

class Solution {
public:
    double Power(double base, int exponent) {

        double ans=1;
        long long q=abs(exponent);
        while(q)
        {
            if(q&1) ans=ans*base;
            base*=base;
            q>>=1;
        }
        if(exponent<0) ans=1/ans;
        return ans;
    }
};


活动打卡代码 AcWing 890. 能被整除的数

//容斥原理
//首先公式记住
//有m个质数
//所以 把所有取值方案枚举一下 会发现 除了一个都不拿的 一共有2的m次方减1个方案
//那么我们可以用位运算来记录每个方案
//为1的那位就代表乘上这个位置对应的质数
//比如 m=3, 质数为 2 3 5
//那么 那么一共有1<<m -1 也就是1<<3 -1 =8-1 =7种方案
//一共需要枚举3位
//记录一下cnt(每次中 位值等于1的数 也就是代表本次枚举取几个数的集合)
//001 一个数 2      cnt=1
//010 一个数 3      cnt=1
//011 两个数 2x3    cnt=2
//100 一个数 5      cnt=1
//101 两个数 2x5    cnt=2
//110 两个数 3x5    cnt=2
//111 三个数 2x3x5  cnt=3
//最后把每次结果求和即得到答案

#include<iostream>
using namespace std;
const int N=20;
int p[N];
int n,m;
int main()
{
    cin>>n>>m;
    for(int i=0;i<m;i++) cin>>p[i];

    int res=0;
    for(int i=1;i<1<<m;i++)
    {
        int t=1,cnt=0;
        for(int j=0;j<m;j++)
        {
            if(i>>j&1)
            {
                cnt++;
                if((long long)t*p[j]>n)
                {
                    t=-1;
                    break;
                }
                t*=p[j];
            }
        }
        if(t!=-1)
        {
            if(cnt%2) res+=n/t;
            else res-=n/t;
        }
    }
    cout<<res<<endl;
    return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 867. 分解质因数

//这里填你的代码^^
#include<iostream>
using namespace std;
void prime(int x)
{
    for(int i=2;i<=x/i;i++)
    {
        int s=0;
        if(x%i==0)
        {
            while(x%i==0)
            {
                x/=i;
                s++;
            }
            cout<<i<<' '<<s<<endl;
        }
    }
    if(x>1) cout<<x<<' '<<1<<endl;

}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int a;
        cin>>a;
        prime(a);
        puts("");
    }
    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



#include<iostream>
using namespace std;
bool prime(int x)
{
    if(x<2) return false;
    for(int i=2;i<=x/i;i++)
    {
        if(x%i==0) 
        {
            return false;
        }
    }
    return true;
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int b;
        cin>>b;
        cout<<(prime(b)?"Yes":"No")<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 843. n-皇后问题

#include<iostream>
using namespace std;
const int N=20;
char g[N][N];
bool dg[N],udg[N],col[N];
int n;

void dfs(int u)
{
    if(u==n)
    {
        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[-u+i+n])
        {
            g[u][i]='Q';
            col[i]=dg[u+i]=udg[-u+i+n]=true;
            dfs(u+1);
            col[i]=dg[u+i]=udg[-u+i+n]=false;
            g[u][i]='.';
        }
    }
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            g[i][j]='.';

    dfs(0);
    return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 842. 排列数字

#include<iostream>
using namespace std;
const int N=100010;
int path[N];
bool st[N];
int n;
void dfs(int u)
{
    if(u==n) 
    {
        for(int i=0;i<n;i++) cout<<path[i]<<" ";
        puts("");
        return ;
    }
    for(int i=1;i<=n;i++)
    {
        if(!st[i])
        {
            path[u]=i;
            st[i]=true;
            dfs(u+1);
            st[i]=false;
        }
    }
}
int main()
{
    cin>>n;
    dfs(0);
    return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 803. 区间合并

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int,int> PII;
const int N=100010;
vector<PII> ans;

void merge(vector<PII>& ans)
{
    vector<PII> res;
    sort(ans.begin(),ans.end());
    int st=-2e9,ed=-2e9;
    for(int i=0;i<ans.size();i++)
    {
        if(ed<ans[i].first)
        {
            if(ed!=-2e9) res.push_back({st,ed});
            st=ans[i].first,ed=ans[i].second;
        }
        else
        {
            ed=max(ed,ans[i].second);
        }
    }
    if(ed!=-2e9) res.push_back({st,ed});
    ans=res;
}

int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int l,r;
        cin>>l>>r;
        ans.push_back({l,r});
    }
    merge(ans);
    cout<< ans.size();
    return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 802. 区间和

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N=300010;
typedef pair<int,int> PII;
int a[N],s[N];
vector<PII> add,query;
vector<int>alls;
int find(int x)
{
    int l=0,r=alls.size()-1;
    while(l<r)
    {
        int mid=(l+r)/2;
        if(alls[mid]>=x) r=mid;
        else l=mid+1;

    }
            return r+1;
}
int main()
{
    int n,m;
    cin>>n>>m;
    while(n--)
    {
        int x,c;
        cin>>x>>c;
        alls.push_back(x);
        add.push_back({x,c});
    }
    while(m--)
    {
        int l,r;
        cin>>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());

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

    for(auto item:query)
    {
        int l=find(item.first),r=find(item.second);
        cout<<s[r]-s[l-1]<<endl;
    }
    return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~