【Leetcode】470. Implement Rand10() Using Rand7()

题目地址：

https://leetcode.com/problems/implement-rand10-using-rand7/description/

假设我们有一个API叫rand7()可以等概率随机产生$1\sim 7$中的一个数，要求利用这个API实现rand10()。

参考https://blog.csdn.net/qq_46105170/article/details/109269492。考虑API被叫的次数，每轮有$\frac{40}{49}$的概率停止，从而轮数的期望就是$\frac{49}{40}$，而每轮叫两次，所以叫的次数的期望是$\frac{49}{20}$。代码如下：

import java.util.Random;

class Solution extends SolBase {
    
    public int rand10() {
    
        while (true) {
    
            int x = rand7(), y = rand7();
            int n = 7 * (x - 1) + y;
            if (n <= 40) {
    
                return (n - 1) / 4 + 1;
            }
        }
    }
}

abstract class SolBase {
    
    int rand7() {
    
        return new Random().nextInt(7) + 1;
    }
}

平均时间复杂度$O(1)$，空间$O(1)$。

C++：

class Solution {
    
 public:
  int rand10() {
    
	while (true) {
    
      int t = (rand7() - 1) * 7 + rand7();
      if (t <= 40) return (t - 1) / 4 + 1;
    }
  }
};

时空复杂度一样。