[数据结构与算法]leetcode 497 528. Random Point in Non-overlapping Rectangles | 497. 非重叠矩形中的随机点（Java）

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() {
        // 根据权重选择一个rectangle
        long sum = weight[N - 1] + weightSum[N - 1];
        long rand = randLong(0, sum);
        // 反向查找randLong属于的index
        int 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() {
        // 根据权重选择一个rectangle
        int sum = w[N - 1] + wSum[N - 1];
        int rand = rand(0, sum);
        // 反向查找randLong属于的index
        int 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();
 */