投稿
  1. 首页
  2. java

《剑指offer》-day 20 分治算法（中等）【分治 & 快速幂】

code • 2022-4-25 • java • 阅读 52

《剑指offer》-day 20 分治算法（中等）【分治 & 快速幂】,第1张

剑指 Offer 07. 重建二叉树


DFS（分治）⭐️

快速排序 便是采用了 “分治” 的思想

思路 🤔

  1. 需要构建树，所以需要用 root.left、root.right “接住” 下层递归返回结果，所以需要递归返回值

    递归函数设计为：

    // 均为左闭右闭区间
TreeNode build(int preorderStartIndex, int preorderEndIndex, int inorderStartIndex, int inorderEndIndex)

  2. 终止条件：

    • 如果当前子数组为空，即 n < 0，则 return null
    • 如果当前子数组只有一个元素，即 n == 0，说明当前节点为“叶子”节点，则 return root;

  3. 在中序序列中找切分位置：前序第一个节点 preorder[preorderStartIndex]，定为当前子树的 “根节点” root

  4. 找切分位置

    • 根据 root.val，将 inorder 划分为左、右子数组；
    • 根据 inorder 左、右子数组长度，将 preorder 划分为左、右子数组

  5. 分治：分别构建左、右子树

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int[] preorder;
    int[] inorder;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.inorder = inorder;
        this.preorder = preorder;
        int n = preorder.length;
        return build(0, n - 1, 0, n - 1);
    }

    // 均为左闭右闭区间
    TreeNode build(int preorderStartIndex, int preorderEndIndex, int inorderStartIndex, int inorderEndIndex) {
        int n = preorderEndIndex - preorderStartIndex;

        // System.out.println("=====================");
        // System.out.println("n = " + n);
        // System.out.println("preorderStartIndex = " + preorderStartIndex);
        // System.out.println("preorderEndIndex = " + preorderEndIndex);
        // System.out.println("inorderStartIndex = " + inorderStartIndex);
        // System.out.println("inorderEndIndex = " + inorderEndIndex);

        // 终止条件
        if (n < 0) {
            return null;
        }
        // 1、设置根节点
        TreeNode root = new TreeNode(preorder[preorderStartIndex]);
        if (n == 0) { // 叶子节点（这里是左闭右闭区间，所以是 == 0），立即返回
            return root;
        }
        // 2、找切分位置
        int index = inorderStartIndex;
        for ( ; index < inorderEndIndex && inorder[index] != root.val; index++) {}
        // 3、划分左、右区间
        int leftInorderStartIndex = inorderStartIndex;
        int leftInorderEndIndex = index - 1;
        int rightInorderStartIndex = index + 1;
        int rightInorderEndIndex = inorderEndIndex;

        int leftPreorderStartIndex = preorderStartIndex + 1;
        int leftPreorderEndIndex = leftPreorderStartIndex + (leftInorderEndIndex - leftInorderStartIndex);
        int rightPreorderStartIndex = leftPreorderEndIndex + 1;
        int rightPreorderEndIndex = preorderEndIndex;

        // test
        // System.out.println("index = " + index);
        // System.out.println("leftInorderStartIndex = " + leftInorderStartIndex);
        // System.out.println("leftInorderEndIndex = " + leftInorderEndIndex);
        // System.out.println("rightInorderStartIndex = " + rightInorderStartIndex);
        // System.out.println("rightInorderEndIndex = " + rightInorderEndIndex);

        // System.out.println("leftPreorderStartIndex = " + leftPreorderStartIndex);
        // System.out.println("leftPreorderEndIndex = " + leftPreorderEndIndex);
        // System.out.println("rightPreorderStartIndex = " + rightPreorderStartIndex);
        // System.out.println("rightPreorderEndIndex = " + rightPreorderEndIndex);

        // 4、递归构建左、右子树
        root.left = build(leftPreorderStartIndex, leftPreorderEndIndex, leftInorderStartIndex, leftInorderEndIndex);
        root.right = build(rightPreorderStartIndex, rightPreorderEndIndex, rightInorderStartIndex, rightInorderEndIndex);
        return root;
    }
}
剑指 Offer 16. 数值的整数次方

暴力 TLE

前言：由于指数 n 的数据范围为 2 31 − 1 2^{31}-1 231−1，所以采用朴素 O ( n ) O(n) O(n) 的暴力方法时，一定会 TLE。

这里不再提供暴力解法。

快速幂 ⭐️

由于暴力会超时，所以，可以考虑使用 快速幂，最终可以使得 幂运算的时间复杂度由 O ( n ) O(n) O(n) 降为 O ( l o g n ) O(log n) O(logn)

