剑指 Offer 16. 数值的整数次方 | Java 刷题打卡

本文正在参加「Java主题月 – Java 刷题打卡」，详情查看 活动链接

题目

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

描述

实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。

示例 1:

输入: 2.00000, 10

输出: 1024.00000

示例 2:

输入: 2.10000, 3

输出: 9.26100

示例 3:

输入: 2.00000, -2

输出: 0.25000

解释: 2^-2 = 1/2² = 1/4 = 0.25

说明:

• -100.0 < x < 100.0
• n 是 32 位有符号整数，其数值范围是 [−2³¹, 2³¹  − 1] 。

实现方法

方法 1

思路

1. 暴力方法，但是时间复杂度（$O(n)$）太高，会超时
2. 求 x 的 n 次方，无非就是 n 个 x 相乘
3. 然后根据 n 的值，返回不同的结果
   • n = 0，返回 1
   • n > 0，返回 pow(x, n) 的值
   • n < 0，返回 1/pow(x, -n) 的值

实现

public double myPow(double x, int n) {
    // x 的 0 次方等于 1
    if(n == 0){
        return (double) 1;
    }

    return n > 0 ? powDemo(x, n): 1/powDemo(x, -n);
}


public double powDemo(double x, int n){
    long N = n;
    double ans = 1.0d;

    for(int i = 0; i < N; i++){
        ans *= x;
    }

    return ans;
}
复制代码

方法 2

思路

1. 快速幂 + 递归，即分治
2. $x^n=x^{n/2}×x^{n/2}=(x^2)^{n/2}$ ，令 $n/2$ 为整数，则需要分为奇偶两种情况（设向下取整除法符号为 “//” ）：

$x^n = \begin{cases} (x^2)^{n//2} , n 为偶数 \\ x(x^2)^{n//2} , n 为奇数\end{cases}$

当 n 为奇数时，二分后会多出一项 x 。

3. 此时时间复杂度为 $O(logn)$

实现

public double myPow(double x, int n) {
    // int 转换为 long，防止越界
    long N = n;
    return N >= 0? powDemo(x, N):1.0/powDemo(x, -N);
}


public double powDemo(double x, long N){

    // 边界情况    
    if(N == 0){
        return 1.0;
    }

    double ans = powDemo(x, N / 2);

    return N % 2 == 0? ans * ans: ans * ans * x;
}
复制代码