LeetCode 50, 75, 295

50. Pow(x, n)

题目链接

50. Pow(x, n)

标签

递归 数学

思路

本题可以使用 快速幂 的思想：将求 $x^n$ 转化为 先求 $x^{\frac{n}{2}}$，然后根据 $n$ (此处的 $n$ 是自然数) 是奇数还是偶数进行不同操作：

• 如果 $n$ 是奇数，由于 $n/2$ 会 向下取整，所以 $x^{\frac{n}{2}}\ast x^{\frac{n}{2}}\ne x^n$，而 $x\ast x^{\frac{n}{2}}\ast x^{\frac{n}{2}}=x^n$。
• 如果 $n$ 是偶数，则 $x^{\frac{n}{2}}\ast x^{\frac{n}{2}}=x^n$。

直到所求的幂为 $0$ 或 $1$：如果幂为 $0$，直接返回 $1$ 即可；如果幂为 $1$，直接返回 $x$ 自身。

如果 $n$ 是负数，则先获取与其相反的正数 $p$，使用快速幂求 $x^p$，然后返回 $\frac{1}{x^p}$ 即可。

代码

class Solution {
    public double myPow(double x, int n) {
        long p = n < 0 ? -n : n; // 将 负次幂 转化为 正次幂
        double pow = quickPowerPositive(x, p); // 计算 x 的 p 次幂 (p 是正数)
        return n < 0 ? 1 / pow : pow; // 如果 n 是负数，则返回 1 / 正次幂；否则返回 正次幂
    }

    // 快速计算一个 x 的 n 次幂，n 是正数
    private static double quickPowerPositive(double x, long n) {
        if (n == 0) { // 如果 n == 0
            return 1; // 则返回 1
        } else if (n == 1) { // 如果 n == 1
            return x; // 则返回 x 本身
        }

        long subN = n >>> 1; // n >>> 1 会向下取整
        double subPow = quickPowerPositive(x, subN); // 获取 x 的 n 次幂的“一半”
        if ((n & 1) == 1) { // 如果 n 是奇数
            return x * subPow * subPow; // 则返回 x * subPow * subPow
        } else { // 如果 n 是偶数
            return subPow * subPow; // 则返回 subPow * subPow
        }
    }
}

75. 颜色分类

题目链接

75. 颜色分类

标签

数组 双指针 排序

思路

本题可以使用 双指针 的思想，左指针 left 指向 目前 最后一个 0 的下一个值，右指针 right 指向 目前 第一个 2 的上一个值，当前指针 curr 在 [left, right] 的范围内进行扫描：

• 如果发现 2，则将其与 右指针 指向的元素进行交换，然后左移右指针。
• 如果发现 0，则将其与 左指针 指向的元素进行交换，然后右移左指针。

不过这道题并没有到此结束，还存在一个小问题，例如对于 nums = [0, 2, 2, 2, 0, 2, 1, 1]，它的遍历结果如下：

初始 left = 0, right = 7, curr = 0, nums = [0, 2, 2, 2, 0, 2, 1, 1]

将 nums[curr = 0] 与 nums[left = 0] 进行交换
得到 left = 1, right = 7, curr = 1, nums = [0, 2, 2, 2, 0, 2, 1, 1]

将 nums[curr = 1] 与 nums[right = 7] 进行交换
得到 left = 1, right = 6, curr = 2, nums = [0, 1, 2, 2, 0, 2, 1, 2]

将 nums[curr = 2] 与 nums[right = 6] 进行交换
得到 left = 1, right = 5, curr = 3, nums = [0, 1, 1, 2, 0, 2, 2, 2]

>>>将 nums[curr = 3] 与 nums[right = 5] 进行交换<<<
得到 left = 1, right = 5, curr = 4, nums = [0, 1, 1, 2, 0, 2, 2, 2]

将 nums[curr = 4] 与 nums[left = 1] 进行交换
得到 left = 2, right = 5, curr = 5, nums = [0, 0, 1, 2, 1, 2, 2, 2]

将 nums[curr = 5] 与 nums[right = 5] 进行交换
得到 nums = [0, 0, 1, 2, 1, 2, 2, 2]

明显这样的结果是有问题的，问题出在用 >>> <<< 标记的地方，此时 right 没有指向目前第一个 2 的上一个值，而是指向目前第一个 2，所以 在交换完 2 之后，要将 right 移动到目前第一个 2 的上一个值。

