题目描述

已知rand5可以等概率随机获得[0,1,2,3,4]中的一个数字。要求用rand5来实现一个rand7，使得rand7可以等概率获得[0,1,2,3,4,5,6]中的一个数字。

思路解析

对rand5随机两次，获得一个坐标(x,y)，x=rand5，y=rand5。坐标(x,y)有25种可能，选取每3个坐标代表[0,1,2,3,4,5,6]中的一个数字，会用掉21个坐标。当(x,y)落在剩余的4个坐标中时，重复生成(x,y)，直到(x,y)有对应的数字。

代码实现

int rand5();
int rand7() {
	//坐标(x,y)和数字的映射
	int matrix[][5] = {
		{0, 0, 0, 1, 1},
		{1, 2, 2, 2, 3},
		{3, 3, 4, 4, 4},
		{5, 5, 5, 6, 6},
		{6, -1, -1, -1, -1}
	}
	
	int x = rand5(), y = rand5();
	while (matrix[x][y] == -1) {
		x = rand5();
		y = rand5();
	}
	return matrix[x][y];
}

概率分析

rand7获得[0,1,2,3,4,5,6]中的每个数字的概率为3/25 + 4/25 * 3/25 + 4/25 * 4/25 * 3/25 +... =1/7，符合题意。

最后分享一份力扣题目列表，这里既提供了经典题目列表，还提供了对应的高质量题解，让刷题更有效率。非常适合刚刚开始刷题或者为了找工作刷题的同学。

此题目列表包含的知识点是比较全面的。

常用的数据结构： 数组、字符串、链表、二叉树、图、前缀树、集合、映射、栈、队列、堆都有覆盖。

常用的解题方法： 递归、迭代、二分法、回溯、贪心、动态规划、位运算、双指针、模拟、拓扑排序、桶排序、单调栈、深度优先搜索、广度优先搜索都有覆盖。

  在线文档  

另外题目列表和题解都开源在github上了，欢迎大家提建议。

关注@溜达虎爱编程，学习算法不辛苦！