此种解法和 快速幂 -leetcode 1922. 统计好数字的数目 基本类似

快速幂-思路 🤔

  • 每一步都把指数分成两半，而相应的底数做平方运算
    • 指数为偶数时，指数直接减半即可；
    • 指数为奇数时，需要先拿出来一个，将指数变成偶数，然后指数再减半。

例如， 3 10 = ( 3 ∗ 3 ) 5 = 9 5 = 9 ∗ ( 9 ∗ 9 ) 2 = 9 ∗ 8 1 2 = 9 ∗ ( 81 ∗ 81 ) 1 = 9 ∗ 6561 ∗ 8 1 0 = 9 ∗ 6561 = 59049 3^{10} = (3*3)^5 = 9^5 = 9 * (9*9)^2 = 9*81^2 = 9*(81*81)^1 = 9*6561*81^0 = 9*6561 = 59049 310=(3∗3)5=95=9∗(9∗9)2=9∗812=9∗(81∗81)1=9∗6561∗810=9∗6561=59049

class Solution {
    public double myPow(double x, int n) {
        double res = 1.0D;
        // -2^31的相反数，即2^31无法用int表示，所以这里需要用 long 来保存n
        // long power = (n < 0) ? (n * (-1)) : n; // 这里不是不对的 “三目运算符”仍然都是int
        long power = (n < 0) ? (n * (-1L)) : n;
        System.out.println("power = " + power);
        while (power > 0) {
            if (power % 2 == 0) { // 指数为偶数时，直接拆分为原来一般，并将底数平方
                x *= x;
                power /= 2;    
            } else { // 指数为奇数时，需要先将指数拿出来一个。此时，指数变为偶数，再同上指数为偶数的情况做相同 *** 作
                res *= x; // 收集底数
                x *= x; // 此时，指数变为偶数，再同上指数为偶数的情况做相同 *** 作
                power /= 2;
            }
        }
        // x的-n次幂，等于x正n此时的倒数
        System.out.println("res = " + res);
        return n < 0 ? (1.0 / res) : res;
    }
}
  • 时间复杂度： O ( l o g n ) O(logn) O(logn)
  • 空间复杂度： O ( 1 ) O(1) O(1)

两点注意 ⭐️

  1. 要用 long 来保存 power，如果用 int 当 n = 2 31 = ( − 2147483648 ) n = 2 ^ {31} = (-2147483648) n=231=(−2147483648) 时，会造成 int 溢出；

  2. 三目运算符中，一定要有 long 的存在；否则，结果仍然是 int 而造成出错
    错误写法：

    由下图运行结果可见，由于三目运算符中全是 int 类型，此时 power 仍然为负数。

    正确写法：可以在三目运算符中引入long 类型，使其均自动升级为 long 类型

    由下图运行结果可见，此时 power 为理想结果

以上代码，可以精简如下（只是精简重复逻辑、并采用位运算，但本质上并没有提升时间复杂度）

class Solution {
    public double myPow(double x, int n) {
        double res = 1.0D;
        long power = (n < 0) ? (n * (-1L)) : n;
        System.out.println("power = " + power);
        while (power > 0) {
            // 指数为奇数时，需要先将指数拿出来一个。此时，指数变为偶数，再同指数为偶数的情况做相同 *** 作
            if ((power & 1) == 1) { 
                res *= x; // 收集底数
            }
            // 指数为偶数时，直接拆分为原来一半，并将底数平方
            x *= x; // 此时，指数变为偶数，再同上指数为偶数的情况做相同 *** 作
            power >>= 1; 
        }
        // x的-n次幂，等于x正n此时的倒数
        System.out.println("res = " + res);
        return n < 0 ? (1.0 / res) : res;
    }
}
递归 暴力递归

使用暴力递归时，由于时间复杂度为 O ( n ) O(n) O(n)，所用栈深度也为 n n n

所以，当 n 较大时，会造成 栈溢出（栈被递归函数撑爆炸了）

class Solution {
    public double myPow(double x, int n) {
        long power = n < 0 ? (n * -1L) : n;
        double res = pow(x, power);
        System.out.println("power = " + power);
        System.out.println("res = " + res);
        return n < 0 ? (1.0 / res) : res;
    }


    double pow(double x, long n) {
        if (n == 0) {
            return 1;
        }
        return pow(x, n - 1) * x;
    }
}
  • 时间复杂度： O ( n ) O(n) O(n)
  • 空间复杂度： O ( n ) O(n) O(n) （递归使用的栈深度）
递归（快速幂思想）⭐️

