【每日一题】-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]