Saturday, December 1, 2018
[Summary]Random
Fisher Yates Algorithm
洗牌算法,O(n)时间生成一个random的排列。
讲解:
Fisher Yates
例题:
Shuffle an Array 解答
Reservoir Sampling Algorithm
给定一个数据流,在我们不知道长度的情况下,需要取k个随机的数据。Reservoir Sampling可以帮助我们在O(n)的时间解决这一题。
讲解:
Reservoir Sampling
例题:
Linked List Random Node 解答
Random Pick Index 解答
每次和末尾交换保证连续的区间
在一个区间内不停地取随机数并且删除可以用这种方法。
例题:
Insert Delete GetRandom O(1) 解答
Insert Delete GetRandom O(1)-Duplicates allowed 解答
Random Flip Index 解答
Random Pick with Blacklist 解答
带权值的随机数
基本思路是presum + binary search
例题:
Random Pick with Weight 解答
Random Point in Non-overlapping Rectangles 解答
Inverse Transform Sampling
概率分布函数(PDF)->累积分布函数(CDF)->Inverse CDF
例题:
Generate Random Point in a Circle 解答
用小的randX()实现更大的randY()
本质上是进制问题,用randX()生成比Y大的randZ()即可
例题:
Implement Rand10() Using Rand7() 解答
Location:
Newark, CA 94560, USA
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment