2017年腾讯秋招软件开发笔试编程题

2017年腾讯秋招软件开发笔试编程题回忆版（所有题目大致描述如下，并非完整的题目回忆，但意思大致一样）1、又一个魔法城市，城市里面有n个魔法城堡，序号为0,1,2。。。n-1;魔法城堡之间都有路径相连；魔法城堡两两之间的到达的距离不同，因此所需时间也可能不会相同。如魔法城堡0到魔法城堡2需要耗时4小时；现，小明想从魔法城堡0到魔法城堡1，他想知道需要花费多少时间；为了快速到达，有一魔法扫把，魔法扫把使用次数有限，使用一次，可以将某一段间的时间减半；求小明从魔法城堡0到魔法城堡1花费的最小时间，精确到一位小数。输入：总共n+1行；第一行，魔法城堡数n;魔法扫把能够使用的次数k;第二行到第n行为魔法城堡之间到达需要的时间；输出：从魔法城堡0到魔法城堡花费的最短时间：t，精确到小数点后一位。示例：输入：32094904440（注：腾讯这里输入的094，904，440，是以字符串的形式输入的）输出：4.0个人大致思路：利用Dijkstra最短路径求法；记录到魔法城堡1的最短路径上每一个前驱节点和对应的距离；然后对每段的距离进行降序排序；之后把魔法扫把使用在所耗时最多的段中。如0到1的最短路径为0到2，消耗为4；2到1消耗为3；魔法扫把能使用1次；那么把这一次机会使用在0到2这一段路径上；那么最后最短时间即为：2+3=5.0；代码实现为：#include<iostream>#include<vector>#include<string>#include<map>#include<set>#include<cstring>#include<math.h>#include<algorithm>usingnamespacestd;#defineMIN99999vector<int>dijkstra_shortpath(vector<vector<int>>arcs,intednode)intsize=arcs.size();vector<int>dist(size);//保存当前最短路径vector<int>path(size); //保存前驱节点vector<int>S(size); //保存已经找到最短路径的节点//初始化for(size_ti=0;i<size;i++){dist[i]=arcs[0][i];S[i]=0;path[i]=0;}S[0]=1,path[0]=-1;//进行循环更新每次遍历每个节点的最短路径长度for(inti=1;i<size;i++){intnmin=MIN,mi=1;for(intj=1;j<size;j++){if(!S[j]&&dist[j]<nmin)mi=j;nmin=dist[j];}cout<<"minindex="<<mi<<";paht="<<nmin<<endl;S[mi]=1;//更新每个节点的最短路径长度for(intj=1;j<size;j++){if(!S[j]&&dist[mi]+arcs[mi][j]<dist[j]){dist[j]=dist[mi]+arcs[mi][j];path[j]=mi;//保存节点j最短路径的前驱mi}}}//输出每个节点的for(inti=0;i<size;i++){cout<<"[pre="<<path[i]<<",len="<<dist[i]<<"];";}cout<<endl;

vector<int>res;while(path[ednode]!=-1){arcs[path[ednode]][ednode]res.push_back(arcs[path[ednode]][ednode]);arcs[path[ednode]][ednode]cout<<"[pre="<<path[ednode]<<";len="<<<<"];";ednode=path[ednode];}cout<<endl;returnres;}intmain(intargc,char**argv){intn=0,k=0;vector<int>res;while(cin>>n>>k){vector<vector<int>>nodes;stringpath;for(inti=0;i<n;i++)cin>>path;for(inti=0;i<n;i++)node[i]=path.at(i)-'0';nodes.push_back(node);}res=dijkstra_shortpath(nodes,1);sort(res.begin(),res.end。);//默认是升序遍历intsum=0;for(inti=res.size()-1;i>=0;i--){if(k>0){sum+=res[i]/2;k-=1;}elsesum+=res[i];}cout<<"mincosttime="<<sum<<endl;}return0;minirides=2;paht=4miniridex=l;paht=8_pre=-l,len=O];_pre=2,Len=8];_pre=O?Lt□二4];_pre=2TLen=4];_pre=O,len=4];minco-sttime=4.013094904440miniridex=2;paht=4miniridex=l;paht=8_pre=-lJlen=0];_pre=2TLen=8]; _pre=0,-Le口二4];_pre=2TLen=4];_pre=0Tlen=4];minco-sttime=6.02、小明有很多枚硬币，每一枚银币的面值均为2的k次方，并且该类硬币的数量均为2枚；也即是他的硬币的序列是：1，1，2，2，4，4，8，8。。。；现在他去超市买东西，需要支付总额为n;问他有多少种支付方式，也即是有多少种硬币的组合的和为n;（腾讯给的示例，想不起来了）个人大致思路是：利用图的深度优先遍历来做这道到，该过程得出的结果肯定有一部分结果是重复的，则需要去重;暂时未想到其他很好的办法。代码实现如下：#include<iostream>#include<vector>#include<string>#include<map>#include<set>#include<cstring>#include<math.h>#include<algorithm>usingnamespacestd;vector<int>res;intget_cnt(intdepth,intcur_sum,inttarget,set<vector<int>>&sres){if(cur_sum==target){vector<int>tmp;for(inti=0;i<res.size();i++){tmp.push_back(res[i]);cout<<res[i]<<",";}cout<<endl;sres.insert(tmp);return1;if(cur_sum>target)return0;for(inti=depth;i<target*2;i++){cur_sum+=pow(2,(i/2));res.push_back(pow(2,(i/2)));//cout<<"pushtms="<<i<<";sum="<<cur_sum<<endl;get_cnt(i+1,cur_sum,target,sres)?1:0;res.pop_back();cur_sum-=pow(2,(i/2));//cout<<"popotms="<<i<<";sum="<<cur_sum<<endl;}return0;intmain(intargc,char**argv){inttarget=0;while(cin>>target){set<vector<int>>sres;get_cnt(0,0,target,sres);cout<<"setsize="<<sres.size()<<endl;}return0;}运行效果下图所示：(注：setsize,即为组合情况数3、这道编程大体大致是这么描述的，有一台魔法机器，机器上有两个按钮；机器的运算方式是：一次输入两个数字；两个数字根据按下不同的进行同时进行相同的操作。规则如下：红色按钮：按下则两个数，分别同时加1；蓝色按钮按下：两个数分别同时*2。现在小明想知道，他有两个数，和与之对应的目标数，分别记为a,b,A,B；经过多少次按钮操作能够把a变成A;的同时b变成B；输出按钮操作的最少次数；如果不能则输出-1。示例输入：10010002022002输出：2代码大致如下,正确性很难讲：#include<iostream>#include<vector>#include<string>#include<map>#include<set>#include<cstring>#include<math.h>#include<algorithm>usingnamespacestd;intget_opera_cnt(inta,intA)intcnt=0;if(A%2==1)//把它变成偶数{A-=1;//表示红色按钮按一次cnt+=1;}if(A/2>=a){while(A%2==0&&A/2>=a){cnt+=1;A=A/2;//表示蓝色按钮按一次}ent+=(A-a);//表示红色按钮按(A-a)次}elseent+=(A-a);//表示红色按钮按(A-a)次returnent;intmain(intargc,char**argv){inta,b,A,B;while(cin>>a>>b>>A>>B){intacnt=g