V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
hakunamatata11
V2EX  ›  LeetCode

九章算法 | 字节跳动面试题:用 Rand7()实现 Rand10()

  •  
  •   hakunamatata11 · 2020-07-03 09:59:11 +08:00 · 2763 次点击
    这是一个创建于 1611 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

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

    在线评测地址:LintCode 领扣

    样例 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;
                }
            }
        }
    }
    

    更多语言代码参见:九章算法

    8 条回复    2020-07-03 17:36:59 +08:00
    churchmice
        1
    churchmice  
       2020-07-03 10:07:03 +08:00 via Android
    你这玩意说得有模有样,其实是错的吧
    你带个乘法,乘完之后你觉得 0-42 的概率是一样的吗?你不觉得 0 的概率大了点吗?这样的水平还搞什么九章算法,赶紧关门吧


    老老实实 rand7 两次,排列组合合计 49 种可能,随即取 10 种结果就好了
    lance6716
        2
    lance6716  
       2020-07-03 10:17:37 +08:00 via Android
    @churchmice 你理解错了,乘法不是两个随机数在乘
    agegcn
        3
    agegcn  
       2020-07-03 10:44:00 +08:00
    解法没问题。看成是 7 进制。2 次 rand7,有 49 种可能,取 40 种,因为 40 是 10 的倍数,丢弃剩下的 9 种可能
    alan0liang
        4
    alan0liang  
       2020-07-03 11:51:09 +08:00 via Android
    我很好奇这道题(或者说这种题) spj 是怎么做的……我给个 return rand7() 竟然就给 AC 了,但是 return 1 会 WA
    jeffdeng
        5
    jeffdeng  
       2020-07-03 15:31:26 +08:00
    rand7()*10/7 行不行
    hakunamatata11
        6
    hakunamatata11  
    OP
       2020-07-03 17:32:11 +08:00
    更多算法真题讲解可以试听 7/12 上午 9:30 的九章算法班噢: https://www.jiuzhang.com/course/71/?utm_source=sc-v2ex-fks
    kinsou
        7
    kinsou  
       2020-07-03 17:34:45 +08:00
    反手就是一个广告。
    Keyes
        8
    Keyes  
       2020-07-03 17:36:59 +08:00 via iPhone
    @kinsou 哈哈哈哈看到这种先拉到最底下看看有没有推广再看正文就对了

    推广就推广呗,非要整这些没用的
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   926 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 35ms · UTC 21:02 · PVG 05:02 · LAX 13:02 · JFK 16:02
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.