笔试强训：Day5

一、笨小猴（哈希+数学）

笨小猴_牛客题霸_牛客网

#include <iostream>
#include <cmath>
using namespace std;
string s;
bool isprime(int x){//试除法if(x==2) return true;if(x<2||x%2==0) return false;int n=sqrt(x);for(int i=3;i<=n;i+=2)if(x%i==0) return false;return true;
}
int main() {cin>>s;int hash[26]={0};//哈希表for(auto&ch:s) ++hash[ch-'a'];int maxn=0,minn=100;for(int i=0;i<26;++i)//找最大值和最小值if(hash[i]){maxn=max(maxn,hash[i]);minn=min(minn,hash[i]);}int x=maxn-minn;if(isprime(x)) {cout<<"Lucky Word"<<endl;cout<<x<<endl;}else {cout<<"No Answer"<<endl;cout<<0<<endl;}}

二、主持人调度（左端点排序）

主持人调度（一）_牛客题霸_牛客网

class Solution {
public:bool hostschedule(vector<vector<int> >& schedule) {sort(schedule.begin(),schedule.end());int n=schedule.size();for(int i=0;i<n-1;++i)if(schedule[i][1]>schedule[i+1][0]) return false;return true;}
};

三、分割等和子集（01背包）

分割等和子集_牛客题霸_牛客网

#include <iostream>
using namespace std;
//从数组中挑选一些数字 是否可以恰好等于sum/2  01背包问题
int n;
const int N=505,M=505*105/2;
int arr[N];
bool dp[M];
int main(){cin>>n;int sum=0;//记录总和for(int i=1;i<=n;++i){cin>>arr[i];sum+=arr[i];}if(sum%2) cout<<"false"<<endl;//不能整除else{sum/=2;dp[0]=true;for(int i=1;i<=n;++i)for(int j=sum;j>=arr[i];--j)dp[j]=dp[j]||dp[j-arr[i]];if(dp[sum]) cout<<"true"<<endl;else cout<<"false"<<endl;}
}

四、小红的ABC（找规律）

登录—专业IT笔试面试备考平台_牛客网

//a b c三个字母 最短的 那么只有可能是2和3
#include<iostream>
#include<string>
using namespace std;
string s;
int main(){cin>>s;int n=s.size();int ret=-1;//没有回文串的情况for(int i=0;i<n-1;++i){if(s[i]==s[i+1]){ret=2;break;}if(i+2<n&&s[i]==s[i+2]) ret=3;}cout<<ret<<endl;
}

五、不相邻取数（状态dp）

不相邻取数_牛客题霸_牛客网

#include <iostream>
using namespace std;
const int N=2e5+10;
int n;
int arr[N],f[N],g[N];//f[i]是选了i位置后的最大  g[i]是没选i位置后的最大
int main() {cin>>n;for(int i=1;i<=n;++i) cin>>arr[i];for(int i=1;i<=n;++i){f[i]=g[i-1]+arr[i];g[i]=max(f[i-1],g[i-1]);}cout<<max(f[n],g[n])<<endl;
}

六、**空调遥控（排序+二分/滑动窗口）

登录—专业IT笔试面试备考平台_牛客网

解法1：排序+二分找区间（左端点+右端点组合）

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e6+10;
int arr[N];
int n,p;
int main(){cin>>n>>p;for(int i=0;i<n;++i) cin>>arr[i];sort(arr,arr+n);int ret=1;//开始枚举for(int i=arr[0];i<=arr[n-1];++i){//枚举温度int left=0,right=n-1;while(left<right){//begin-2 用左端点区间int mid=left+(right-left)/2;if(arr[mid]<i-p) left=mid+1;else right=mid;}int begin=left;right=n-1;//left可以继续从原来的位置找 重置right就行了while(left<right){//begin-p 用右端点区间int mid=left+(right-left+1)/2;if(arr[mid]<=i+p) left=mid;else right=mid-1;}ret=max(ret,right-begin+1);}cout<<ret<<endl;return 0;
}

解法2：滑动窗口

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e6+10;
int arr[N];
int n,p;
int main(){cin>>n>>p;p*=2;//差值for(int i=0;i<n;++i) cin>>arr[i];sort(arr,arr+n);//滑动窗口 差值在2*p的最大区间int ret=1;for(int left=0,right=0;right<n;++right){while(arr[right]-arr[left]>p)++left;ret=max(ret,right-left+1);}cout<<ret<<endl;
}

七、kotori和气球（组合数学）

登录—专业IT笔试面试备考平台_牛客网

#include<iostream>
using namespace std;
const int mod=109;
int n,m;
int main(){cin>>n>>m;//n与m个(n-1)的乘积int ret=n;for(int i=0;i<m-1;++i) ret=ret*(n-1)%mod;cout<<ret<<endl;
}

八、 *走迷宫（单源最短路BFS）

走迷宫_牛客题霸_牛客网

 单源最短路问题：

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int N=1010;
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
int n,m,x1,x2,y1,y2;
char arr[N][N];
int dis[N][N];//不仅用来看看搜索过了没 
//单源最短路问题 用bfs扩展
int bfs(){//-1表示走不到if(arr[x2][y2]=='*') return -1;memset(dis, -1, sizeof dis); // 表⽰还没开始搜索queue<pair<int,int>> q;q.emplace(x1,y1);dis[x1][y1]=0;while(!q.empty()){auto[a,b]=q.front();q.pop();for(int k=0;k<4;++k){int x=dx[k]+a,y=dy[k]+b;if(x>=1&&x<=n&&y>=1&&y<=m&&arr[x][y]=='.'&&dis[x][y]==-1){q.emplace(x,y);dis[x][y]=dis[a][b]+1;if(x==x2&&y==y2) return dis[x][y];}}}return -1;
}
int main() {cin>>n>>m>>x1>>y1>>x2>>y2;for(int i=1;i<=n;++i)for(int j=1;j<=m;++j) cin>>arr[i][j];cout<<bfs()<<endl;
}

1、读取定长字符串也可以按照字符一个个读取

2、单源最短路的标记数组不仅可以记录距离，也可以用来标记是否搜索过

3、memset用来标记-1 

九、**主持人调度2（贪心+优先级队列+左端点排序）

主持人调度（二）_牛客题霸_牛客网

 解法1：贪心+优先级队列+左端点排序

class Solution {
public:int minmumNumberOfHost(int n, vector<vector<int>>& startEnd) {sort(startEnd.begin(),startEnd.end());priority_queue<int,vector<int>,greater<int>> heap;//创建一个小根堆heap.push(startEnd[0][1]);for(int i=1;i<n;++i){int a=startEnd[i][0],b=startEnd[i][1];if(a>=heap.top()) heap.pop(); //说明没有重叠heap.push(b);}return heap.size();}
};

 解法2：分别排序+遍历比较

class Solution {
public:int minmumNumberOfHost(int n, vector<vector<int> >& startEnd) {vector<int> start;vector<int> end;//分别得到活动起始时间for(int i = 0; i < n; i++){start.push_back(startEnd[i][0]);end.push_back(startEnd[i][1]);}//分别对开始和结束时间排序sort(start.begin(), start.end());sort(end.begin(), end.end());int res = 0;int j = 0;//遍历结束时间for(int i = 0; i < n; i++)//新开始的节目大于上一轮结束的时间，主持人不变if(start[i] >= end[j])  j++;  else res++;  //主持人增加return res;}
};

十、游游的重组偶数（数学）

游游的重组偶数__牛客网

#include <iostream>
#include <string>
using namespace std;
//把每个数字中为偶数的部分放到最后就可以了
int q;
string s;
int main() {cin>>q;while(q--){cin>>s;int n=s.size();int i=n-1;for(;i>=0;--i)if(s[i]%2==0){swap(s[i],s[n-1]);break;}if(i!=-1) cout<<s<<endl;else cout<<-1<<endl;}
}

十一、**体操队形（枚举+dfs）

登录—专业IT笔试面试备考平台_牛客网

#include<iostream>
using namespace std;
int n;
int ret=0;//统计最终结果
const int N=11;
int arr[N];
bool vis[N];//队员
void dfs(int pos){if(pos==n+1){++ret;return;}//说明找到了一种合法方案//开始一个个位置去选择for(int i=1;i<=n;++i){if(vis[i]) continue;//如果该位置的人选过了 就跳过//我不可能排在我想排的人前面 那后面再怎么选都是错的if(vis[arr[i]]) return;vis[i]=true;dfs(pos+1);vis[i]=false;}
}
int main(){cin>>n;for(int i=1;i<=n;++i) cin>>arr[i];dfs(1);//从第一个位置开始选cout<<ret<<endl;
}

十二、**二叉树中的最大路径和（dfs+树形dp思想）

二叉树中的最大路径和_牛客题霸_牛客网

 

class Solution {
public:int ret=-1010;//统计最大值int maxPathSum(TreeNode* root) {dfs(root);return ret;}int dfs(TreeNode* root){if(root==nullptr) return 0;int left=max(dfs(root->left),0);//最大左子链int right=max(dfs(root->right),0);//最大右子链ret=max(ret,left+right+root->val);//经过root的最大路径return root->val+max(left,right);//给上层返回单链的信息}
};

十三、*排序子序列（模拟+贪心）

排序子序列_牛客笔试题_牛客网

 

#include <iostream>
using namespace std;
int n;
const int N=1e5+10;
int arr[N];
int main() {cin>>n;for(int i=0;i<n;++i) cin>>arr[i];int ret=0,i=0;while(i<n){if(i==n-1){//这个时候不存在后面的数比了 所以自己就是一个子序列++ret;break;}if(arr[i+1]>arr[i]){//搞一个上升的子序列while(i+1<n&&arr[i+1]>=arr[i]) ++i;++ret;}else if(arr[i+1]<arr[i]){//说明搞一个下降的子序列while(i+1<n&&arr[i+1]<=arr[i]) ++i;++ret;}else  while(i+1<n&&arr[i+1]==arr[i]) ++i;++i;}cout<<ret<<endl;
}

十四、消减整数（贪心+数学）

登录—专业IT笔试面试备考平台_牛客网

#include<iostream>
using namespace std;
//得确保 正好a*2==cur 才可以翻倍
int t,h;
int main(){cin>>t;while(t--){cin>>h;int a=1,ret=0;while(h){h-=a;++ret;if(h%(a*2)==0) a*=2;}cout<<ret<<endl;}
}

十五、最长上升子序列2（贪心+二分）

最长上升子序列(二)_牛客题霸_牛客网

 

class Solution {
public:int LIS(vector<int>&nums) {int n=nums.size();if(n<=1) return n;//至少有两个元素vector<int> v;//用来当数组v.emplace_back(nums[0]);for(int i=1;i<n;++i){int x=nums[i];//如果比后面的大 就直接插入if(x>v.back()) v.emplace_back(nums[i]);else if(x==v.back()) continue;else{//二分查找插入的位置int left=0,right=v.size()-1;while(left<right){int mid=left+(right-left)/2;if(v[mid]<x) left=mid+1;else right=mid;}v[left]=x;}} return v.size();}
};

十六、爱吃素（数学）

登录—专业IT笔试面试备考平台_牛客网

#include<iostream>
#include<cmath>
using namespace std;
int t;
typedef long long LL;
LL a,b;
bool isprim(LL x){if(x==2) return true;if(x<2||x%2==0) return false;int n=sqrt(x);for(int i=3;i<=n;i+=2)if(x%i==0) return false;return true;
}
int main(){cin>>t;while(t--){cin>>a>>b;if((a==1&&isprim(b))||(b==1&&isprim(a))) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
}

十七、相差不超过k的最多数（排序+滑动窗口）

相差不超过k的最多数_牛客题霸_牛客网

#include <iostream>
#include <algorithm>
using namespace std;
int n,k;
const int N=2e5+1;
int arr[N];
int main() {cin>>n>>k;for(int i=0;i<n;++i) cin>>arr[i];sort(arr,arr+n);int ret=1;for(int left=0,right=0;right<n;++right){while(arr[right]-arr[left]>k) ++left;ret=max(right-left+1,ret);}cout<<ret<<endl;
}

十八、最长公共子序列1（LCSdp）

最长公共子序列(一)_牛客题霸_牛客网

 

#include <iostream>
using namespace std;
const int N=1010;
char s1[N],s2[N];
int dp[N][N];
int n,m;
int main() {//dp[i][j]表示以0-i的字符串1中 与0-j字符串2中 的最长公共子序列长度cin>>n>>m;for(int i=1;i<=n;++i) cin>>s1[i];for(int i=1;i<=m;++i) cin>>s2[i];//开始进行dpfor(int i=1;i<=n;++i)for(int j=1;j<=m;++j)if(s1[i]==s2[j]) dp[i][j]=dp[i-1][j-1]+1;else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);cout<<dp[n][m]<<endl;
}