剑指offer 12. 数值的整数次方

12. 数值的整数次方

题目描述

实现函数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/22 = 1/4 = 0.25

说明:

-100.0 < x < 100.0
n 是 32 位有符号整数，其数值范围是 [−2

³¹

, 2

³¹

 − 1] 。

分析：

0的任何次幂都是0，非零整数的 0 次幂都是1，整数的负数次幂等于整数的倒数的正数次幂，最后折半递归，判断指数的奇偶，如果是奇数还要多乘一个x

 1 class Solution {
 2     public double myPow(double x, int n) {
 3         if(x == 0){
 4             return 0;
 5         }
 6         // 递归
 7         // 递归边界是0
 8         //long power = n;
 9         if(n == 0){
10             return 1;
11         }
12         if(n < 0){
13             return myPow(1/x, -n);  // 如果幂指数为负，底数取倒数，幂指数取反
14         }
15 
16         // 折半递归
17         double temp = myPow(x, n/2);
18         temp *= temp;
19         if((n % 2) == 1){   // 奇数, 如果是奇数还要多乘一个x,
20             temp *= x;
21         }
22         return temp;
23     }
24 }

上面的程序其实是有问题的，因为n是int类型的，范围是[-2³¹, 2³¹-1], 如果 n = -2³¹, 那取反后就越界了，所以有两种解决办法，

① 一种是把 n 用一个long变量存下来，这样取反后就不会越界了，只适用于非递归方式

② 另一种是在把n取反的时候1/x提取出来一个，这样就不会越界了，

分别的代码如下

思路参考：

https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/solution/mian-shi-ti-16-shu-zhi-de-zheng-shu-ci-fang-kuai-s/

https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/solution/fei-di-gui-he-di-gui-de-liang-chong-jie-jue-fang-s/

① 一种是把 n 用一个long变量存下来

n = b0*2⁰ + b1*2¹ + b2*2² + ... + bi*2ⁱ (bi=0/1), 只有bi等于1才对n的值有作用

，只有bi等于1才对 xⁿ有作用，因为x⁰ = 1, 所以我们应该让n不断右移一位，等n的二进制最后一位是1的时候，让 res 乘上当前基数即可，如果n的二进制位的最后一位是0，继续计算当前位的基数，为后续做铺垫。

 1 class Solution {
 2     public double myPow(double x, int n) {
 3         // 非递归方式
 4         if(x == 0){
 5             return 0;
 6         }
 7         long power = n;
 8         if(n < 0){
 9             power = -power;
10             x = 1/x;
11         }
12         double res = 1.0, temp = x;
13         while(power != 0){
14             
15             if((power & 1) == 1){
16                 res *= x;
17             }
18 
19             x = x * x;
20             power >>= 1;
21         }
22         return res;
23     }
24 }

② 另一种是在把n取反的时候1/x提取出来一个

 1 class Solution {
 2     public double myPow(double x, int n) {
 3         if(x == 0){
 4             return 0;
 5         }
 6         // 递归，递归边界是0
 7         //long power = n;
 8         if(n == 0){
 9             return 1;
10         }
11         if(n < 0){
12             return 1/x * myPow(1/x, -n-1);  // 如果幂指数为负，底数取倒数，幂指数取反
13         }
14 
15         // 折半递归
16         double temp = myPow(x, n/2);
17         temp *= temp;
18         if((n % 2) == 1){   // 奇数, 如果是奇数还要多乘一个x,
19             temp *= x;
20         }
21         return temp;
22     }
23 }

复杂度分析：

时间复杂度：折半求幂，所以时间复杂度为O(logn)

空间复杂度：递归方式下有个栈的空间复杂度，为O(logn), 非递归方式下空间复杂度为O(1)