[算法课]算法考试赌题
程序员文章站
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