9. Math

获得随机数 Shuffle an array

• 这题的关键在于要设计一个shuffle算法使得每个位置的数被shuffle的概率相同

• 于是就有了int i = random.nextInt(j + 1)的这个trick

• int index = random.nextInt(i + 1);

• nextInt返回的是[0,i+1)的整数

• 所以不可以是random.nextInt(0, i)，设想一共就两个数(6,4)

• 如果是nextInt(0,i) i start from 1, 这样的话4就只可能在[0,0]区间内变换，就只有这一种shuffle可能了

• 这里有人给了个简单的证明

public class Solution {
    private int[] nums = null;
    private Random random = null;
    public Solution(int[] nums) {
        this.nums = nums;
        random = new Random();
    }

    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
        return Arrays.copyOf(nums, nums.length);
    }

    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
        int[] arr = Arrays.copyOf(nums, nums.length);
        for(int i = 1; i < arr.length; i++){
            int index = random.nextInt(i + 1);
            swap(arr, i, index);
        }
        return arr;
    }
    private void swap(int[] nums, int a, int b){
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
}

Count Primes

• 给定一个数n, 求比n小的素数的个数

• 建立一个boolean[] notPrime = new boolean[n]

• 然后每找到一个prime number, cnt++, 并把它的所有的倍数都设成notPrime = true

public int countPrimes(int n) {
        if (n < 2) return 0;
        boolean[] notPrime = new boolean[n];
        notPrime[0] = true;
        notPrime[1] = true;
        int cnt = 0;
        for (int i = 2; i < n; i++) {
            if(notPrime[i] == false) {
                cnt++;
                for (int j = 2; i * j < n; j++) {
                    notPrime[i * j] = true;
                }
            }
        }
        return cnt;
    }

Reverse Integer

• 本身不难

• 注意integer overflow的edge case

public int reverse(int x) {
        if (x == 0) return 0;
        int sign = x > 0 ? 1 : -1;
        long num = Math.abs(x), res = 0;
        while (num > 0) {
            res = res * 10 + num % 10;
            num /= 10;
        }
        res = res * sign;
        if (res > Integer.MAX_VALUE || res < Integer.MIN_VALUE) {
            return 0;
        }
        return (int) res;
    }