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


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

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

一、题目描述

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

示例 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
  • -231 <= n <= 231-1
  • -104 <= xn <= 104

二、题目解析

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

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

1、模拟

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

当计算到 25 时,它的结果进行平方操作即可得到 210 ,相比较于 25 * (2 * 2 * 2 * 2 * 2)减少了 4 次运算。

面试题 16.数值的整数次方.003

面试题 16.数值的整数次方.005

即 211 = 25 * 25 * 2。

2、规律

如果 n 为奇数,最终结果为 x * xn – 1

如果 n 为偶数,最终结果为 x2 * (n/2)

3、匹配

递归。

4、边界

当 n = 0 时,返回 1。

当 n < 0 时,返回 1/ x-n

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

三、动画描述

隐藏内容
  • 普通用户购买价格:5积分
  • 会员用户购买价格:免费
  • 永久会员用户购买价格:免费推荐

四、图片描述

面试题 16.数值的整数次方新.002

面试题 16.数值的整数次方新.003

面试题 16.数值的整数次方新.004

面试题 16.数值的整数次方新.005

面试题 16.数值的整数次方新.006

面试题 16.数值的整数次方新.007

面试题 16.数值的整数次方新.008

面试题 16.数值的整数次方新.009

面试题 16.数值的整数次方新.010

五、参考代码

// 登录 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)。

七、相关标签

  • 递归

发表评论

邮箱地址不会被公开。 必填项已用*标注