2017网易互娱雷火盘古实习生招聘笔试

第二题:
在一个NN的数组中寻找所有横,竖,左上到右下,右上到左下,四种方向的直线连续D个数字的和里面最大的值。
解答:
如果没有思路,就按照题目要求直接穷举遍历来做。
在实现的过程中,要考虑到边界问题,这也是这类题的陷阱所在。
第四题:
在一条无限长的跑道上,有N匹马在不同的位置上出发开始赛马。当开始赛马比赛后,所有的马开始以自己的速度一直匀速前进。每匹马的速度都不一样,且全部是同样的均匀随机分布。在比赛中当某匹马追上了前面的某匹马时,被追上的马就出局。 请问按以上的规则比赛无限长的时间后,赛道上剩余的马匹数量的数学期望是多少。
解答:
首先这是一个数学问题,首先梳理题目,每匹马的速度是不变的,这样可以按照马的速度进行排序,会有v1>v2>v3>...>vn。速度最大的马无论在什么位置都可以不被淘汰,所以速度最大的马存活的概率是1,然后速度第二大的马只有在速度最大的马后面才能存活,否则迟早都会被超越,由于只有在它前后两种情况,所以存活的概率是1/2,同理,速度第三大的马有三种排列情况(不考虑前面两匹马的排列),存活概率是1/3,依次类推,所以最后的情况就是1+1/2+1/3+...+1/n。
这里会有人问,为什么是加法,期望不是乘法吗?其实这个式子里边就包含了乘法,1+1/2+1/3+......1/n = 1
1+11/2+11/3+...+1*1/n。
注意不是通过每种排列情况计算能存活下来的马的数量,而是根据每匹马能存活的概率计算。