当前位置: 首页 > news >正文

LeetCode-470. 用 Rand7() 实现 Rand10()【数学 拒绝采样 概率与统计 随机化】

LeetCode-470. 用 Rand7 实现 Rand10【数学 拒绝采样 概率与统计 随机化】

  • 题目描述:
  • 解题思路一:首先说一个结论就是`(rand_X() - 1) × Y + rand_Y() ==> [1,X*Y]`,即可以等概率的生成[1, X * Y]范围的随机数,其实就像军训的时候报数,Y是每一行的人数,X是列数【参考下面的图】。第二就是拒绝采样,效果是能够减少调用rand7()的调用次数。我们在利用`(rand_7() - 1) × 7 + rand_7() ==> [1,7*7]`得到rand49()的时候,我们希望能够等概率的生成[1,10]的随机数,那么可以拒绝掉大于40的数。即`if num<=40:`才进行采样。
  • 解题思路二:0
  • 解题思路三:0

题目描述:

给定方法 rand7 可生成 [1,7] 范围内的均匀随机整数,试写一个方法 rand10 生成 [1,10] 范围内的均匀随机整数。

你只能调用 rand7() 且不能调用其他方法。请不要使用系统的 Math.random() 方法。

每个测试用例将有一个内部参数 n,即你实现的函数 rand10() 在测试时将被调用的次数。请注意,这不是传递给 rand10() 的参数。

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

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

示例 3:
输入: 3
输出: [3,8,10]

提示:
1 <= n <= 105

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

解题思路一:首先说一个结论就是(rand_X() - 1) × Y + rand_Y() ==> [1,X*Y],即可以等概率的生成[1, X * Y]范围的随机数,其实就像军训的时候报数,Y是每一行的人数,X是列数【参考下面的图】。第二就是拒绝采样,效果是能够减少调用rand7()的调用次数。我们在利用(rand_7() - 1) × 7 + rand_7() ==> [1,7*7]得到rand49()的时候,我们希望能够等概率的生成[1,10]的随机数,那么可以拒绝掉大于40的数。即if num<=40:才进行采样。

请添加图片描述
为了充分利用被拒绝的采样结果,即舍弃掉[41, 49]这9个数。我们可以使用a = num - 40得到rand9,从而可以得到(rand_9() - 1) × 7 + rand_7() ==> [1,9*7]得到rand63,从而对rand63进行采样。这样之后的就不难理解了。

# The rand7() API is already defined for you.
# def rand7():
# @return a random integer in the range 1 to 7class Solution:def rand10(self):""":rtype: int"""while True:a = rand7()b = rand7()num = (a-1)*7 + b # rand49if num<=40:return num%10 + 1a = num - 40 # rand9b = rand7()num = (a-1)*7 + b # rand63if num<=60:return num%10 + 1a = num - 60 # rand3b = rand7()num = (a-1)*7 + b # rand21if num<=20:return num%10 + 1

