LeetCode刷题实战470：用 Rand7() 实现 Rand10()-技术圈

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 用 Rand7() 实现 Rand10()，我们先来看题面：

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

Given the API rand7() that generates a uniform random integer in the range [1, 7], write a function rand10() that generates a uniform random integer in the range [1, 10]. You can only call the API rand7(), and you shouldn't call any other API. Please do not use a language's built-in random API.

Each test case will have one internal argument n, the number of times that your implemented function rand10() will be called while testing. Note that this is not an argument passed to rand10().

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

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

示例

示例 1:
输入: 1
输出: [7]

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

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

解题

(rand_Y - 1) * X + rand_X => 可以生成[1, X*Y]的等概率随机数。

在本题中，可生成1-49的随机数，我们可以只取前40个，当数字大于40时，继续产生1-49的随机数，直到小于等于40停止。

在得到1-40的随机数后，对10取余再加1，即可得到1到10范围内的随机数字

class Solution {
public:
    int rand10() {
        int ans = 0;
        do{
            ans = (rand7() - 1) * 7 + rand7();
        }while(ans > 40);

        return ans % 10 + 1;
    }
};