当前位置: 代码迷 >> 综合 >> 百度2017春招笔试的部分编程题
  详细解决方案

百度2017春招笔试的部分编程题

热度:48   发布时间:2024-01-15 09:52:11.0
博主今天分享一下 百度2017春招笔试的部分编程题 的思路和代码实现,如果有错误,希望大家评论指正。
first:TOP3问题
度度熊想去商场买一顶帽子,商场里有N顶帽子,有些帽子的价格可能相同。度度熊想买一顶价格第三便宜的帽子,问第三便宜的帽子价格是多少?
思路解析
这是一个典型的TOPK问题,利用STL库中的顺序表接收N顶帽子的价格,再利用选择排序的思维,从小到大排到第三个就结束,即得到第三便宜的帽子了。
代码实现
#include<iostream> using namespace std; #include<vector>int TheThree(int n,vector<int> str){if(n<3) return -1;int num=0;int i=0;for(; i<n && num<3; i++){//利用选择排序的思维for(int j=n-1; j>i; j--){if(str[j]<str[j-1])swap(str[j],str[j-1]);}if(i==0)num=1;else{if(str[i]!=str[i-1])//去掉价格重复的帽子num++;}}if(num==3)return str[--i];elsereturn -1; } int main(){int n;cin>>n;while(n<0 || n>50){//得到帽子的个数不满足要求继续输入cin>>n;}vector<int> str;while(str.size()<n){int k=0;cin>>k;str.push_back(k);}cout<<TheThree(n,str)<<endl;return 0; }
second:度度回家
一个数轴上共有N个点,第一个点的坐标是度度熊现在位置,第N-1个点是度度熊的家。现在他需要依次的从0号坐标走到N-1号坐标。
但是除了0号坐标和N-1号坐标,他可以在其余的N-2个坐标中选出一个点,并直接将这个点忽略掉,问度度熊回家至少走多少距离?
思路解析
当N<2,则默认回家距离为0;
当N==2,则回家距离为0号和1号差值的绝对值;(与下面的情况可归为一类,此忽略点为-1,忽略长度为0)
当N>2,需要计算忽略点和N个点之间的总距离。
记录忽略点的下标,和当前忽略点的差值,
忽略差值=忽略掉max点后的距离-忽略点与前一个点和后一个点的距离之和。
计算除0号坐标和N-1号坐标外其他点的忽略差值,并找出忽略差值最大的下标即忽略点,并记录忽略差值。
最后回家距离=总距离+忽略点差值(忽略掉max点后的距离-max与前一个点和后一个点的距离之和)。
代码实现
#include<iostream> using namespace std; #include<vector> #include<string> #include<algorithm>int LessNum(int n, vector<int> str){if(n<=2) return 0;int num=0;//回家的距离int max=-1;//被忽略的点的下标值int length=0;//忽略差值for(int i=1; i<n-1; i++){int len=abs(str[i]-str[i-1]);//当前点和以一个点的差值int DifV=len+abs(str[i]-str[i+1])-abs(str[i-1]-str[i+1]);//当前点的忽略差值if(DifV>0&&length <DifV){//比较忽略差值max=i;length=DifV;}num+=len;//保留当前的总距离} num+=abs(str[n-1]-str[n-2]);//N个点的总距离num-= length;//回家距离return num; }int main(){int n;cin>>n;if(n>=0 && n<=50){vector<int> str;while(str.size()<n){int k=0;cin>>k;if(abs(k)<=100)str.push_back(k);}cout<<LessNum(n,str)<<endl;}return 0; }
third:有趣的排序
度度熊有一个N个数的数组,他想将数组从小到大 排好序,但是萌萌的度度熊只会下面这个操作:
任取数组中的一个数然后将它放置在数组的最后一个位置。
问最少操作多少次可以使得数组从小到大有序?
思路解析
这道题很简单,并不一是真的要把数组从小到大排好序,只要把排序的最小操作数算出来就好了,其实就是找到当前数组中乱序的最小值的下标,再计算数组中值比它大的个数就是最小操作数。
代码实现
//有趣的排序 #include<iostream> using namespace std; #include<vector>int MinOperation(int n, vector<int> str) {//找出乱序的最小值,比它大的num加1(需要移动)int min=-1;//乱序的最小值下标for(int i=0; i<n-1; i++){if(str[i]>str[i+1] && (min==-1 || str[min]>str[i]))min=i;}int k=str[min+1];for(int i=0; i<min; i++){//min之前没有比它小的if(str[i]<str[min] && str[i]>k)min=i;}if(min==-1) return 0;//乱序不存在,数组不需要移动int num=1;//乱序最小值存在,需要移动+1for(int i=0; i<n; i++){//min之前没有比它小的if(str[i]>str[min])//所有比乱序最小值大的都需要移动num++;}return num; }int main(){int n;cin>>n;if(n>=0 && n<=50){vector<int> str;while(str.size()<n){int k=0;cin>>k;while(k>1000)cin>>k;str.push_back(k);}cout<<MinOperation(n,str)<<endl;}return 0; }

如果以上有错误,希望大家指正,愿共同进步,编程让人快乐,学习让人成长。
  相关解决方案