专栏首页Michael阿明学习之路LeetCode 470. 用 Rand7() 实现 Rand10()(随机概率)

LeetCode 470. 用 Rand7() 实现 Rand10()(随机概率)

1. 题目

已有方法 rand7 可生成 1 到 7 范围内的均匀随机整数,试写一个方法 rand10 生成 1 到 10 范围内的均匀随机整数。

不要使用系统的 Math.random() 方法。

示例 1:
输入: 1
输出: [7]

示例 2:
输入: 2
输出: [8,4]

示例 3:
输入: 3
输出: [8,1,10]
 
提示:
rand7 已定义。
传入参数: n 表示 rand10 的调用次数。
 

进阶:
rand7()调用次数的 期望值 是多少 ?
你能否尽量少调用 rand7() ?

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/implement-rand10-using-rand7 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题

class Solution {
	int a, b;
public:
    int rand10() {
        a = rand7();
        b = rand7();
        while(a == 7)
        	a = rand7(); //a = 1--6均匀分布
        while(b > 5)
        	b = rand7(); //b = 1--5均匀分布
        if(a%2)	//a有50%的概率是奇数(1,3,5)
        	return b;//1--5
        return 5+b;//6--10(a有50%概率是偶数)
    }
};

调用次数

2+\sum_{i=1}^n i/{7^i}+\sum_{i=1}^n i*{2^i}/{7^i}=2.75
>>> sum = 2
>>> for i in range(1,10000):
	sum += (i+i*pow(2,i))/pow(7,i)

	
>>> sum
2.7544444444444447

看官方解法: 有个疑问 : 1-49的分布概率是不均匀的吧,比如 6= 1X6 = 2X3,而 7 = 1X7

class Solution {
	int a, b, n;
public:
    int rand10() {
    	do
    	{
	        a = rand7();
	        b = rand7();
	        n = (a-1)*7+b;
	    }while(n > 40);
	    return (n-1)%10 + 1;
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 程序员面试金典 - 面试题 17.04. 消失的数字(数学/位运算)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/missing-number-lcci 著作权归领扣...

    Michael阿明
  • LeetCode 666. 路径和 IV(树的遍历)

    给定一个包含三位整数的升序数组,表示一棵深度小于 5 的二叉树, 请你返回从根到所有叶子结点的路径之和。

    Michael阿明
  • LeetCode 408. 有效单词缩写

    给一个 非空 字符串 s 和一个单词缩写 abbr ,判断这个缩写是否可以是给定单词的缩写。

    Michael阿明
  • 以Spring Cache扩展为例介绍如何进行高效的源码的阅读

    日常开发中,需要用到各种各样的框架来实现API、系统的构建。作为程序员,除了会使用框架还必须要了解框架工作的原理。这样可以便于我们排查问题,和自定义的扩展。那么...

    方丈的寺院
  • 聊聊dubbo的DubboSwaggerService

    dubbo-2.7.2/dubbo-rpc/dubbo-rpc-rest/src/main/java/org/apache/dubbo/rpc/protocol...

    codecraft
  • 聊聊dubbo的DubboSwaggerService

    dubbo-2.7.2/dubbo-rpc/dubbo-rpc-rest/src/main/java/org/apache/dubbo/rpc/protocol...

    codecraft
  • Docker简介、常用命令与实践(二)

    Docker Hub 上有大量的高质量的镜像可以用,这里我们就说一下怎么获取这些镜像。 从 Docker 镜像仓库获取镜像的命令是 docker pull。其命...

    唐成勇
  • bootstrap快速入门笔记(九)-响应式工具

    从 v3.2.0 版本起,形如 .visible-*-* 的类针对每种屏幕大小都有了三种变体,每个针对 CSS 中不同的 display 属性,列表如下:

    用户3055976
  • 思维导图学Java虚拟机

    本篇文章是对周志明的《深入理解Java虚拟机》的读书笔记,思维导图使用Mindjet MindManager。曾经看到过这样一句话:

    Yano_nankai
  • 金融再进化:开局金融科技,终局数字科技

    持续不断的互联网金融乱象,正在生动地告诉我们,仅仅只是将“互联网”和“金融”两种元素相加,无法带来行业的持久发展。金融行业科技化的过程必须找到互联网金融之外的方...

    孟永辉

扫码关注云+社区

领取腾讯云代金券