欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

[算法课]算法考试赌题

程序员文章站 2022-04-10 19:35:15
赌题目录递归:归并#include#includeusing namespace std;vector arr;vector tmpArr(1000);void func(int l,int r){ if(l>=r)return ; int mid =l+r>>1; func(l,mid),func(mid+1,r);...

赌题目录

递归:归并

#include<iostream>
#include<vector>

using namespace std;

vector<int> arr;
vector<int> tmpArr(1000);

void func(int l,int r){
    if(l>=r)return ;
    
    int mid =l+r>>1;
    
    func(l,mid),func(mid+1,r);
    
    int i=l,j=mid+1,k=0;
    while(i<=mid&&j<=r)
        if(arr[i]<=arr[j])tmpArr[k++]=arr[i++];
        else tmpArr[k++]=arr[j++];
        
    while(i<=mid)tmpArr[k++]=arr[i++];
    while(j<=r)tmpArr[k++]=arr[j++];
    
    for(int i=0,j=l;j<=r;j++,i++)arr[j]=tmpArr[i];
}

int main(){
    int n;
    cin>>n;
    
    int tmpn;
    while(n--)cin>>tmpn,arr.push_back(tmpn);
    
    func(0,arr.size()-1);
    
    for(int x:arr)cout<<x<<" ";
    
    return 0;
}

[算法课]算法考试赌题

分治:最大值次大值

#include<iostream>
#include<vector>

using namespace std;

int n;
vector<int>arr;

int firstAns,secondAns;

void func(int l,int r){
    if(l==r){
        if(arr[l]>firstAns)secondAns = firstAns,firstAns=arr[l];
        else secondAns=max(secondAns,arr[l]);
        
        return ;
    }
    else {
        int mid = l+r>>1;
        func(l,mid),func(mid+1,r);
    }
}

int main(){
    cin>>n;
    
    int tmpn;
    while(n--)cin>>tmpn,arr.push_back(tmpn);
    
    func(0,arr.size());    
    
    cout<<firstAns<<" "<<secondAns;
    return 0;
}

[算法课]算法考试赌题

蛮力:最大值的连续子序列

#include<iostream>
#include<vector>

using namespace std;

vector<int> arr;

int main(){
    int tn;
    cin>>tn;
    
    auto func = [](int n){
        int tmpn;
        while(n--)cin>>tmpn,arr.push_back(tmpn);
        
        int maxSum=0;
        for(int i=0;i<arr.size();i++)
            for(int j=i;j<arr.size();j++){
                int tmpSum=0;
                for(int p=i;p<=j;p++)tmpSum+=arr[p];
                maxSum=max(maxSum,tmpSum);
            }
        
        return maxSum;
    };
    
    cout<<func(tn);
    
    return 0;
}

[算法课]算法考试赌题

回溯:迷宫

#include<iostream>
#include<vector>
#include<string>

using namespace std;

const int len=8+1;

string map[]={
"OXXXXXXX",
"OOOOOXXX",
"XOXXOOOX",
"XOXXOXXO",
"XOXXXXXX",
"XOXXOOOX",
"XOOOOXOO",
"XXXXXXXO"
};

int beginX=0,beginY=0;
int endX=7,endY=7;

int dx[]={-1,0,1,0},dy[]={0,1,0,-1};

void dfs(int x,int y){
        if(x == endX&&y==endY){
            for(int i=0;i<sizeof map / map[0].length();i++)cout<<map[i]<<endl;
            
            return ;
        }
        else {
        for(int i=0;i<4;i++){
            if((unsigned int)x<=sizeof map/map[0].length()
            &&(unsigned int)y<=map[0].length()
            &&map[x][y]=='O'){
                map[x][y]=' ';
                dfs(x+dx[i],y+dy[i]);
                map[x][y]='O';
            }
        }
    }
}

int main(){
    
    dfs(beginX,beginY);
      
    return 0;
}

[算法课]算法考试赌题

贪心:活动安排

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

using namespace std;

typedef pair<int,int> PII;
vector<PII> arr;

int main(){
    int tn;
    cin>>tn;
    
    int tbegin,tend;
    while(tn--)cin>>tbegin>>tend,arr.push_back((PII){tbegin,tend});
    
    sort(arr.begin(),arr.end(),[](PII a,PII b){
        return a.second < b.second; 
    });
    
    vector<bool> checkArr(arr.size(),false);
    
    int preEnd =0;
    for(int i=0;i<arr.size();i++)
        if(arr[i].first>=preEnd){
            checkArr[i]=true;
            preEnd = arr[i].second;
        }
    
    int ansSum=0;
    for(int i=0;i<arr.size();i++)if(checkArr[i]==true){cout<<i+1<<" ";ansSum++;}
    
    cout<<endl<<ansSum;
    
    return 0;
}

[算法课]算法考试赌题

动态规划:lcs

#include<iostream>
#include<string>
#include<vector>

using namespace std;


int main(){
    string  str1,str2;
    cin>>str1>>str2;
    
    vector<vector<int>> dp(str1.size()+1,vector<int>(str2.size()+1,0));
    
    for(int i=1;i<=str1.size();i++)
        for(int j=1;j<=str2.size();j++)
            if(str1[i-1] == str2[j-1])dp[i][j]=dp[i-1][j-1]+1;
            else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
    
    cout<<dp[str1.size()][str2.size()];
    
    return 0;
}

[算法课]算法考试赌题

本文地址:https://blog.csdn.net/weixin_43910320/article/details/107313955