【leetcode】rand7()实现rand10()

2024-01-06 17:58
文章标签 leetcode 实现 rand7 rand10

本文主要是介绍【leetcode】rand7()实现rand10(),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

已有方法 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() ?

思路分析

首先,rand7()是[1,7]等概率,我们需要实现[1,10]等概率,因此需要扩展rand7().
第一个方法:x = rand7() + rand7() -1 范围在[1,13],若x > 10则重新循环,这样可以扩展范围,但不是等概率的。
比如 1 只能是1+1-1,而 2 可以是1+2-12+1-1.

我们可以考虑乘法实现。
首先,x = rand7(),x在[1,7]等概率,那么x-1[0,6]等概率,(x-1)*7[0,7,14,21,28,35,42]这7个离散的数等概率。
这时,(x-1)*7 + rand7()就在[1,49]等概率了。

我们可以利用的范围在[1,40],通过对10取模得到[1,10]的等概率。 x = 1+x%10
x > 40,剩余的数字将x -= 40会在[1,9],如果直接舍弃,利用率就比较低,因此我们对这 9 个数字再进行一次乘法扩展。

x = (x-1)*7 + rand7(),和上面一样,先是[0,8],乘以 7 后到[0, 7, 14... 56]的等概率离散数字,加上rand7()就是[1,63]等概率数字。
我们可以利用[1,60]对10取模得到等概率,对于x > 60的数据,将x -= 60可以用[1,2,3],接下来再进行一次乘法扩展。

x = (x-1)*7 + rand7(),得到[1,21]等概率数字,用到[1,20],剩下的 1 舍弃即可。

// The rand7() API is already defined for you.
// int rand7();
// @return a random integer in the range 1 to 7class Solution {
public:int rand10() {int x;while(1){x = (rand7()-1)*7 + rand7(); //[1,49], 1~40利用 41到49回收if(x <= 40) return 1+x%10;x -= 40;//下面是[1,9], 乘法扩展x = (x-1)*7 + rand7(); //[1,63]等概率if(x <= 60) return 1+x%10;//下面是[1,3], 乘法扩展x -= 60;x = (x-1)*7 + rand7(); //[1,21]if(x <= 20) return 1+x%10;}return x;}
};

这篇关于【leetcode】rand7()实现rand10()的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/577134

相关文章

python+OpenCV反投影图像的实现示例详解

《python+OpenCV反投影图像的实现示例详解》:本文主要介绍python+OpenCV反投影图像的实现示例详解,本文通过实例代码图文并茂的形式给大家介绍的非常详细,感兴趣的朋友一起看看吧... 目录一、前言二、什么是反投影图像三、反投影图像的概念四、反向投影的工作原理一、利用反向投影backproj

Django之定时任务django-crontab的实现

《Django之定时任务django-crontab的实现》Django可以使用第三方库如django-crontab来实现定时任务的调度,本文主要介绍了Django之定时任务django-cront... 目录crontab安装django-crontab注册应用定时时间格式定时时间示例设置定时任务@符号

Python中edge-tts实现便捷语音合成

《Python中edge-tts实现便捷语音合成》edge-tts是一个功能强大的Python库,支持多种语言和声音选项,本文主要介绍了Python中edge-tts实现便捷语音合成,具有一定的参考价... 目录安装与环境设置文本转语音查找音色更改语音参数生成音频与字幕总结edge-tts 是一个功能强大的

Java实现按字节长度截取字符串

《Java实现按字节长度截取字符串》在Java中,由于字符串可能包含多字节字符,直接按字节长度截取可能会导致乱码或截取不准确的问题,下面我们就来看看几种按字节长度截取字符串的方法吧... 目录方法一:使用String的getBytes方法方法二:指定字符编码处理方法三:更精确的字符编码处理使用示例注意事项方

使用Python和PaddleOCR实现图文识别的代码和步骤

《使用Python和PaddleOCR实现图文识别的代码和步骤》在当今数字化时代,图文识别技术的应用越来越广泛,如文档数字化、信息提取等,PaddleOCR是百度开源的一款强大的OCR工具包,它集成了... 目录一、引言二、环境准备2.1 安装 python2.2 安装 PaddlePaddle2.3 安装

嵌入式Linux之使用设备树驱动GPIO的实现方式

《嵌入式Linux之使用设备树驱动GPIO的实现方式》:本文主要介绍嵌入式Linux之使用设备树驱动GPIO的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录一、设备树配置1.1 添加 pinctrl 节点1.2 添加 LED 设备节点二、编写驱动程序2.1

Android 实现一个隐私弹窗功能

《Android实现一个隐私弹窗功能》:本文主要介绍Android实现一个隐私弹窗功能,本文通过实例代码给大家介绍的非常详细,感兴趣的朋友一起看看吧... 效果图如下:1. 设置同意、退出、点击用户协议、点击隐私协议的函数参数2. 《用户协议》、《隐私政策》设置成可点击的,且颜色要区分出来res/l

spring IOC的理解之原理和实现过程

《springIOC的理解之原理和实现过程》:本文主要介绍springIOC的理解之原理和实现过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、IoC 核心概念二、核心原理1. 容器架构2. 核心组件3. 工作流程三、关键实现机制1. Bean生命周期2.

Redis实现分布式锁全解析之从原理到实践过程

《Redis实现分布式锁全解析之从原理到实践过程》:本文主要介绍Redis实现分布式锁全解析之从原理到实践过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、背景介绍二、解决方案(一)使用 SETNX 命令(二)设置锁的过期时间(三)解决锁的误删问题(四)Re

Java根据IP地址实现归属地获取

《Java根据IP地址实现归属地获取》Ip2region是一个离线IP地址定位库和IP定位数据管理框架,这篇文章主要为大家详细介绍了Java如何使用Ip2region实现根据IP地址获取归属地,感兴趣... 目录一、使用Ip2region离线获取1、Ip2region简介2、导包3、下编程载xdb文件4、J