【LeetCode】均等概率问题
发布时间:2021-03-25 12:52:00 所属栏目:动态 来源:互联网
导读:决算法问题中我们会经常遇到要求均等概率的问题, 以leetcode 470. 用 Rand7() 实现 Rand10() 为例。 已有方法 rand7 可生成 1 到 7 范围内的均匀随机整数,试写一个方法 rand10 生成 1 到 10 范围内的均匀随机整数。 不讨论最优解,只讨论算法思路 看到均等
决算法问题中我们会经常遇到要求均等概率的问题, 以leetcode 470. 用 Rand7() 实现 Rand10() 为例。
第一步转化二进制函数Rand7() 的结果是均等概率 出现 1,2,3,4,5,6 拆解下就是 均等概率出现 1,2,3 和 4,5,6 当出现 1,2,3 的时候返回 0 ,当出现 4,5,6 的时候返回 1这道题解决完了, 再来一道题,思路也是用二进制均等概率的。
可以得出 00 的概率是 P*P , 11 的概率是 (1-P) * (1-P) 01 的概率是 P * (1-P) 10 的概率是 (1-P) * P 而这两个是相等的(交换率) 那么我们只要 保留 01 和 10 舍弃 00 和 11 就会获得均等概率 P * (1-P)
10 和 01 这两个数字不想等即可 (编辑:江门站长网) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |
站长推荐