【LeetCode】均等概率问题，我有妙招！

在解决算法问题中我们会经常遇到要求均等概率的问题， 以leetcode 470. 用 Rand7() 实现 Rand10() 为例。

成都创新互联专业IDC数据服务器托管提供商，专业提供成都服务器托管，服务器租用，四川乐山服务器托管，四川乐山服务器托管，成都多线服务器托管等服务器托管服务。

• 已有方法 rand7 可生成 1 到 7 范围内的均匀随机整数，试写一个方法 rand10 生成 1 到 10 范围内的均匀随机整数。
• ️ 不讨论最优解，只讨论算法思路 看到均等概率的问题， 我们最先要想到转成2进制来处理，思路是让均等概率转换成均等概率出现0和1， 再由 0 和 1 ，增加位数来处理均等概率的其他数。拆解下上面的题目 我们使用 Rand7 转成 Rand2 。让 Rand2 的返回结果均等的出现 0 和 1， 我们可以用4位二进制数来生成包含 0 ～ 15 的数。舍弃 10～15，保留 0 到 9 ，结果加1 就是 1～ 10的随机数。

第一步转化二进制函数

Rand7() 的结果是均等概率 出现 1,2,3,4,5,6 拆解下就是 均等概率出现 1,2,3 和 4,5,6 当出现 1,2,3 的时候返回 0 ，当出现 4,5,6 的时候返回 1

 
 
 
 

  
  
  
  
declare function rand7(): number 
  
  
  
  
function Rand2(): number { 
  
  
  
  
 return Rand7() > 3 ? 1 : 0 
  
  
  
  
} 
 
 
 
 

现在我们有了过渡函数 Rand2 , 那么我们使用随机生成4位二进制数那么我就会得到 一个 均等生成 0 ～ 15 的函数

 
 
 
 

  
  
  
  
function Rand15(): number { 
  
  
  
  
 return Rand2() * 2 * 2 * 2 + Rand2() * 2 * 2  + Rand2() * 2  + Rand2() 
  
  
  
  
} 
 
 
 
 

上面代码略蠢，我们用移位的方法优化下， 左移操作符是二进制进位的。

 
 
 
 

  
  
  
  
function Rand15(): number { 
  
  
  
  
 return (rand2() << 3) + (rand2() << 2)  + (rand2() << 1)  +  (rand2() << 0) 
  
  
  
  
} 
 
 
 
 

那么最终的 Rand10() 函数， 我们只要舍弃掉 10～15 就可以了

 
 
 
 

  
  
  
  
function Rand10(): number { 
  
  
  
  
 let num: number 
  
  
  
  
 // 使用do while 循环 遇到小于10 的结束循环返回结果，遇到大的继续 roll  
  
  
  
  
 do { 
  
  
  
  
   num = Rand15() 
  
  
  
  
 } while ( num > 9) 
  
  
  
  
  return num + 1 // 别忘记 + 1  
  
  
  
  
} 
 
 
 
 

这道题解决完了， 再来一道题，思路也是用二进制均等概率的。

• 给一个随意函数f，以P概率返回 0 ， 以 1-P 的概率返回1 这是你唯一可以使用的随机机制，如何实现等概率返回 0 和 1
• 思路还是用二进制升位的方式， 0 的概率是 P 1 的概率是 1- P

可以得出 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 这两个数字不想等即可

 
 
 
 

  
  
  
  
declare function f(): 0 | 1 
  
  
  
  
function round01 () : number { 
  
  
  
  
 let num : number 
  
  
  
  
 do { 
  
  
  
  
  num = f() 
  
  
  
  
  } while ( num == f()) 
  
  
  
  
 return num 
  
  
  
  
} 
 
 
 
 

 总结

 两道小题都是用二进制位来解决的算法题。解题思路也是两个大致的方向，一个是把高进制的数拆解成均等的二进制均等概率，然后再组成目标数。另一个是通过升位来构造均等概率。

当前文章：【LeetCode】均等概率问题，我有妙招！
标题链接：http://www.mswzjz.cn/qtweb/news37/300087.html

攀枝花网站建设、攀枝花网站运维推广公司-贝锐智能，是专注品牌与效果的网络营销公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 贝锐智能