题目1 前缀数组

假设有一个数组arr，用户总是频繁的查询arr中某一段的累加和
你如何组织数据，能让这种查询变得便利和快捷？
算法1：
思路;前缀和

  1.     /**
  2.      * 求数组 给定区间的和
  3.      *
  4.      * @param arr        数组
  5.      * @param leftIndex  区间左边下标
  6.      * @param rightIndex 区间右边下标
  7.      * @return 给定区间的和
  8.      */
  9.     public static int getRangeSum1(int[] arr, int leftIndex, int rightIndex) {
  10.         int sum = 0;
  11.         int[] preSum = new int[arr.length];
  12.         for (int i = 0; i < arr.length; i++) {
  13.             preSum[i] = sum + arr[i];
  14.             sum = preSum[i];
  15.         }
  16.         return leftIndex == 0 ? preSum[rightIndex] : preSum[rightIndex] - preSum[leftIndex - 1];
  17.     }

算法2：
思路：遍历

  1.      /**
  2.      * 求数组 给定区间的和
  3.      *
  4.      * @param arr        数组
  5.      * @param leftIndex  区间左边下标
  6.      * @param rightIndex 区间右边下标
  7.      * @return 给定区间的和
  8.      */
  9.     public static int getRangeSum2(int[] arr, int leftIndex, int rightIndex) {
  10.         int sum = 0;
  11.         for (int i = leftIndex; i <= rightIndex; i++) {
  12.             sum += arr[i];
  13.         }
  14.         return sum;
  15.     }

算法3：
思路：将每个区间的和构建一个二维表

    /**
     * 求数组 给定区间的和
     *
     * @param arr        数组
     * @param leftIndex  区间左边下标
     * @param rightIndex 区间右边下标
     * @return 给定区间的和
     */
    public static int getRangeSum3(int[] arr, int leftIndex, int rightIndex) {
        int[][] table = new int[arr.length][];
        for (int i = 0; i < arr.length; i++) {
            int sum = 0;
            table[i] = new int[arr.length - i];
            for (int j = 0, k = i; j < arr.length - i && k < arr.length; j++, k++) {
                table[i][j] = sum + arr[k];
                sum = table[i][j];
            }
        }
        return table[leftIndex][rightIndex - leftIndex];
    }

当查询次数非常大非常大非常大时，可采用第三种将所有结果构建一个表，查询时直接返回查询结果即可。

题目2 随机数1

如果利用Math.random()函数，把得到[0,x)范围上的数的概率从x调整成x^2
思路：
Math.random()函数，等概率返回区间 [0,1）上任意一个double类型的小数。那么返回在[0，x)区间（x<=1)里的数的概率为x

    /**
     * 以x^2概率等概率返回[0,x)上的数
     * @return double
     */
    public static double xToPower2() {
        return Math.max(Math.random(), Math.random());
    }

思考：这里为什么要用Math.max()而不是用Math.min()呢？
回答：①Math.max()为返回两个数的较大值，只有2个数都落在[0,x)区间，才会返回[0,x)区间上的数，因此返回的概率从x变为x^2。
②而Math.min()返回两个数的较小值，因此，只要有一个数在[0,x)区间上，返回的值一定在[0,x）区间，因此返回的概率为1-（1-x)^2。

题目3 随机数2

从1~5随机到1~7随机；从a~b随机到c~d随机；01不等概率随机到01等概率随机。
思路：
根据已知的随机数生成器，生成一个等概率0，1发生器。然后运用2进制的规律。

    /**
     * 一个随机数发生器random5()，等概率生成1-5之间的数，仅适用random5(),
     *生成一个等概率生成1-7之间数的随机数生成器random7()
     */
    public static int random7() {
        int num;
        do {
            num = (randomToRandom() << 2) + (randomToRandom() << 1) + randomToRandom();
        } while (num == 0);
        return num;
    }

    /**
     * 根据random5()随机生成器生成等概率的0,1生成器
     *
     * @return 等概率返回0和1
     */
    private static int randomToRandom() {
        int i = 0;
        do {
            i = random5();
        } while (i == 3);
        return i < 3 ? 0 : 1;
    }


    /**
     * 随机数发生器random5()，等概率生成1-5之间的数
     *
     * @return 等概率返回1-5之间的数
     */
    private static int random5() {
        return (int) (Math.random() * 5) + 1;
    }

扩展为一般性


    // 这个结构是唯一的随机机制
    // 你只能初始化并使用，不可修改
    public static class RandomBox {
        private final int min;
        private final int max;

        // 初始化时请一定不要让mi==ma
        public RandomBox(int mi, int ma) {
            min = mi;
            max = ma;
        }

        // 13 ~ 17
        // 13 + [0,4]
        public int random() {
            return min + (int) (Math.random() * (max - min + 1));
        }

        public int min() {
            return min;
        }

        public int max() {
            return max;
        }
    }

    // 利用条件RandomBox，如何等概率返回0和1
    public static int rand01(RandomBox randomBox) {
        int min = randomBox.min();
        int max = randomBox.max();
        // min ~ max
        int size = max - min + 1;
        // size是不是奇数，odd 奇数
        boolean odd = (size & 1) != 0;
        int mid = size / 2;
        int ans = 0;
        do {
            ans = randomBox.random() - min;
        } while (odd && ans == mid);
        return ans < mid ? 0 : 1;
    }

    // 给你一个RandomBox，这是唯一能借助的随机机制
    // 等概率返回from~to范围上任何一个数
    // 要求from<=to
    public static int random(RandomBox randomBox, int from, int to) {
        if (from == to) {
            return from;
        }
        // 3 ~ 9
        // 0 ~ 6
        // 0 ~ range
        int range = to - from;
        int num = 1;
        // 求0～range需要几个2进制位
        while ((1 << num) - 1 < range) {
            num++;
        }

        // 我们一共需要num位
        // 最终的累加和，首先+0位上是1还是0，1位上是1还是0，2位上是1还是0...
        int ans = 0;
        do {
            ans = 0;
            for (int i = 0; i < num; i++) {
                ans |= (rand01(randomBox) << i);
            }
        } while (ans > range);
        return ans + from;
    }

随机数的应用——对数器

可以用随机数生成任意长度数组，数组每一位的元素也是随机数的测试样本。
比较待测试算法与已知算法的结果差异，来进行待测试算法的测试。
image.png