Other

调整[0,x)区间上的数出现的概率

随机返回[0,1)上的数，使得在[0,x)区间上的数出现的概率是x^k (0<=x<=1)

public double randXPowerK(int k) {
    if (k < 1) {
        return 0;
    }
    double res = -1;
    // k次调用Math.random返回值都必须落在[0,x)上，才会出现目标值，所以概率=x^k
    for (int i = 0; i < k; i++) {
        res = Math.max(res, Math.random());
    }
    return res;
}

从N个数中等概率打印M个数

要求：

1. 不重复打印
2. time = M，space = 1
3. 可以改变数组

很多有关概率随机的面试题都是用这种和最后一个位置交换的解法

public void printRandM(int[] arr, int m) {
    if (arr == null || arr.length == 0 || m < 0) {
        return;
    }

    // 细节！！！
    m = Math.min(arr.length, m);
    int n = arr.length;

    for (int i = 0; i < m; i++) {
        int index = (int) (Math.random() * n);
        System.out.print(arr[index] + " ");
        swap(arr, index, n-- - 1);
    }
}

public void swap(int[] arr, int index1, int index2) {
    int tmp = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = tmp;
}

判断一个数是否是回文数

注：32位整数中的最小值是转不成相应的绝对值的，也不是回文数，因特殊处理。
way1：转字符串左右往中间遍历进行比较，额外需要一个数组，t=N,s=1

public boolean isPalindrome(int n) {
    if (n == Integer.MIN_VALUE) {
        return false;
    }
    if (n < 0) {
        n = -n;
    }

    String[] arr = (n + "").split("");
    int len = arr.length;
    for (int i = 0; i < len / 2; i++) {
        if (!arr[i].equals(arr[len - 1 - i])) {
            return false;
        }
    }
    return true;
}

way2：生成一个位数相同的变量，num用/和%取首末位比较，然后去掉，位数同步，直到num=0

public boolean isPalindrome(int n) {
    if (n == Integer.MIN_VALUE) {
        return false;
    }
    
    n = Math.abs(n);
    int help = 1;
    while (n / help >= 10) {
        help *= 10;
    }
    
    while (n != 0) {
        if (n / help != n % 10) {
            return false;
        }
        help /= 100;
        n = (n % help) / 10;
    }
    return true;
}