文档章节

美团笔试题

SibylY
 SibylY
发布于 2013/10/09 16:18
字数 645
阅读 62
收藏 0

已有一个随机数发生器,生成0的概率为p,生成1的概率为1-p,求如何利用这个随机数发生器制作一个生成1~n的概率都是 1/n 的发生器

制作 1 2 发生概率都是 1 / 2 的发生器,连续发生2次,则发生00,11的概率为p*p,(1-p)(1-p),发生10,01的概率都为p(1-p),在发生10时返回1,发生01时返回2,则发生1,2的概率相等

制作 1 2 3 发生概率都是 1 / 3的发生器,连续发生3次,则发生001,010,100的概率都为p*p*(1-P),或者是110,101,011概率都为p*(1-p)*(1-p),则用001,010,100分别对应1,2,3返回,即可使得发生1,2,3的概率都为1/3

字符串ABCD,可以由字符串BCDA或者CDAB通过循环移位而得到

考虑一下数组A中元素123456循环右移2位到底是怎么个情况!!!可不可以这样实现呢?将数组A分成两个部分:A[0~n-k-1] 和 A[n-k~n-1] ,将这两个部分分别翻转,然后放在一起在翻转(逆序)。具体是这样的:

(1)翻转1234:123456 ---> 432156

(2)翻转56:     432156 ---> 432165

(3)翻转432165:432165 ---> 561234



//逆序
 2 void Reverse(int A[],int b,int e)
 3 {
 4     for(;b < e;b++,e--)
 5     {
 6         int temp = A[b];
 7         A[b] = A[e];
 8         A[e] = temp;
 9     }
10 }
11 //循环右移
12 void RightShift(int A[],int,int n,int k)
13 {
14     Reverse(A,0,n-k-1);
15     Reverse(A,n-k,n-1);
16     Reverse(A,0,n-1);
17 }
复制代码
细心的读者可能就发现,这里的右移并没有说小于n呀,那么一个k>n那就会出现问题,经过简单的分析,我们发现如果A[]={1,2,3,4,5,6},数组长度是6,那么循环右移7位和循环右移1位是一样的,所以只需要把函数RightShift()中的k取值为k=k%n。如此一来问题就解决了。


【列方程】有四个足球队A,B,C,D分入同一个小组进行单循环比赛,争夺出线权,比赛规定:胜一场得3分,平一场得1分,负一场得0分,小组中名列第一的出现。小组赛结束后,如果A队积分为7分。讨论:①这一小组中共进行多少场比赛?②A队的成绩是几胜几平几负?③请你判断A队能否一定出线?

© 著作权归作者所有

共有 人打赏支持
SibylY
粉丝 29
博文 438
码字总数 354912
作品 0
海淀
程序员
私信 提问
90 道名企笔试和算法题 (含答题讨论)

(点击上方公众号,可快速关注) 节选自「算法爱好者」微信公号的精选算法题和名企笔试题。 问:如何获取题目列表? 答:① 长摁二维码关注「算法爱好者」,② 然后给它发送 名企笔试 或 算法...

Python开发者
01/21
0
0
【干货分享】面试小技巧

纪念一下第一份面试经历 美团面试主要就是分为笔试和面试,笔试以后我恬不知耻地去霸面了(其实也不觉得有什么恬不知耻,权当考察去了)但其实笔试完没多久后我就接到了约面试时间的电话了。...

路过全世界
2017/04/26
0
0
2018年,作为应届生,求职的我

大学四年,转眼即逝。 四年期间,没有拿过一次奖学金,唯有拿过钱的只有贫困补助。 有参加过社团或是部门,有收获友谊,但不争的我,有想过成为某某部或社团的部长或是副部长,但却不怎么行动...

北极星_51ae
2017/10/21
0
0
2018年,作为应届生,求职的我

大学四年,转眼即逝。 四年期间,没有拿过一次奖学金,唯有拿过钱的只有贫困补助。 有参加过社团或是部门,有收获友谊,但不争的我,有想过成为某某部或社团的部长或是副部长,但却不怎么行动...

北极星_51ae
2017/10/21
0
0
机器学习实习生面试总结(阿里 腾讯等)

今年来一直在找暑期实习,现在基本已经确定了,前后历经差不多2个月吧,发现了很多自己的缺点,同时也希望写出来供需要的人参考了解 先说下我自己的情况吧,决定去腾讯TEG的机器学习岗实习了...

Gavin__Zhou
2017/05/01
0
0

没有更多内容

加载失败,请刷新页面

加载更多

PHP生成CSV之内部换行

当我们使用PHP将采集到的文件内容保存到csv文件时,往往需要将采集内容进行二次过滤处理才能得到需要的内容。比如网页中的换行符,空格符等等。 对于空格等处理起来都比较简单,这里我们单独...

豆花饭烧土豆
54分钟前
1
0
使用 mjml 生成 thymeleaf 邮件框架模板

发邮件算是系统开发的一个基本需求了,不过搞邮件模板实在是件恶心事,估计搞过的同仁都有体会。 得支持多种客户端 支持响应式 疼彻心扉的 outlook 多数客户端只支持 inline 形式的 css 布局...

郁也风
57分钟前
4
0
让哲学照亮我们的人生——读《医务工作者需要学点哲学》有感2600字

让哲学照亮我们的人生——读《医务工作者需要学点哲学》有感2600字: 作者:孙冬梅;以前读韩国前总统朴槿惠的著作《绝望锻炼了我》时,里面有一句话令我印象深刻,她说“在我最困难的时期,...

原创小博客
今天
3
0
JAVA-四元数类

public class Quaternion { private final double x0, x1, x2, x3; // 四元数构造函数 public Quaternion(double x0, double x1, double x2, double x3) { this.x0 = ......

Pulsar-V
今天
17
0
Xshell利用Xftp传输文件,使用pure-ftpd搭建ftp服务

Xftp传输文件 如果已经通过Xshell登录到服务器,此时可以使用快捷键ctrl+alt+f 打开Xftp并展示Xshell当前的目录,之后直接拖拽传输文件即可。 pure-ftpd搭建ftp服务 pure-ftpd要比vsftp简单,...

野雪球
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部