[leetcode/lintcode 题解] 字节跳动面试题:用 Rand7()实现 Rand10()

2020-07-02 17:44:04 +08:00
 hakunamatata11

已有方法 rand7 可生成 1 到 7 范围内的均匀随机整数,试写一个方法 rand10 生成 1 到 10 范围内的均匀随机整数。 不要使用系统的 Math.random()方法

  1. rand7 已定义。
  2. 传入参数: n 表示 rand10 的调用次数。

在线评测地址:https://www.lintcode.com/problem/implement-rand10-using-rand7/?utm_source=sc-v2ex-fks

样例 1:

输入:1
输出:[7]

样例 2:

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

样例 3:

输入:3
输出:[8,1,10]

[题解]
考点: 随机数 题解:

  1. [1,7] 的随机数, 减一-> [0,6] 的随机数,乘以 7 -> {0,7,14,21,28,35,42} 中的随机数
  2. [1,7]的随机数 1+2 是[1,49]的随机数,且均匀生成 -> [0,48]的随机数取出[0,39]区间 取到的概率是 1/49 除以 4-> [0,9]的随机数 加一->[1,10]的随机数
public class Solution extends SolBase{
    public  int rand10() {
        while(true){
           int rand49 = (rand7() - 1) * 7 + rand7() - 1;
            if(rand49 <= 39) {
                return rand49 / 4 + 1;
            }
        }
    }
}

更多语言代码参见:https://www.jiuzhang.com/solution/implement-rand10-using-rand7/?utm_source=sc-v2ex-fks

772 次点击
所在节点    推广
0 条回复

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/686630

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX