​LeetCode刷题实战497:非重叠矩形中的随机点

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

今天和大家聊的问题叫做 非重叠矩形中的随机点,我们先来看题面:
https://leetcode-cn.com/problems/random-point-in-non-overlapping-rectangles/

​LeetCode刷题实战497:非重叠矩形中的随机点

给定一个非重叠轴对齐矩形的列表 rects,写一个函数 pick 随机均匀地选取矩形覆盖的空间中的整数点。
提示:
  • 整数点是具有整数坐标的点。

  • 矩形周边上的点包含在矩形覆盖的空间中。

  • 第 i 个矩形 rects [i] = [x1,y1,x2,y2],其中 [x1,y1] 是左下角的整数坐标,[x2,y2] 是右上角的整数坐标。

  • 每个矩形的长度和宽度不超过 2000。

  • 1 <= rects.length <= 100

  • pick 以整数坐标数组 [p_x, p_y] 的形式返回一个点。

  • pick 最多被调用10000次 。


示例                         

示例 1
输入:
["Solution","pick","pick","pick"]
[[[[1,1,5,5]]],[],[],[]]
输出:
[null,[4,1],[4,1],[3,3]]

示例 2
输入:
["Solution","pick","pick","pick","pick","pick"]
[[[[-2,-2,-1,-1],[1,0,3,0]]],[],[],[],[],[]]
输出:
[null,[-1,-2],[2,0],[-2,-1],[3,0],[-2,-2]]


解题

https://blog.csdn.net/weixin_44171872/article/details/111083657
主要思路:
(1)两次随机过程,先使用随机找到点所在的矩形,再使用随机确定该矩形内的一个位置;
(2)随机确定矩形的过程,可以通过面积来进行映射,计算出矩形的总的面积,然后将随机数对该总面积取余,将余数映射到某个矩形;
(3)找到该矩形后,可以对使用随机数对该矩形的高和宽分别取余映射,获得两个值,将这两个值加上左下角,即为坐标位置;


class Solution {
public:
    vector<vector<int>> _rects;//统计各个矩形
    vector<int> _area;//获得各个矩形对应的面积
    long _sum_area;//总的矩形面积
    Solution(vector<vector<int>>& rects):_rects(rects) {
        _area.reserve(_rects.size());
        _sum_area=0;
        for(vector<int>& rect:_rects){
            _area.push_back((rect[2]-rect[0]+1)*(rect[3]-rect[1]+1));//获得各个矩形的面积
            _sum_area+=_area.back();
        }
    }
    
    vector<int> pick() {
        long sum_area=rand()%_sum_area+1;//将随机数映射到矩形中
        int index=0;
        //找出是第几个矩形
        while(_area[index]<sum_area){
            sum_area-=_area[index];
            ++index;
        }
        vector<int>& cur_rect=_rects[index];
        //对该矩形的高和宽进行区域,映射到矩形内的点
        int x=rand()%(cur_rect[2]-cur_rect[0]+1);
        int y=rand()%(cur_rect[3]-cur_rect[1]+1);
        return {cur_rect[0]+x,cur_rect[1]+y};//加上矩形的左下角,即为坐标
    }
};


好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。

上期推文:


LeetCode1-480题汇总,希望对你有点帮助!

LeetCode刷题实战481:神奇字符串

LeetCode刷题实战482:密钥格式化

LeetCode刷题实战483:最小好进制

LeetCode刷题实战484:寻找排列

LeetCode刷题实战485:最大连续 1 的个数

LeetCode刷题实战486:预测赢家

LeetCode刷题实战487:最大连续1的个数 II

LeetCode刷题实战488:祖玛游戏

LeetCode刷题实战489:扫地机器人

LeetCode刷题实战490:迷宫

LeetCode刷题实战491:递增子序列

LeetCode刷题实战492:构造矩形

LeetCode刷题实战493:翻转对

LeetCode刷题实战494:目标和

LeetCode刷题实战495:提莫攻击

LeetCode刷题实战496:下一个更大元素 I


​LeetCode刷题实战497:非重叠矩形中的随机点

本篇文章来源于微信公众号:程序IT圈

原创文章,作者:栈长,如若转载,请注明出处:https://www.cxyquan.com/18227.html

发表评论

登录后才能评论

联系我们

400-800-8888

在线咨询:点击这里给我发消息

邮件:admin@example.com

工作时间:周一至周五,9:30-18:30,节假日休息