首页 > 代码库 > LeetCode: Pow(x, n) 解题报告

LeetCode: Pow(x, n) 解题报告

2024-08-08 23:31:15   221人阅读

Pow(x, n)

Implement pow(x, n).

技术分享

SOLUTION 1:

使用二分法。

1. 负数的情况，使用以下的公式转化为求正数power，另外，考虑到MIN_VALUE可能会造成越界的情况，我们先将负数+1：

X^(-n) = X^(n + 1) * X
X^n = 1/(x^(-n))

2. Base case: pow = 0, RESULT = 1;

3. 正数的时候，先求n/2的pow，再两者相乘即可。

当n = -2147483648 必须要特别处理，因为对这个数取反会得到相同的数（已经越界）
所以当n为负时，先加个1再说。具体可以看代码。

先计算出x的n/2次方，再自乘一下。另外，注意n%2如果为1，
记得再乘以x

如果n是负数，所有计算完成后，执行x=1/x就行

技术分享
 1 public class Solution { 2     public double pow(double x, int n) { 3         if (x == 0) { 4             return 0; 5         } 6          7         // base case: when n = 0, the result is 1; 8         if (n == 0) { 9             return 1;10         }11         12         /*13         递归的主体部分14         */15         16         // X^(-n) = X^(n + 1) * X17         // X^n = 1/(x^(-n))18         if (n < 0) {19             double ret = x * pow(x, -(n + 1));20             return (double)1/ret;21         }22         23         // 将求pow对半分。再将结果相乘24         double ret = pow(x, n / 2);25         ret = ret * ret;26         27         //如果有余数，再乘以x本身。28         if (n % 2 != 0) {29             ret = ret * x;30         }31         32         return ret;33     }34 }
View Code

GITHUB:

https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/divide2/Pow_1219_2014.java

 

LeetCode: Pow(x, n) 解题报告


联系
我们