【每日一题】-2020年2月20日 造rand10() 随机1~10

[watchpoints]

来源：编程之法：面试和算法心得

已知有个rand7()的函数，返回1到7随机自然数，让利用这个rand7()构造rand10() 随机1~10。

这题主要考的是对概率的理解。程序关键是要算出rand10，1到10，十个数字出现的考虑都为10%.

[watchpoints]

https://www.jianshu.com/p/84bba3df9748 / Returns a random level for the new skiplist node we are going to create.

• 返回一个随机值，用作新跳跃表节点的层数。
• The return value of this function is between 1 and ZSKIPLIST_MAXLEVEL
• (both inclusive), with a powerlaw-alike distribution where higher
• levels are less likely to be returned.
• 返回值介乎 1 和 ZSKIPLIST_MAXLEVEL 之间（包含 ZSKIPLIST_MAXLEVEL），
• 根据随机算法所使用的幂次定律，越大的值生成的几率越小。

• T = O(N) */ int zslRandomLevel(void) { int level = 1;

  while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF)) level += 1;

  return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL; }

class Solution extends SolBase { public int rand10() { int x = rand7(); //若为7，重新取值，使x为奇/偶数的概率一样为3/7 while(x==7){ x = rand7(); } int res = 0; //奇数取1-5，偶数取6-10 if((x%2 == 0)){ res = 5; } int z = rand7(); //大于5，则重新取值 while(z>5){ z = rand7(); } return res + z; } }

作者：liu-jia-liang 链接：https://leetcode-cn.com/problems/implement-rand10-using-rand7/solution/javajie-fa-by-liu-jia-liang-10/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

[watchpoints]

[watchpoints]

[watchpoints]