資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++中非重疊矩形內的隨機點
假設我們有一組非重疊的軸對齊矩形rects，我們需要編寫一個函式pick，該函式隨機且均勻地選擇矩形覆蓋空間中的一個整數點。我們需要記住以下幾點：
- 整數點是指具有整數座標的點。
- 矩形周界上的點包含在矩形覆蓋的空間內。
- 第i個矩形 = rects[i] 表示[x1,y1,x2,y2]，其中[x1, y1]是左下角的整數座標，[x2, y2]是右上角的整數座標。
- 每個矩形的長度和寬度不超過2000。
- 1 <= rects.length <= 100
- pick返回一個整數座標對[p_x, p_y]作為點。
如果輸入為[1,1,5,5]，並且我們呼叫pick()三次，則輸出將為[4,1]，[4,1]，[3,3]。
為了解決這個問題，我們將遵循以下步驟：
- 建立兩個陣列area和rect。
- 在初始化中執行以下操作：
- rect := rects，sum := 0
- 對於範圍0到rects大小-1的i
- (x1, y1) := (rects[i, 0], rects[i, 1])
- (x2, y2) := (rects[i, 2], rects[i, 3])
- temp := |x2 – x1 + 1| * |y2 – y1 + 1|
- sum := sum + temp，並將sum插入area。
- 在pick方法中，執行以下操作：
- randArea := 隨機數 mod sum + 1
- 對於範圍0到area大小-1的i
- 如果randArea <= area[i]，則退出迴圈。
- dist_x := 隨機數 mod |rect[i,0] – rect[i,2] + 1|
- dist_y := 隨機數 mod |rect[i,1] – rect[i,3] + 1|
- 返回一個座標對(dist_x + rect[i, 0], dist_y + rect[i, 1])
讓我們看看下面的實現來更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector <int> area;
vector < vector <int> > rect;
int sum;
Solution(vector<vector<int> >& rects) {
rect = rects;
sum = 0;
for(int i =0 ; i < rects.size(); i++){
int x1 = rects[i][0];
int y1 = rects[i][1];
int x2 = rects[i][2];
int y2 = rects[i][3];
int temp = (abs(x2 - x1) + 1) * (abs(y2 - y1) + 1);
sum += temp;
area.push_back(sum);
}
}
vector<int> pick() {
int randArea = rand() % sum + 1;
int i;
for(i = 0; i < area.size(); i++){
if(randArea <= area[i]) break;
}
int dist_x = rand() % (abs(rect[i][0] - rect[i][2] ) + 1);
int dist_y = rand() % (abs(rect[i][1] - rect[i][3] ) + 1);
return {dist_x + rect[i][0], dist_y + rect[i][1]};
}
};
main(){
vector<vector<int> > v = {{1, 1, 5, 5}};
Solution ob(v);
print_vector(ob.pick());
print_vector(ob.pick());
print_vector(ob.pick());
}輸入
["Solution", "pick", "pick", "pick"] [[[[1, 1, 5, 5]]], [], [], []]
輸出
[2, 3, ] [4, 1, ] [3, 5, ]
更新於：2020年5月2日
275 次瀏覽
廣告