leetcode 精选top面试题

50. Pow(x, n)

实现 pow(x, n) ，即计算 x 的 n 次幂函数。

示例 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 位有符号整数，其数值范围是 [−231, 231 − 1] 。

思路一：二分法 + 递归（分治思想）

如果n是偶数：myPow(x, n) = myPow(x, n/2) * myPow(x, n/2)；

如果n 是奇数，还需要多乘一个x: myPow(x, n) = myPow(x, n/2) * myPow(x, n/2) * x；

如果n 是偶数，需要转换成求 1/x的-n次幂，即求 myPow(1/x, -1 n);

递归的边界是n == 0, 返回0，任何数的0次幂都是1。

另外一些特殊值x == 0, x == 1, n == 1，这些值的结果都是可以预知的。

 1 class Solution {
 2 
 3     public double myPow(double x, int n) {
 4         // 二分法 + 递归(分治思想)
 5         if(x == 0 || x == 1 || n == 1){ // 0 的任何次方都等于 0,1 的任何次方都等于 1
 6             return x;
 7         }
 8         if(n == 0){
 9             return 1;
10         }
11         if(n < 0){  // 如果指数为负数，转换成正数
12             return myPow(1/x, -1 n);    // 当n刚好是Integer.MIN_VALUE时，乘以一个-1会溢出
13         }
14         double sqrt = myPow(x, n/2);
15         if((n&1) == 0){
16             return sqrt * sqrt;
17         }else{
18             return sqrt * sqrt * x;
19         }
20     }
21 }

但是当n为负数且刚好是Integer.MIN_VALUE时，乘以一个-1会溢出，所以必须借助一个中间函数，把指数类型变成long类型，改变后的编码如下：

 1 class Solution {
 2 
 3     public double quickMulti(double x, long n){
 4         if(n == 0){         // 递归结束的边界
 5             return 1;
 6         }
 7         double sqrt = quickMulti(x, n/2);
 8         if((n&1) == 0){
 9             return sqrt * sqrt;
10         }else{
11             return sqrt * sqrt * x; // 奇数要多乘一个x
12         }
13     }
14 
15     public double myPow(double x, int n) {
16         // 二分法 + 递归(分治思想)
17         if(x == 0 || x == 1 || n == 1){ // 0 的任何次方都等于 0,1 的任何次方都等于 1
18             return x;
19         }
20         return n < 0 ? quickMulti(1/x, -1 * (long)n) : quickMulti(x, n);
21     }
22 }

leetcode 执行用时：1 ms, 在所有 Java 提交中击败了97.96%的用户，内存消耗：37.7 MB, 在所有 Java 提交中击败了30.68%的用户

复杂度分析：

时间复杂度: O(logn)。因为采用的是二分法，所以时间复杂度为O(logn)。

空间复杂度：O(logn)。空间复杂度取决于递归深度，而递归深度刚好是logn, 所以空间复杂度为O(logn)。

思路二：迭代法

思路参考：https://leetcode-cn.com/problems/powx-n/solution/powx-n-by-leetcode-solution/

每个二进制数位都有一个权值，权值如下图所示，最终结果就等于所有二进制位为1的权值之积, 例如上述 x^77次方对应的二进制 (1001101) 和每个二进制位的权值如下和每个二进制位的权值如下

最终结果就是所有二进制位为1的权值之积：x^1 * x^4 * x^8 * x^64 = x^77

而且我们不必预先把每一个二进制位的权值计算出来，我们可以一边计算结果，一边计算权值

 1 class Solution {
 2 
 3     public double myPow(double x, int n) {
 4         // 迭代算法，利用二进制位
 5         if(x == 0){ // 0 的任何次方都等于 0,1 的任何次方都等于 1
 6             return x;
 7         }
 8 
 9         long power = n;    // 为了保证-n不溢出，先转换成long类型
10         if(n < 0){         // 如果n小于0， 求1/x的-n次方
11             power *= -1;
12             x = 1 / x;
13         }
14         double weight = x;  // 权值初值为x, 即二进制位第1位的权值为x^1
15         double res = 1;
16         while(power != 0){
17             // 如果当前二进制位为1， 让结果乘上这个二进制位上的权值, 
18             // 该位权值在上一轮迭代中已经计算出来了
19             if((power & 1) == 1){   
20                 res *= weight;
21             }
22             weight *= weight;   // 计算下一个二进制位的权值
23             power /= 2;
24         }
25         return res;
26     }
27 }

leetcode 执行用时：1 ms, 在所有 Java 提交中击败了97.96%的用户, 内存消耗：36.5 MB, 在所有 Java 提交中击败了69.88%的用户，空间效率确实是提升了一些。

复杂度分析：

时间复杂度：O(logn)。利用的二进制位的思想，所以迭代次数是二进制位的长度，所以时间复杂度为O(logn)。

空间复杂度: O(1)。没有借助递归，其他变量都是常量的空间，所以空间复杂度为O(1)。