时间复杂度:期望时间复杂度为O(1),但最坏情况下会达到 (∞)(一直被拒绝)。
空间复杂度:O(1)
分析一下rand7()调用次数的 期望值:
首先调用2次得到a,b
然后拒绝采样一次概率是9/49
第二次是9/49 * 3/63
第三次是9/49 * 3/63 * 1/21就是进入下一轮while循环了。所以是一个等比数列。
a = 2 + 9 49 + 9 49 ⋅ 3 63 / / 是每次采样成功的概率 b = 9 49 ⋅ 3 63 ⋅ 1 21 / / 是每次进入下一轮循环的概率(等比数列的公比) E ( # c a l l ) = a ⋅ 1 1 − b ≈ 2.19333 \begin{align} a &= 2 + \frac{9}{49}+\frac{9}{49}·\frac{3}{63} \quad // \text{是每次采样成功的概率} \notag \\ b &= \frac{9}{49}·\frac{3}{63}·\frac{1}{21} \quad // \text {是每次进入下一轮循环的概率(等比数列的公比)} \notag \\ E(\#call) &= a·\frac{1}{1-b} \notag \\ &\approx 2.19333 \end{align} abE(#call)=2+499+499633//是每次采样成功的概率=499633211//是每次进入下一轮循环的概率(等比数列的公比)=a1b12.19333
所以期望次数是2.19332

解题思路二:0


解题思路三:0


相关文章:

LeetCode-470. 用 Rand7() 实现 Rand10()【数学 拒绝采样 概率与统计 随机化】

LeetCode-470. 用 Rand7 实现 Rand10【数学 拒绝采样 概率与统计 随机化】 题目描述&#xff1a;解题思路一&#xff1a;首先说一个结论就是(rand_X() - 1) Y rand_Y() > [1,X*Y]&#xff0c;即可以等概率的生成[1, X * Y]范围的随机数&#xff0c;其实就像军训的时候报数…...

通达信指标公式19:龙虎榜股票池——主力控盘度的计算方法

0.小红牛本指标&#xff0c;选股的思路说明&#xff1a;控盘度&#xff0c;又称主力控盘&#xff0c;是指主力控制了某只股票的大部分流通股&#xff0c;从而控制了股票的价格。主力控盘的目的通常是为了获取更多的收益&#xff0c;通过控制股票价格来实现其策略。所以首要分析…...

手搓图片滑动验证码_JavaScript进阶

手搓图片滑动验证码 背景代码效果图展示网站 背景 在做前端项目开发的时候&#xff0c;少不了登录注册部分&#xff0c;既然有登录注册就少不了机器人验证&#xff0c;验证的方法有很多种&#xff0c;比如短信验证码、邮箱验证码、图片滑动、图片验证码等。 由于鄙人在开发中…...

Linux服务器超级实用的脚本

1.使用INOTIFY+RSYNC自动实时同步数据 代码执行: bash inotify_rsyncs.sh :cat inotify_rsyncs.sh 脚本内容如下: #!bing/bash # Author: reyn #检测/data路径下的文件变化,排除Temp目录 INOTIFY_CMD="inotifywait -mrq -e modify,create,move,delete /data/ --exc…...

IntelliJ IDEA安装使用教程#intellij idea

做为基础开发软件&#xff0c;idea、pycharm、phpstorm是高级企业级开发中常用的图形化工具。 安装非常简单&#xff1a;去官网下载即可&#xff0c;有社区版本、有企业版本&#xff1a; IntelliJ IDEA – 领先的 Java 和 Kotlin IDE 因版权问题&#xff1a;这里不方面多讲。…...

【组合数学】容斥鸽巢原理

目录 1. 容斥原理容斥原理三种形式 2. 容斥原理应用有限重复数的多重集合的 r 组合数错排问题 3. 鸽巢原理4. Ramsey 定理 1. 容斥原理 容斥原理提供了一种通过计算每个单独集合的大小&#xff0c;然后修正重复计数的方法&#xff0c;从而得到多个集合并集大小的计算方法。它通…...

视频后期特效处理软件 Motion 5 mac中文版

Motion mac是一款运动图形和视频合成软件&#xff0c;适用于Mac OS平台。 Motion mac软件特点 - 精美的效果&#xff1a;Motion提供了多种高质量的运动图形和视频效果&#xff0c;例如3D效果、烟雾效果、粒子效果等&#xff0c;方便用户制作出丰富多彩的视频和动画。 - 高效的工…...

【智能家居】一、工厂模式实现继电器灯控制

用户手册对应的I/O 工厂模式实现继电器灯控制 代码段 controlDevice.h&#xff08;设备设备&#xff09;main.c&#xff08;主函数&#xff09;bathroomLight.c&#xff08;浴室灯&#xff09;bedroomLight.c&#xff08;卧室灯&#xff09;restaurantLight.c&#xff08;餐厅…...

第三节:提供者、消费者、Eureka

一、 提供者 消费者&#xff08;就是个说法、定义&#xff0c;以防别人叭叭时听不懂&#xff09; 服务提供者&#xff1a;业务中被其他微服务调用的服务。&#xff08;提供接口给其他服务调用&#xff09;服务消费者&#xff1a;业务中调用其他微服务的服务。&#xff08;调用…...

Leetcode刷题详解——等差数列划分

1. 题目链接&#xff1a;413. 等差数列划分 2. 题目描述&#xff1a; 如果一个数列 至少有三个元素 &#xff0c;并且任意两个相邻元素之差相同&#xff0c;则称该数列为等差数列。 例如&#xff0c;[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。 给你一个整数数组 …...

导出主机上所有docker 镜像并导入到其它主机

保存镜像列表到文件 docker images --format “{{.Repository}}:{{.Tag}}” > image_list.txt 导出列表中所有镜像到tar文件 cat image_list.txt | xargs -L 1 docker save -o all_images.tar 导入tar包中所有镜像 docker load -i all_images.tar...

HTML5+CSS3+JS小实例:焦点图波浪切换动画特效

实例:焦点图波浪切换动画特效 技术栈:HTML+CSS+JS 字体图标库:Font Awesome 效果: 源码: 【HTML】 <!DOCTYPE html> <html><head><meta http-equiv="content-type" content="text/html; charset=utf-8"><meta name=&…...

Mac电脑如何安装git

一、简介 在Mac上安装Git之前&#xff0c;可以先使用git --version来查看一下是否安装了Git&#xff0c;因为Mac系统可能自带了Git&#xff0c;或者在你安装XCode&#xff08;或者XCode的命令行工具&#xff09;时&#xff0c;可能已经安装了 Git。 如果Mac还没有安装Git的话&…...

macOS本地调试k8s源码

目录 准备工作创建集群注意点1. kubeconfig未正常加载2. container runtime is not running3. The connection to the server 172.16.190.132:6443 was refused - did you specify the right host or port?4. 集群重置5.加入子节点 代码调试 准备工作 apple m1芯片 安装vmwa…...

JS 实现一键复制文本内容

1、演示&#xff1a; 2、代码 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>一键复制</title&g…...

【Linux】echo命令使用

​echo命令 功能是在显示器上显示一段文字&#xff0c;一般起到一个提示的作用。此外&#xff0c;也可以直接在文件中写入要写的内容。也可以用于脚本编程时显示某一个变量的值&#xff0c;或者直接输出指定的字符串。 ​ 著者 由布莱恩福克斯和切特拉米撰写。 语法 echo […...

Day03 嵌入式---中断

目录 一、简单介绍 二、总体框架 三、NVIC 3.2 NVIC的寄存器 3.3 中断向量表 3.4 中断优先级 3.5 NVIC优先级分组 3.6 NVIC配置 3.6.1、设置中断分组 3.6.2、初始化 四、EXTI 外部中断 4.1.EXTI的基本概念 4.2.EXTI的⼯作原理 4.3 EXTI配置 五、SYSCFG 5.1 SYS…...

wpf devexpress 使用IDataErrorInfo实现input验证

此处下载源码 当form初始化显示&#xff0c;Register按钮应该启动和没有输入错误应该显示。如果用户点击注册按钮在特定的输入无效数据&#xff0c;form将显示输入错误和禁用的注册按钮。实现逻辑在标准的IDataErrorInfo接口。请查阅IDataErrorInfo接口&#xff08;System.Com…...

shell_81.Linux在命令行中创建使用函数

在命令行中使用函数 在命令行中创建函数 两种方法 单行方式来定义函数&#xff1a; $ function divem { echo $[ $1 / $2 ]; } $ divem 100 5 20 $ 当你在命令行中定义函数时&#xff0c;必须在每个命令后面加个分号&#xff0c;这样 shell 就能知道哪里是命令的起止了&am…...

鱼香ROS一键安装命令(支持微信、docker、ros等)

按照指定的数字选择即可。 wget http://fishros.com/install -O fishros && . fishros小鱼的一键安装系列 [14个ROS版本任你选]一键安装Docker使用指南...

JavaSec-RCE

简介 RCE(Remote Code Execution)&#xff0c;可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景&#xff1a;Groovy代码注入 Groovy是一种基于JVM的动态语言&#xff0c;语法简洁&#xff0c;支持闭包、动态类型和Java互操作性&#xff0c…...

23-Oracle 23 ai 区块链表(Blockchain Table)

小伙伴有没有在金融强合规的领域中遇见&#xff0c;必须要保持数据不可变&#xff0c;管理员都无法修改和留痕的要求。比如医疗的电子病历中&#xff0c;影像检查检验结果不可篡改行的&#xff0c;药品追溯过程中数据只可插入无法删除的特性需求&#xff1b;登录日志、修改日志…...

【机器视觉】单目测距——运动结构恢复

ps&#xff1a;图是随便找的&#xff0c;为了凑个封面 前言 在前面对光流法进行进一步改进&#xff0c;希望将2D光流推广至3D场景流时&#xff0c;发现2D转3D过程中存在尺度歧义问题&#xff0c;需要补全摄像头拍摄图像中缺失的深度信息&#xff0c;否则解空间不收敛&#xf…...

STM32标准库-DMA直接存储器存取

文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA&#xff08;Direct Memory Access&#xff09;直接存储器存取 DMA可以提供外设…...

cf2117E

原题链接&#xff1a;https://codeforces.com/contest/2117/problem/E 题目背景&#xff1a; 给定两个数组a,b&#xff0c;可以执行多次以下操作&#xff1a;选择 i (1 < i < n - 1)&#xff0c;并设置 或&#xff0c;也可以在执行上述操作前执行一次删除任意 和 。求…...

Psychopy音频的使用

Psychopy音频的使用 本文主要解决以下问题&#xff1a; 指定音频引擎与设备&#xff1b;播放音频文件 本文所使用的环境&#xff1a; Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

(转)什么是DockerCompose?它有什么作用?

一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用&#xff0c;而无需手动一个个创建和运行容器。 Compose文件是一个文本文件&#xff0c;通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...

如何理解 IP 数据报中的 TTL?

目录 前言理解 前言 面试灵魂一问&#xff1a;说说对 IP 数据报中 TTL 的理解&#xff1f;我们都知道&#xff0c;IP 数据报由首部和数据两部分组成&#xff0c;首部又分为两部分&#xff1a;固定部分和可变部分&#xff0c;共占 20 字节&#xff0c;而即将讨论的 TTL 就位于首…...

Android第十三次面试总结(四大 组件基础)

Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成&#xff0c;用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机&#xff1a; ​onCreate()​​ ​调用时机​&#xff1a;Activity 首次创建时调用。​…...

mac 安装homebrew (nvm 及git)

mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用&#xff1a; 方法一&#xff1a;使用 Homebrew 安装 Git&#xff08;推荐&#xff09; 步骤如下&#xff1a;打开终端&#xff08;Terminal.app&#xff09; 1.安装 Homebrew…...