当前位置:网站首页>LeetCode 497(C#)
LeetCode 497(C#)
2022-07-07 15:38:00 【有趣就行】
题目
给定一个由非重叠的轴对齐矩形的数组 rects ,其中 rects[i] = [ai, bi, xi, yi] 表示 (ai, bi) 是第 i 个矩形的左下角点,(xi, yi) 是第 i 个矩形的右上角点。设计一个算法来随机挑选一个被某一矩形覆盖的整数点。矩形周长上的点也算做是被矩形覆盖。所有满足要求的点必须等概率被返回。
在给定的矩形覆盖的空间内的任何整数点都有可能被返回。
请注意 ,整数点是具有整数坐标的点。
实现 Solution 类:
Solution(int[][] rects) 用给定的矩形数组 rects 初始化对象。
int[] pick() 返回一个随机的整数点 [u, v] 在给定的矩形所覆盖的空间内。
示例 1:
输入:
[“Solution”, “pick”, “pick”, “pick”, “pick”, “pick”]
[[[[-2, -2, 1, 1], [2, 2, 4, 6]]], [], [], [], [], []]
输出:
[null, [1, -2], [1, -1], [-1, -2], [-2, -2], [0, 0]]
解释:
Solution solution = new Solution([[-2, -2, 1, 1], [2, 2, 4, 6]]);
solution.pick(); // 返回 [1, -2]
solution.pick(); // 返回 [1, -1]
solution.pick(); // 返回 [-1, -2]
solution.pick(); // 返回 [-2, -2]
solution.pick(); // 返回 [0, 0]
代码
二分 + 前缀和
public class Solution
{
Random _random;
int[] _sum;
int[][] _rects;
public Solution(int[][] rects)
{
_rects = rects;
_sum = new int[rects.Length + 1];
for (int i = 1; i <= rects.Length; i++)
_sum[i] = _sum[i - 1] + (rects[i - 1][2] - rects[i - 1][0] + 1) * (rects[i - 1][3] - rects[i - 1][1] + 1);
_random = new Random();
}
public int[] Pick()
{
int k = _random.Next(_sum[_sum.Length - 1]);
int index = BinarySearch(k + 1) - 1;
k -= _sum[index];
int[] cnt = _rects[index];
int col = cnt[3] - cnt[1] + 1;
return new int[]{
cnt[0] + k / col, cnt[1] + k % col};
}
private int BinarySearch(int k)
{
var (low, high) = (0, _sum.Length - 1);
while (low < high)
{
int mid = low + (high - low) / 2;
if (_sum[mid] >= k) high = mid;
else low = mid + 1;
}
return high;
}
}
边栏推荐
猜你喜欢
Linux 安装mysql8.X超详细图文教程
麒麟信安携异构融合云金融信创解决方案亮相第十五届湖南地区金融科技交流会
《产品经理必读:五种经典的创新思维模型》的读后感
QML beginner
[Seaborn] combination chart: facetgrid, jointgrid, pairgrid
Lex & yacc of Pisa proxy SQL parsing
科普达人丨一文弄懂什么是云计算?
[video / audio data processing] Shanghai daoning brings you elecard download, trial and tutorial
QT picture background color pixel processing method
skimage学习(1)
随机推荐
麒麟信安携异构融合云金融信创解决方案亮相第十五届湖南地区金融科技交流会
How to mount the original data disk without damage after the reinstallation of proxmox ve?
Flask搭建api服务
From Devops to mlops: how do it tools evolve to AI tools?
The server is completely broken and cannot be repaired. How to use backup to restore it into a virtual machine without damage?
QT video transmission
LeetCode刷题day49
LeetCode 312. Poke balloon daily
LeetCode 1031. 两个非重叠子数组的最大和 每日一题
Flash build API service
Skimage learning (3) -- gamma and log contrast adjustment, histogram equalization, coloring gray images
智慧物流平台:让海外仓更聪明
Flask搭建api服务-生成API文档
Solidity 开发环境搭建
Seaborn数据可视化
LeetCode 1049. 最后一块石头的重量 II 每日一题
LeetCode 300. 最长递增子序列 每日一题
管理VDI的几个最佳实践
Process from creation to encapsulation of custom controls in QT to toolbar (I): creation of custom controls
Rpcms method of obtaining articles under the specified classification