LeetCode 528. Random Pick with Weight / 497. Random Point in Non-overlapping Rectangles _leetcode

【LeetCode 528. Random Pick with Weight / 497. Random Point in Non-overlapping Rectangles】寸阳分阴须爱惜，休负春色与时光。这篇文章主要讲述LeetCode 528. Random Pick with Weight / 497. Random Point in Non-overlapping Rectangles相关的知识，希望能为你提供帮助。
528. Random Pick with Weight
根据weight随机选取一个数，用 Prefix Sum+Binary Search 来解决。
https://www.geeksforgeeks.org/random-number-generator-in-arbitrary-probability-distribution-fashion/

class Solution { public: vector< int> prefixSum; int total=0; Solution(vector< int> & w) { for (auto x:w){ total += x; prefixSum.push_back(total); } }int pickIndex() { // random generate from [1,total] int r=rand()%total+1; // find the first > = element auto it=lower_bound(prefixSum.begin(),prefixSum.end(),r); return it-prefixSum.begin(); } }; /** * Your Solution object will be instantiated and called as such: * Solution* obj = new Solution(w); * int param_1 = obj-> pickIndex(); */

497. Random Point in Non-overlapping Rectangles
矩形的内包括点的数量实际就是weight，根据weight先随机选择一个矩形，然后随机生成该矩形内的x和y即可。

class Solution { public: vector< vector< int> > rects; vector< int> prefixSum; int total=0; Solution(vector< vector< int> > & rects) { this-> rects = rects; for (auto rect:rects){ int cur=(rect[2]-rect[0]+1)*(rect[3]-rect[1]+1); total += cur; prefixSum.push_back(total); } }vector< int> pick() { // select from [1,total] int r=rand()%total+1; auto it=lower_bound(prefixSum.begin(),prefixSum.end(),r); auto rect=rects[it-prefixSum.begin()]; // randomly pick x from [rect[0],rect[2]], y from [rect[1],rect[3]] int x = rect[0] + rand()%(rect[2]-rect[0]+1); int y = rect[1] + rand()%(rect[3]-rect[1]+1); return {x,y}; } }; /** * Your Solution object will be instantiated and called as such: * Solution* obj = new Solution(rects); * vector< int> param_1 = obj-> pick(); */

Followup: 如果有overlap的矩形怎么办？
思路：把重复的长方形分成不重复的小块，然后用prefix sum进行二分查找
把一堆重叠长方形变成不重叠的长方形的具体思路可以看这个帖子：
递归解法 https://leetcode.com/problems/rectangle-area-ii/discuss/138028/Clean-Recursive-Solution-Java
迭代解法 https://leetcode.com/problems/rectangle-area-ii/discuss/137995/O(N2)-Maintain-a-List-of-Rectangle-Split-the-Rectangle-in-List-without-overlap