50. Pow(x, n)

题目链接

50. Pow(x, n)

标签

递归 数学

思路

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

  • 如果 n n n 是奇数,由于 n / 2 n / 2 n/2向下取整,所以 x n 2 ∗ x n 2 ≠ x n x^{\frac{n}{2}} * x^{\frac{n}{2}} \not = x^n x2nx2n=xn,而 x ∗ x n 2 ∗ x n 2 = x n x * x^{\frac{n}{2}} * x^{\frac{n}{2}} = x^n xx2nx2n=xn
  • 如果 n n n 是偶数,则 x n 2 ∗ x n 2 = x n x^{\frac{n}{2}} * x^{\frac{n}{2}} = x^n x2nx2n=xn

直到所求的幂为 0 0 0 1 1 1:如果幂为 0 0 0,直接返回 1 1 1 即可;如果幂为 1 1 1,直接返回 x x x 自身。

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

代码

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; // 是否是大顶堆
    }
}

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部