剑指 Offer 16 . 数值的整数次方

大家好，我是程序员吴师兄，欢迎来到 图解剑指 Offer 结构化专栏，在这个专栏里我将和大家一起学习如何用结构化的思维来思考、解题、写代码，希望能帮助你即使在面试的时候紧张也能做对。

今天分享的题目来源于 LeetCode 上的剑指 Offer 系列 面试题16 . 数值的整数次方。

题目汇总链接：https://www.algomooc.com/hi-offer

一、题目描述

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xⁿ）。不得使用库函数，同时不需要考虑大数问题。

示例 1：

输入：x = 2.00000, n = 10
输出：1024.00000

示例 2：

输入：x = 2.10000, n = 3
输出：9.26100

示例 3：

输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25

提示：

• -100.0 < x < 100.0
• -2³¹ <= n <= 2³¹-1
• -10⁴ <= xⁿ <= 10⁴

二、题目解析

我们依旧用 四步分析法 进行结构化的分析。

• 模拟：模拟题目的运行。
• 规律：尝试总结出题目的一般规律和特点。
• 匹配：找到符合这些特点的数据结构与算法。
• 边界：考虑特殊情况。

1、模拟

第一想法就是利用循环，将 n 个 x 连乘起来立马得到答案，比如 x = 2，n = 11，需要进行 11 次循环的乘法，但基于这种做法实现的代码一提交显示超时，所以我们考虑的方向就是如何缩减计算的次数。

当计算到 2⁵ 时，它的结果进行平方操作即可得到 2¹⁰ ，相比较于 2⁵ * （2 * 2 * 2 * 2 * 2）减少了 4 次运算。

即 2¹¹ = 2⁵ * 2⁵ * 2。

2、规律

如果 n 为奇数，最终结果为 x * x^{n – 1}

如果 n 为偶数，最终结果为 x^{2 * (n/2)}

3、匹配

递归。

4、边界

当 n = 0 时，返回 1。

当 n < 0 时，返回 1/ x^-n

同时，Java 代码中 int32 变量的范围是 [−2147483648,2147483647]，当n = -2147483648，取绝对值为 2147483648 会发生越界的情况，为避免越界提取一个 x ，把 xⁿ 变成了 x * x^n-1，即将 n 变成了 n – 1，这样取绝对值是不会越界。

三、动画描述

四、图片描述

五、参考代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
class Solution {
    public double myPow(double x, int n) {
        //当 n = 0 时，返回 1
        if(n == 0){
            return 1;
        }else if(n < 0){
            // 当 n < 0 时，返回 1/ x^-n
            return 1 / (x * myPow(x, - n - 1));
        }else if(n % 2 == 1){
            //为避免越界，提取 x
            return x * myPow(x, n - 1);
        }else{
            return myPow(x * x, n / 2);
        }     
    }
}

六、复杂度分析

时间复杂度

时间复杂度为 O(logN)。

空间复杂度

空间复杂度为 O(logN)。

七、相关标签

• 递归

程序员吴师兄算法训练营永久会员

打赏 收藏 海报 链接