代码

class Solution {
    public void sortColors(int[] nums) {
        int n = nums.length;
        // 左指针 left 指向目前最后一个 0 的下一个值，右指针 right 指向目前第一个 2 的上一个值
        int left = 0, right = n - 1;

        // 让 左指针 指向目前最后一个 0 的下一个值
        while (left < n && nums[left] == 0) {
            left++;
        }

        // 让 右指针 指向目前第一个 2 的上一个值
        while (right >= 0 && nums[right] == 2) {
            right--;
        }

        for (int curr = left; curr <= right; curr++) { // curr 在 [left, right] 的范围内扫描
            if (nums[curr] == 2) { // 如果扫描到 2，则将 2 交换到数组右侧
                swap(nums, curr, right);
                // 将 右指针 向左移，直到目前第一个 2 的上一个值
                while (curr <= right && nums[right] == 2) {
                    right--;
                }
            }

            if (nums[curr] == 0) { // 如果扫描到 0，则将 0 交换到数组左侧
                swap(nums, curr, left);
                left++; // 将 左指针 向右移
            }
        }
    }
    // 交换 nums 中 i 和 j 指向的元素
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

295. 数据流的中位数

题目链接

295. 数据流的中位数

标签

设计 双指针 数据流 排序 堆（优先队列）

思路

前提条件——了解优先队列的实现

在解答本题之前，需要了解 数据结构——优先队列，从优先队列中可以学到 大顶堆 的实现，由此可以类比出 小顶堆 的实现，它们的核心概念如下：

• 大顶堆：父节点的值 比 子节点的值 大 的完全二叉树。
• 小顶堆：父节点的值 比 子节点的值 小 的完全二叉树。

根据大、小顶堆的特点设计 findMedian() 方法

本题是一个 设计题，要求这个数据结构能够 返回目前为止所有元素的中位数，可以这样思考：如果将所有（经过 升序 排序后的）元素分为两半，放入不同的堆中：

• 将小的一半放入大顶堆，大顶堆的堆顶元素就是小的一半元素中最大的那个。
• 将大的一半放入小顶堆，小顶堆的堆顶元素就是大的一半元素中最小的那个。

如果大、小顶堆的元素数量不同，那么 元素多的堆的堆顶元素 就是中位数；如果相同，那么 将大、小顶堆的堆顶元素求和并除以 2.0 即可 获得中位数。

对数据流的特殊处理

不过，本题并没有一次给一个数组，而是每次添加一个元素，所以需要解决两个问题：

1. 将新元素放到大顶堆还是小顶堆？
   • 如果大、小顶堆的元素个数相同，则将新元素放到大顶堆。
   • 否则大、小顶堆的元素个数不同，则将新元素放到小顶堆，保持两个堆的元素数量差值不大于 1。
2. 如何进行排序？
   • 假如大、小顶堆中已经有一些元素了，现在要添加一个新元素，如果直接将其添加到单个堆中，那么会导致 堆中存储的元素不是按升序排列的连续的一半，而如果 先将其加到另一个堆中，再取出另一个堆中的堆顶元素，将其放入原本选择的堆中，此时可以保证堆中存储的元素是按升序排列的连续的一半。

大、小顶堆实现差异

本题解中将大顶堆和小顶堆揉合到一起，通过 private boolean isMaxHeap; 这个变量来区分，从而针对不同的堆有不同的行为。实际上这两个堆的行为差异很小，只有 上浮、下潜 这两个操作的具体实现不同，可以将元素理解成空气：

• 越 轻 的元素越在 上面，也就是需要上浮。
• 越 重 的元素越在 下面，也就是需要下潜。

大顶堆和小顶堆对 轻 和 重 的定义不同：

• 大顶堆：越大的元素越轻，越小的元素越重。
• 小顶堆：越小的元素越轻，越大的元素越重。

代码

class MedianFinder {
    public MedianFinder() {}
    
