497. Random Point in Non-overlapping Rectangles

https://leetcode.com/problems/random-point-in-non-overlapping-rectangles/

題解

大坑：面積包含邊界，計算要注意+1，這種隨機數的問題，沒有固定的輸出，調bug不好調啊…目前的方法是，手動指定random的值，遍歷所有可能的random，看是否符合預期。

思路：
1、先按照面積計算每個rectangle的權重
2、根據權重選擇rectangle的下標（參考 528. Random Pick with Weight）
3、選好rectangle后，根據范圍隨機生成橫坐標x、縱坐標y

class Solution {Random r;int N;int[][] rects;long[] weight; // 權重long[] weightSum; // 權重前綴和public Solution(int[][] rects) {this.rects = rects;r = new Random();N = rects.length;weight = new long[N];weightSum = new long[N];for (int i = 0; i < N; i++) {weight[i] = ((long) rects[i][2] + 1 - rects[i][0]) * ((long) rects[i][3] + 1 - rects[i][1]); // +1 因為包含邊界！坑！！}weightSum[0] = 0;if (N > 1) weightSum[1] = weight[0];for (int i = 2; i < N; i++) {weightSum[i] = weightSum[i - 1] + weight[i - 1];}}public int[] pick() {// 根據權重選擇一個rectanglelong sum = weight[N - 1] + weightSum[N - 1];long rand = randLong(0, sum);// 反向查找randLong屬于的indexint L = 0;int R = N - 1;int index = -1;if (weightSum[N - 1] <= rand) {index = N - 1;} else {while (L < R) {int M = L + (R - L) / 2;if (weightSum[M] == rand) {index = M;break;} else if (weightSum[M] < rand) {if (L == M) {index = M;break;}L = M;} else {R = M - 1;if (weightSum[R] <= rand) {index = R;break;}}}if (index == -1) index = L;}int[] rec = rects[index];long x = randLong(rec[0], rec[2] + 1);long y = randLong(rec[1], rec[3] + 1);return new int[]{(int) x, (int) y};}public long randLong(long a, long b) { // 左閉右開return a + (long) (Math.random() * (b - a));}}/*** Your Solution object will be instantiated and called as such:* Solution obj = new Solution(rects);* int[] param_1 = obj.pick();*/

528. Random Pick with Weight

https://leetcode.com/problems/random-pick-with-weight/

本題是上一題的一個子問題，直接復制粘貼了。

class Solution {int N;int[] w; // 權重int[] wSum; // 權重前綴和public Solution(int[] w) {N = w.length;this.w = w;wSum = new int[N];wSum[0] = 0;if (N > 1) wSum[1] = this.w[0];for (int i = 2; i < N; i++) {wSum[i] = wSum[i - 1] + this.w[i - 1];}}public int pickIndex() {// 根據權重選擇一個rectangleint sum = w[N - 1] + wSum[N - 1];int rand = rand(0, sum);// 反向查找randLong屬于的indexint L = 0;int R = N - 1;int index = -1;if (wSum[N - 1] <= rand) {index = N - 1;} else {while (L < R) {int M = L + (R - L) / 2;if (wSum[M] == rand) {index = M;break;} else if (wSum[M] < rand) {if (L == M) {index = M;break;}L = M;} else {R = M - 1;if (wSum[R] <= rand) {index = R;break;}}}if (index == -1) index = L;}return index;}public int rand(int a, int b) { // 左閉右開return (int) (a + (Math.random() * (b - a)));} }/*** Your Solution object will be instantiated and called as such:* Solution obj = new Solution(w);* int param_1 = obj.pickIndex();*/

總結

以上是生活随笔為你收集整理的leetcode 497, 528. Random Point in Non-overlapping Rectangles | 497. 非重叠矩形中的随机点（Java）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。