阿里2020/03/27笔试

第一题:
给定两个等长字符串S,T。可以移动S的任意字符到其末尾。问最少移动几次可以使的S和T完全相同。不可以的话输出-1;
输入:abc
bac
输出  2(先移动a到末尾,再移动c到末尾)

解答:比较简单。

第二题:
给定n,给定n个区间[li,ri]。
取n次,每次从第i个区间中取一个数。
问取得的n个数中最小的数的期望。

输入:2
1 3
2 3
输出1.833333(保留六位好像)

解释:最小为1,可以取(1,2)(1,3)。2种。概率为2/6,期望为2/6*1
最小为2,可以取(2,2)(2,3)(3,2),期望为3/6*2
最小为3,可以取(3,3),期望为1/6*3
加起来。

解答:求解答,不会做。
#阿里巴巴春招实习##阿里巴巴##笔试题目#
全部评论
第二题题解:不要直接算最小值为x的期望p[x]。算最小值大于x的期望f[x],则p[x]=f[x-1]-f[x]. 前者复杂度2000^3。后者2000^2。
点赞 回复 分享
发布于 2020-03-27 14:38
n<2000,li与ri<2000
点赞 回复 分享
发布于 2020-03-27 11:08

相关推荐

04-17 10:16
门头沟学院 Java
不河狸啊:为什么我的是已送达,连已读都没有
点赞 评论 收藏
分享
评论
点赞
5
分享

创作者周榜

更多
牛客网
牛客企业服务