当前位置:网站首页>LeetCode 497(C#)
LeetCode 497(C#)
2022-07-07 19:04:00 【Just be interesting】
subject
Given an array of rectangles aligned by non overlapping axes rects , among rects[i] = [ai, bi, xi, yi] Express (ai, bi) It's No i Bottom left corner of rectangle ,(xi, yi) It's No i The upper right corner of a rectangle . Design an algorithm to randomly select an integer point covered by a rectangle . Points on the perimeter of a rectangle are also considered to be covered by the rectangle . All points that meet the requirements must be returned with equal probability .
Any integer point in the space covered by a given rectangle can be returned .
Please note that , An integer point is a point with integer coordinates .
Realization Solution class :
Solution(int[][] rects) With the given rectangular array rects Initialize object .
int[] pick() Returns a random integer point [u, v] In the space covered by a given rectangle .
Example 1:
Input :
[“Solution”, “pick”, “pick”, “pick”, “pick”, “pick”]
[[[[-2, -2, 1, 1], [2, 2, 4, 6]]], [], [], [], [], []]
Output :
[null, [1, -2], [1, -1], [-1, -2], [-2, -2], [0, 0]]
explain :
Solution solution = new Solution([[-2, -2, 1, 1], [2, 2, 4, 6]]);
solution.pick(); // return [1, -2]
solution.pick(); // return [1, -1]
solution.pick(); // return [-1, -2]
solution.pick(); // return [-2, -2]
solution.pick(); // return [0, 0]
Code
Two points + The prefix and
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;
}
}
边栏推荐
- Redis publishing and subscription
- Tsinghua, Cambridge and UIC jointly launched the first Chinese fact verification data set: evidence-based, covering many fields such as medical society
- Redis cluster and expansion
- Skills of embedded C language program debugging and macro use
- unity2d的Rigidbody2D的MovePosition函数移动时人物或屏幕抖动问题解决
- 行业案例|数字化经营底座助力寿险行业转型
- Redis
- Recommend free online SMS receiving platform in 2022 (domestic and foreign)
- RISCV64
- RISCV64
猜你喜欢
C语言中匿名的最高境界
数据验证框架 Apache BVal 再使用
Tsinghua, Cambridge and UIC jointly launched the first Chinese fact verification data set: evidence-based, covering many fields such as medical society
将模型的记忆保存下来!Meta&UC Berkeley提出MeMViT,建模时间支持比现有模型长30倍,计算量仅增加4.5%...
Charles+drony的APP抓包
CVPR 2022丨学习用于小样本语义分割的非目标知识
[information security laws and regulations] review
Save the memory of the model! Meta & UC Berkeley proposed memvit. The modeling time support is 30 times longer than the existing model, and the calculation amount is only increased by 4.5%
Interview vipshop internship testing post, Tiktok internship testing post [true submission]
完整的电商系统
随机推荐
[Blue Bridge Cup training 100 questions] sort scratch from small to large. Blue Bridge Cup scratch competition special prediction programming question centralized training simulation exercise question
Redis集群与扩展
PIP related commands
testing and SQA_动态白盒測试[通俗易懂]
Reinforcement learning - learning notes 8 | Q-learning
Idea completely uninstalls installation and configuration notes
Basic concepts and properties of binary tree
POJ 2392 Space Elevator
数据验证框架 Apache BVal 再使用
String type, constant type and container type of go language
Skills of embedded C language program debugging and macro use
Mathematical analysis_ Notes_ Chapter 11: Fourier series
低代码助力企业数字化转型会让程序员失业?
企业展厅设计中常用的三种多媒体技术形式
PTA 1101 B是A的多少倍
Interview vipshop internship testing post, Tiktok internship testing post [true submission]
[论文分享] Where’s Crypto?
RIP和OSPF的区别和配置命令
高考填志愿规则
The moveposition function of rigidbody2d of unity2d solves the problem of people or screen jitter when moving