    public void addNum(int num) {
        if (maxHeap.getSize() == minHeap.getSize()) {
            // 如果两个堆的元素个数相同，最终 将新元素加入到 大顶堆 中
            minHeap.offer(num); // 先给 小顶堆 添加元素
            maxHeap.offer(minHeap.poll()); // 然后把 小顶堆 弹出的元素加入到 大顶堆
        } else {
            // 否则大顶堆的元素个数多，最终 将新元素加入到 小顶堆 中
            maxHeap.offer(num); // 先给 大顶堆 添加元素
            minHeap.offer(maxHeap.poll()); // 然后把 大顶堆 弹出的元素加入到 小顶堆
        }
    }
    
    public double findMedian() {
        if (maxHeap.getSize() == minHeap.getSize()) { // 如果两个堆的元素个数相同
            // 则 中位数 是 大顶堆 和 小顶堆 堆顶元素之和的一半
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        } else { // 否则 中位数 是 大顶堆 的堆顶元素
            return maxHeap.peek();
        }
    }

    private Heap maxHeap = new Heap(10, true); // 大顶堆，初始容量为 10
    private Heap minHeap = new Heap(10, false); // 小顶堆，初始容量为 10

    private static class Heap { // 堆
        public Heap(int capacity, boolean isMaxHeap) {
            data = new int[capacity];
            this.isMaxHeap = isMaxHeap;
        }
        // 获取堆中存储的元素数量
        public int getSize() {
            return size;
        }
        // 添加新值
        public void offer(int value) {
            if (isFull()) { // 当堆满之后
                grow(); // 进行扩容，然后再放元素
            }

            int child = up(value);
            data[child] = value;
            size++;
        }
        // 删除堆顶元素
        public int poll() {
            int value = data[0];
            swap(0, --size);
            down(0);
            return value;
        }
        // 查看堆顶元素
        public int peek() {
            return data[0];
        }
        // 检查堆是否为空
        public boolean isEmpty() {
            return (size == 0);
        }
        // 检查堆是否已满
        public boolean isFull() {
            return (size == data.length);
        }
        // 上浮
        private int up(int value) {
            int child = size;
            int parent = getParent(child);
            // 只要 value 轻，就一直让它上浮，直到根节点
            while (child > 0 && isLighter(parent, value)) {
                data[child] = data[parent];
                child = parent;
                parent = getParent(parent);
            }
            return child;
        }
        // 判断 value 是否比 index 指向的元素 轻
        private boolean isLighter(int index, int value) {
            if (isMaxHeap) {    // 大顶堆中，越大的值越轻
                return (value > data[index]);
            } else {            // 小顶堆中，越小的值越轻
                return (value < data[index]);
            }
        }
        // 下潜
        private void down(int parent) {
            int left = getLeft(parent);
            int right = left + 1;
            int lightest = parent; // 最轻的元素的索引

            // 如果 lightest 指向的元素 比 left 指向的元素 重
            if (left < size && isHeavier(lightest, left)) {
                // 则将 lightest 更新为 left
                lightest = left;
            }
            // 如果 lightest 指向的元素 比 right 指向的元素 重
            if (right < size && isHeavier(lightest, right)) {
                // 则将 lightest 更新为 right
                lightest = right;
            }

            // 如果父节点是最轻的元素，那么它就不需要下沉
            if (lightest == parent) {
                return;
            }

            swap(lightest, parent);
            down(lightest);
        }
        // 判断 i 指向的元素 是否比 j 指向的元素 重
        private boolean isHeavier(int i, int j) {
            if (isMaxHeap) {    // 大顶堆中，越小的值越重
                return (data[i] < data[j]);
            } else {            // 小顶堆中，越大的值越重
                return (data[i] > data[j]);
            }
        }
        // 根据 子节点 的索引返回 父节点 的索引
        private int getParent(int child) {
            return (child - 1) >> 1;
        }
        // 根据 父节点 的索引返回 左子节点 的索引
        private int getLeft(int parent) {
            return (parent << 1) + 1;
        }
        // 交换指定索引的元素
        private void swap(int i, int j) {
            int temp = data[j];
            data[j] = data[i];
            data[i] = temp;
        }
        // 扩容
        private void grow() {
            int newCap = size + (size >> 1); // 新数组的容量为原数组的 1.5 倍
            int[] newData = new int[newCap];
            System.arraycopy(data, 0, newData, 0, size);
            data = newData;
        }
        private int[] data; // 存储数据的数组
        private int size; // 当前存储的元素个数
        private boolean isMaxHeap; // 是否是大顶堆
    }
}