[算法课]算法考试赌题

赌题目录

递归：归并

#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