可以采用 快速幂思想，进行递归处理，代码如下：]

但是，由于两次递归函数 pow(x, n >> 1) 会造成大量冗余计算，所以最终会 TLE

class Solution {
    public double myPow(double x, int n) {
        long power = n < 0 ? (n * -1L) : n;
        System.out.println("power = " + power);
        double res = pow(x, power);
        return n < 0 ? (1.0 / res) : res;
    }

    double pow(double x, long n) {
        if (n == 0) {
            return 1;
        }
        double odd = 1.0;
        if ((n & 1) == 1) {
            odd = x;
        }
        return pow(x, n >> 1) * pow(x, n >> 1) * odd; // 两个递归函数会造成大量冗余计算，所以会 TLE
    }
}
  • 时间复杂度： O ( l o g n ) O(logn) O(logn)
  • 空间复杂度： O ( ) O() O()


为避免两次递归函数造成大量重复计算，可以采用 cnt 将递归结果保存起来。

最终版 AC 代码如下：

class Solution {
    public double myPow(double x, int n) {
        long power = n < 0 ? (n * -1L) : n;
        System.out.println("power = " + power);
        double res = pow(x, power);
        return n < 0 ? (1.0 / res) : res;
    }

    double pow(double x, long n) {
        if (n == 0) {
            return 1;
        }
        double odd = 1.0;
        if ((n & 1) == 1) {
            odd = x;
        }
        // 保存递归结果，避免重复计算
        double cnt = pow(x, n >> 1);
        return cnt * cnt * odd;
    }
}

剑指 Offer 33. 二叉搜索树的后序遍历序列


提示：

  • 数 组 长 度 < = 1000 数组长度 <= 1000 数组长度<=1000
分治 ⭐️

快速排序 便是采用了 “分治” 的思想

思路 🤔

  1. 如果当前发现不是 BST，则需要立刻返回结果，所以递归函数需要返回类型

    // 左闭右闭区间
boolean verify(int[] postorder, int startIndex, int endIndex)

  2. 终止条件：空树、只有一个节点都是 BST

  3. 划分区间

    利用 BST 性质（"左 < 根，右 > 根”），以及后序遍历顺序为“左右根”，对 postorder 进行区间划分

    • 从 startIndex 开始向右遍历，搜索第一个所有元素均 < postorder[endIndex] 的 左子树区间（即，[startIndex, leftIndex)）
    • 从 leftIndex 开始向右遍历，搜索第一个所有元素均 > postorder[endIndex] 的 右子树区间（即，[leftIndex, rightIndex)）

  4. 验证当前区间是否合法

    如果 rightIndex无法达到 endIndex，即rightIndex < endIndex，则说明无法根据 postorder[endIndex] 将其左边元素分为两堆（无法构成 BST），立刻返回 false；（如下图所示）
    否则，进行第 5 步

  5. 分治：分别判断左、右区间是否合法

    • 左子树区间：[startIndex, leftIndex)
    • 右子树区间：[leftIndex, rightIndex)
class Solution {
    public boolean verifyPostorder(int[] postorder) {
        return verify(postorder, 0, postorder.length - 1);
    }

    // 左闭右闭
    boolean verify(int[] postorder, int startIndex, int endIndex) {
        // 终止条件（空树、只有一个节点都是BST）
        if (endIndex - startIndex <= 1) return true;
        // 划分区间(这里是左闭右开区间，[startIndex, leftIndex) 为左区间、[leftIndex, rightIndex)为右区间）
        int leftIndex = startIndex;
        for ( ; leftIndex < endIndex && postorder[leftIndex] < postorder[endIndex]; leftIndex++) {}
        int rightIndex = leftIndex;
        for ( ; rightIndex < endIndex && postorder[rightIndex] > postorder[endIndex]; rightIndex++) {}
        
        System.out.println("--------------");
        System.out.println("start = " + startIndex);
        System.out.println("end = " + endIndex);
        System.out.println("leftIndex = " + leftIndex);
        System.out.println("rightIndex = " + rightIndex);
        
        // 验证当前区间是否合法（如果rightIndex无法达到endIndex，则说明无法根据postorder[endIndex]将其左边元素分为两堆）
        if (rightIndex < endIndex) {
            return false;
        }
        // 分别判断左、右区间是否合法
        return verify(postorder, startIndex, leftIndex - 1) && verify(postorder, leftIndex, rightIndex - 1);
    }
}

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/721155.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
code code 管理员组
0 0
上一篇 2022-04-25
下一篇 2022-04-25

发表评论

登录后才能评论

评论列表（0条）

保存