阿里巴巴笔试题选解

阿里巴巴笔试题选解--9月22日，阿里巴巴北邮站小题：1、有三个结点，可以构成多少种树形结构？2、一副牌52张(去掉大小王)，从中抽取两张牌，一红一黑的概率是多少？编程题：3、设计一个最优算法来查找一n个元素数组中的最大值和最小值。已知一种需要比较2n次的方法，请给一个更优的算法。情特别注意优化时间复杂度的常数。4、已知三个升序整数数组a[l],b[m]和c[n]。请在三个数组中各找一个元素，是的组成的三元组距离最小。三元组的距离定义是：假设a[i]、b[j]和c[k]是一个三元组，那么距离为:Distance=max(|a[I]–b[j]|,|a[I]–c[k]|,|b[j]–c[k]|)请设计一个求最小三元组距离的最优算法，并分析时间复杂度。5、在黑板上写下50个数字：1至50.在接下来的49轮操作中，每次做如下动作：选取两个黑板上的数字a和b，擦去，在黑板上写|b-a|。请问最后一次动作之后剩下数字可能是什么？为什么？题解：(题解非官方，仅供参考，有错误的地方望指正！谢谢)1、有三个结点的，可以构成多少个种树形结构？解：应该是5种；2、一副牌52张(去掉大小王)，从中抽取两张牌，一红一黑的概率是多少？考察概率论知识解法一：52张牌从中抽两张，就是C(2,52)种情况，一红一黑是C(1,26)*C(1,26)种P=[C(1,26)*C(1,26)]/C(2,52)=26*26/(26*51)=26/51解法二：全为黑或者全为红是C(2,26)种情况，由于是黑和红两种，所以要乘以2P=1-C(2,26)/C(2,52)-C(2,26)/C(2,52)=1-2*(26*25)/(51*52)=1-25/51=26/513、设计一个最优算法来查找一n个元素数组中的最大值和最小值。已知一种需要比较2n次的方法，请给一个更优的算法。情特别注意优化时间复杂度的常数。解：把数组两两一对分组，如果数组元素个数为奇数，就最后单独分一个，然后分别对每一组的两个数比较，把小的放在左边，大的放在右边，这样遍历下来，总共比较的次数是N/2次；在前面分组的基础上，那么可以得到结论，最小值一定在每一组的左边部分找，最大值一定在数组的右边部分找，最大值和最小值的查找分别需要比较N/2次和N/2次；这样就可以找到最大值和最小值了，比较的次数为N/2*3=(3N)/2次如图会更加清晰：代码实现：[cpp]viewplaincopy1.#includestdio.h2.#includestdlib.h3.#defineN74.intmain()5.{6.intarr[N]={4,1,5,9,9,7,10};7.intiter=0;8.intcnt=0;9.for(iter=0;iterN;iter+=2)10.{11.if(++cnt&&arr[iter]arr[iter+1])12.{13.inttemp=arr[iter];14.arr[iter]=arr[iter+1];15.arr[iter+1]=temp;16.}17.}18.intmyMin=arr[0];19.for(iter=2;iterN;iter+=2)20.{21.if(++cnt&&arr[iter]myMin)22.{23.myMin=arr[iter];24.}25.}26.intmyMax=arr[1];27.for(iter=3;iterN;iter+=2)28.{29.if(++cnt&&arr[iter]myMax)30.{31.myMax=arr[iter];32.}33.}34.if(N%2!=0&&++cnt&&myMaxarr[N-1])myMax=arr[N-1];35.printf(minis%d\n,myMin);36.printf(maxis%d\n,myMax);37.printf(comparetimesis%d,cnt);38.return0;39.}上面的算法比较次数基本上已经是最优了，但是有朋友提出这样的顾虑，在极端的情况下，每次都做交换，可能会导致程序开销很大，这样的顾虑是对的，其实在上面的算法的基础上，可以不做交换就能找到最大值和最小值。第3题改进的算法：依旧把数组两两一组分配，不做交换操作，设置一个最大值Max和最小值Min，依次和每一组的两个数据做比较，把较大的值给Max,较小的值给Min，遍历一次就能找到数组的最大值和最小值。示例：数组为{(4,1),(5,9),(9,7),(10,2)},经过第一组比较得到Max=4，Min=1，其中比较了3次；,经过第二组比较得到Max=9，Min=1，其中比较了3次；……到最后Max=10，Min=1；比较次数是3*N/2=(3N)/2，比较次数没有改变！代码实现不难，就不贴了4、已知三个升序整数数组a[l],b[m]和c[n]。请在三个数组中各找一个元素，是的组成的三元组距离最小。三元组的距离定义是：假设a[i]、b[j]和c[k]是一个三元组，那么距离为:Distance=max(|a[I]–b[j]|,|a[I]–c[k]|,|b[j]–c[k]|)请设计一个求最小三元组距离的最优算法，并分析时间复杂度。解：这道题目有两个关键点：第一个关键点：max{|x1-x2|,|y1-y2|}=（|x1+y1-x2-y2|+|x1-y1-(x2-y2)|）/2--公式（1）我们假设x1=a[i]，x2=b[j]，x3=c[k]，则Distance=max(|x1–x2|,|x1–x3|,|x2–x3|)=max(max(|x1–x2|,|x1–x3|),|x2–x3|)--公式（2）根据公式（1），max(|x1–x2|,|x1–x3|)=1/2(|2x1–x2–x3|+|x2–x3|)，带入公式（2），得到Distance=max(1/2(|2x1–x2–x3|+|x2–x3|),|x2–x3|)=1/2*max(|2x1–x2–x3|,|x2–x3|)+1/2*|x2–x3|//把相同部分1/2*|x2–x3|分离出来=1/2*max(|2x1–(x2+x3)|,|x2–x3|)+1/2*|x2–x3|//把(x2+x3)看成一个整体，使用公式（1）=1/2*1/2*((|2x1–2x2|+|2x1–2x3|)+1/2*|x2–x3|=1/2*|x1–x2|+1/2*|x1–x3|+1/2*|x2–x3|=1/2*(|x1–x2|+|x1–x3|+|x2–x3|)//求出来了等价公式，完毕！第二个关键点：如何找到(|x1–x2|+|x1–x3|+|x2–x3|)的最小值，x1，x2，x3，分别是三个数组中的任意一个数，这一题，我只是做到了上面的推导，后面的算法设计是由csdn上的两个朋友想出来的方法，他们的CSDN的ID分别为“云梦泽”和“shuyechengying”.算法思想是：用三个指针分别指向a,b,c中最小的数，计算一次他们最大距离的Distance，然后在移动三个数中较小的数组指针，再计算一次，每次移动一个，直到其中一个数组结束为止，最慢(l+m+n)次，复杂度为O(l+m+n)代码如下：[cpp]viewplaincopy1.#includestdio.h2.#includestdlib.h3.#includemath.h4.#definel35.#definem46.#definen67.intMymin(inta,intb,intc)8.{9.intMin=ab?a:b;10.Min=Minc?Min:c;11.returnMin;12.}13.14.intSolvingviolence(inta[],intb[],intc[])15.{16.//暴力解法，大家都会，不用过多介绍了！17.inti=0,j=0,k=0;18.intMinSum=(abs(a[i]-b[j])+abs(a[i]-c[k])+abs(b[j]-c[k]))/2;19.//intstore[3]={0};20.intSum=0;21.for(i=0;il;i++)22.{23.for(j=0;jm;j++)24.{25.for(k=0;kn;k++)26.{27.Sum=(abs(a[i]-b[j])+abs(a[i]-c[k])+abs(b[j]-c[k]))/2;28.if(MinSumSum)29.{30.MinSum=Sum;31.//store[0]=i;32.//store[1]=j;33.//store[2]=k;34.}35.}36.}37.}38.//printf(theminis%d\n,minABC);39.//printf(thethreenumberis%-3d%-3d%-3d\n,a[store[0]],b[store[1]],c[store[2]]);40.returnMinSum;41.42.}43.44.intMinDistance(inta[],intb[],intc[])45.{46.intMinSum=0;//最小的绝对值和47.intSum=0;//计算三个绝对值的和，与最小值做比较48.intMinOFabc=0;//a[i],b[j],c[k]的最小值49.intcnt=0;//循环次数统计，最多是l+m+n次50.inti=0,j=0,k=0;//a,b,c三个数组的下标索引51.MinSum=(abs(a[i]-b[j])+abs(a[i]-c[k])+abs(b[j]-c[k]))/2;52.for(cnt=0;cnt=l+m+n;cnt++)53.{54.Sum=(abs(a[i]-b[j])+abs(a[i]-c[k])+abs(b[j]-c[k]))/2;55.MinSum=MinSumSum?MinSum:Sum;56.MinOFabc=Mymin(a[i],b[j],c[k]);//找到a[i],b[j],c[k]的最小值57.//判断哪个是最小值，做相应的索引移动58.if(MinOFabc==a[i])59.{60.if(++i=l)break;61.}//a[i]最小,移动i62.63.if(MinOFabc==b[j])64.{65.if(++j=m)break;66.}//b[j]最小,移动j67.if(MinOFabc==c[k])68.{69.if(++k=n)break;70.}//c[k]最小,移动k71.72.}73.returnMinSum;74.}75.intmain(void)76.{77.inta[l]={5,6,7};78.intb[m]={13,14,15,17};79.intc[n]={19,22,24,29,32,42};80.81.printf(\nByviolentsolution,theminis%d\n,Solvingviolence(a,b,c));82.printf(\nByOptimalsolution,theminis%d\n,MinDistance(a,b,c));83.return0;84.}5、这几天有点事，第5题还没仔细研究，要是解出来会第一时间更新博客！有求解方法的朋友欢迎评论！