数据结构与算法-数学系列

这部分来自于<LeetCode提高班第三期——Week3数学专题>, 有的题不需要数学方法, 用动态规划或者利用数据结构做更容易想象.

268. 丢失的数字

直接HashSet用$O(n)$时间搞定. 比较tricky的方法是用高斯公式求和在减去实际的数组内数字的和, 得到结果.

class Solution {
    public int missingNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        for (int i = 0; i <= nums.length; i++) {
            if (!set.contains(i)) return i;
        }
        return -1;
    }
}

453. 最小操作次数使数组元素相等

动态规划可以模拟每一步, 得到结果. 也可以反过来想, n-1个数字增加相当于1个数字减少, 那么减少的大小其实就是答案. 而减少的大小等于每个数字减去最小数字再求和.

class Solution {
    public int minMoves(int[] nums) {
        int[] dp = Arrays.copyOf(nums, nums.length);
        int res = 0;
        Arrays.sort(dp);
        for (int i = 1; i < dp.length; i++) {
            int diff = (dp[i] + res) - dp[i - 1];
            dp[i] += res;
            res += diff;
        }
        return res;
    }
}

class Solution {
    public int minMoves(int[] nums) {
        int[] dp = Arrays.copyOf(nums, nums.length);
        int res = 0;
        Arrays.sort(dp);
        for (int i = 0; i < dp.length; i++) {
            res += dp[i] - dp[0];
        }
        return res;
    }
}

462. 最少移动次数使数组元素相等II

直接排序计算中位数即可, 排序复杂度$O(nlogn)$. 也可以用快速选择的思想, 时间复杂度为$O(n)$, 最坏为$O(n^{2})$.

class Solution {
    public int minMoves2(int[] nums) {
        Arrays.sort(nums);
        int res = 0;
        for (int num : nums) {
            res += Math.abs(num - nums[nums.length / 2]);
        }
        return res;
    }
}

458. 可怜的小猪

想象n为2, 那么实际上这就是一个进制问题. 若有16个桶, 刚好对应4位2进制, 把0011给0号, 1号猪, 1101给0号, 2号, 3号猪等等. 如果最后123号猪死了, 那么说明1110有毒. n大于2的时候同理. n可以看作是尝试的机会数.

class Solution {
    public int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
        int n = (int) Math.ceil(minutesToTest / minutesToDie) + 1; //n进制
        int res = 0;
        while (Math.pow(n, res) < buckets) res++;
        return res;
    }
}

319. 灯泡开关

将灯泡编号, 完全平方数的灯泡被操作的次数是偶数次, 会亮着. 所以答案就是小于等于n的完全平方数量.

class Solution {
    public int bulbSwitch(int n) {
        return (int)Math.sqrt(n);
    }
}

343. 整数拆分

动态规划, 每次比较当前值, j和i-j相乘, j和之前数组的最大值相乘. 每一轮计算的实际上是当前i的最大值. 数学法不好理解.

class Solution {
    public int integerBreak(int n) {
        int[] dp = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                dp[i] = Math.max(dp[i], Math.max(dp[i - j] * j, (i - j) * j));
            }
        }
        return dp[n];
    }
}

470. 用 Rand7() 实现 Rand10()

rand7当成一个位, 所以相当于要生成一个7进制数字, 去覆盖1到10的范围. 通过拒绝策略, 拒绝掉不要的数字. 优化的思想是把拒绝的数字再次映射到1到10的范围内. 比如下面的算法抛弃了0, 41, … 48的数字. 那么可以通过x = (x % 40) * 7 + rand7();再做一次rand操作, 范围是1~63, 那么舍弃的数字只有61, 62, 63了. 这样我们依然保证了等概率, 相当于一个结合律. 算平均调用rand7的次数可以把两位的7进制数字当成一组, 剩下的就是以不被拒绝的数字构成的等比数列.

class Solution extends SolBase {
    public int rand10() {
        while (true) {
            int x = (rand7() - 1) * 7 + (rand7() - 1);
            if (x >= 1 && x <= 40) return x % 10 + 1;
        } 
    }
}