从网上整理的华为机试题目

一、华为机试——2018年校招10号参加的华为的机试，这次的3道题难度适中。第一题字符串，第二题贪心算法（会不会？），dp可以解，第三题长整数相乘。因为题主做过第三题原题，刚开始就把第三题秒了～～然后开始做第一题，一般10分钟就可以搞定。第二题要想一下，不过也差不多是原题，Leetcode上第55题jumpgame应该是此题原型。因为都刷过几乎是原题的原故，一个小时不到3题就AC完了下面是完整题目和代码题目一、给你一个原始字符串，根据该字符串内每个字符出现的次数，按照ASCII码递增顺序重新调整输出。举例！假设原始字符串为eeefgghhh则每种字符出现的次数分别是1.eee3次2.f1次3.gg1次4.hhh3次重新排序后输出的字符串如下：efghegheh编写程序，实现上述功能。【温馨提示】1.原始字符串中仅可能出现“数字”和“字母”；2.请注意区分字母大小写。1.#includeiostream2.#includemap3.#includevector4.#includealgorithm5.usingnamespacestd;6.intmain(){7.stringstr;8.inta[128]={0};9.while(cinstr){10.for(inti=0;istr.length();i++){11.a[str[i]]++;12.}//caculatethenumberofeachcharacter13.intmax=*max_element(a,a+128);14.sort(str.begin(),str.end());15.longi=unique(str.begin(),str.end())-str.begin();//thelocationofthemaxiumnumbercharacter16.str=str.substr(0,i);17.for(intj=0;jmax;j++)18.for(inti=0;istr.length();i++){19.if(a[str[i]]){20.coutstr[i];21.a[str[i]]--;22.}23.}24.coutendl;25.}26.27.return0;28.}题目二、给出一组正整数，你从第一个数向最后一个数方向跳跃，每次至少跳跃1格，每个数字的值表示你这个位置可以跳跃的最大长度。计算如何以最少的跳跃次数跳到最后一个数。输入描述：第一行表示有多少个数n第二行依次是1到n，一个数一行。输出描述：输出一行，表示跳跃最少的次数1.#includeiostream2.#includecstdlib3.#includevector4.#includealgorithm5.//确定起点后，用一个指针指向最大跳跃点。6.//搜索最大跳跃点与起点之间能往后走的最远的点，选定该点为起点，其最大跳跃点为终点。重复。7.#defineMAX10008.usingnamespacestd;//每次跳的最大长度为a[i]+i。9.if(a[i]+istepMax){//搜索最大的跳跃点，记为index10.stepMax=a[i]+i;11.index=i;12.}13.if(i==end){//搜索完毕，从index（能跳最远的位置）开始继续跳14.end=stepMax;15.++count;16.i=index;17.}18.}19.returncount;20.}21.22.intmain()23.{24.intn;25.while(cinn){26.inta[MAX]={0};27.for(inti=0;in;i++){28.cina[i];29.}30.coutjump(a,n);31.}32.33.}题目三、编写“长整数相乘”的程序，实现两个任意长度的长整数（正数）相乘，输出结果这题就不多逼逼了，网上多的是答案。[1.#includeiostream2.usingnamespacestd;3.4.5.6.intmultiply(stringma,stringmb,string&strRst)7.{8.9.stringchengshuA=ma;10.stringchengshuB=mb;11.unsignedlonga=chengshuA.length();12.unsignedlongb=chengshuB.length();13.intstrRst_length=0;14.unsignedlongc=(a+1)*(b+1);15.int*p=newint[c];16.int*pA=newint[a];17.int*pB=newint[b];18.19.20.if((a==0)||(b==0))21.return-1;22.23.for(inti=0;i!=c;i++)24.p[i]=0;25.26.27.for(string::size_typeindex=0;index!=chengshuA.length();index++)28.pA[a-1-index]=chengshuA.at(index)-'0';29.30.31.for(string::size_typeindex=0;index!=chengshuB.length();index++)32.pB[b-1-index]=chengshuB.at(index)-'0';33.34.35.for(inttemp_b=0;temp_b!=b;temp_b++)36.{37.for(inttemp_a=0;temp_a!=a;temp_a++)38.{39.40.inttemp=p[temp_a+temp_b]+pA[temp_a]*pB[temp_b];41.p[temp_a+temp_b]=temp%10;42.intcarry=temp/10;43.44.intx=temp_a+temp_b+1;45.46.while(carry!=0)47.{48.p[x]=p[x]+carry%10;49.carry=carry/10;50.x++;51.}52.}53.}54.55.while(c--0)56.{57.if(p[c]!=0)58.{59.strRst_length=c+1;60.break;61.}62.}63.64.charch;65.for(inti=strRst_length-1;i=0;i--)66.{67.ch=p[i]+'0';68.strRst.push_back(ch);69.}70.if(strRst.empty())71.{72.strRst=0;73.}74.75.return0;76.}77.78.intmain(void)79.{80.stringa;81.stringb;82.while(cinab){83.stringstrRst=\0;84.multiply(a,b,strRst);85.coutstrRstendl;86.}87.return0;88.}二．华为机试题目+解答+自己不足+提升题目一、給一个十进制数，输出其二进制第一个1所在的位置这个题目没截下来，大概意思就是这个。首先就是要把十进制转成二进制。由于长时间没接触算法，当时我就懵逼了。还好后来我机智（此处省略机智的过程300字。。。。）算法如下：if(x=0)return-1;inta[40]={0};inti;for(i=0;x0;i++){a[i]=x%2;x/=2;}for(i--;i=0;i--)//fortestprintf(%d,a[i]);coutendl;首先如果给的是负数或者小数什么的要进行输入判定，我这里就判定了负数（我觉得第一题没得满分就是忽略了小数判定）然后正式开始将十进制转为二进制。数组a[40]用于存储二进制，其中a[0]是二进制的第0位。x是我输入的整数，将x不停地对2取余，余数就是对应的2进制位。比如x=12，第一次12对2取余余数为0商为6，那么0就是12的二进制第0位，存至a[0]中，第二次就对6取余余数为2，存到a[1]中，以此类推了。最终得到a[0]、a[1]、a[2]。。。。。便是二进制的0,1,2......位。我不放心，输出测试一下。之后就简单了，输出a数组中从小到大第一个值为1的i值即可。值得注意的是，这种题其实写在一个main函数里就够了，而且这样写也比较好。毕竟机试不是做项目，不需要模块化，这样修改起来也比较容易。题目二、宝宝表示这道题其实不难，就是两个字，复杂。我的思路大概就是1.首先判断所给矩形是否相交，不相交直接输出02.若相交，将相交面积表示出来，并输出结果最后发现貌似判断相交的思路会影响相交求面积的思路（正所谓数学题多问，第一问为第二问做铺垫一样）由于我的判相交思路不好影响了第二问，导致这一题我没做出来。思路大概是求出两个矩形中心坐标，用平行于坐标轴的线段连接两个中心，平行于x轴的线段长度若记为cenX,另一个记为cenY，我就判断cenX，Y与两矩形边长的关系。做完后才发现对第二问毫无帮助，炸了。。。。。。。浴室这一题200分我得了不到100分。。。。。（没代码）题目三、这道题其实没怎么做出来，就不好说什么。。。。。。下面是这道题正解的源码：#includeiostream#includestack#includealgorithmusingnamespacestd;intnum[400][400];intlen[400][400];intmax(inta,intb){if(ab)returna;elsereturnb;}intmain(){intm,n;scanf(%d%d,&m,&n);for(inti=1;i=m;i++){len[i][0]=0;for(intj=1;j=n;j++){len[0][j]=-1;scanf(%d,&num[i][j]);if(num[i][j])len[i][j]=len[i][j-1]+num[i][j];elselen[i][j]=0;}}stackintS;intans=0,tmp;for(intj=n;j0;j--){intW,L;tmp=0;if(ans=j*m)break;S.push(0);for(inti=1;i=m;i++){if(len[i][j]len[S.top()][j]){S.push(i);}else{while(!S.empty()&&len[i][j]=len[S.top()][j]){L=S.top();S.pop();intp=S.top();W=(i-p-1);tmp=max(tmp,W*len[L][j]);}S.push(i);}}intLL;if(!S.empty())LL=S.top();while(!S.empty()){L=S.top();S.pop();intp=S.top();if(p)W=(LL-p);else{W=LL;S.pop();}tmp=max(tmp,W*len[L][j]);}ans=max(tmp,ans);}printf(%d\n,ans);return0;}三．华为挑战赛（也是模拟机试）题目一、这种第一题摆明了是送分题，不好说什么，有一点编程底子的10分钟内都能做出来#includeiostream#includemath.husingnamespacestd;intmain(){intm,n;inti,j;inttemp;boolflag;cinmn;for(i=m;i=n;i++){flag=true;;temp=(int)sqrt(i);for(j=2;j=temp;j++){if(i%j==0)flag=false;}if(flag==true)couti;}return0;}题目二、卧槽，这道题我要吐槽。因为一些原因和问题，导致这道题