LeetCode--050--Pow(x,n) (java and python)

实现 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] 。

思路：不断分解幂进行递归，2^3 = 2^1 * 2^1 * 2 =(2^0 *2^0 *2)(2^0 *2^0*2)*2

 1 class Solution {
 2     public double myPow(double x, int n) {
 3         if(n > 0){
 4             return pow(x,n);
 5         }else{
 6             return 1/pow(x,n);
 7         }
 8     }
 9     public double pow(double x,int n){
10         if(n == 0){
11             return 1;
12         }
13         double y = pow(x,n/2);
14         if(n % 2 == 0){
15             return y * y;
16         }else{
17             return y * y * x;
18         }
19     }
20 }

写法2：

 1 class Solution {
 2     public double myPow(double x, int n) {
 3         if (n == 0)return 1;
 4         double res = 1;
 5         long abs = Math.abs((long)n);
 6         while(abs > 0){
 7             if(abs % 2 != 0){
 8                 res *= x;
 9             }
10             x *= x;
11             abs /= 2;
12         }
13         if(n < 0){
14             return 1/res;
15         }
16         return res;
17     }
18     
19 }

2019-05-08 17:56:53

python版本

 1 class Solution:
 2     def myPow(self, x: float, n: int) -> float:
 3         def help(x,n):
 4             if n == 0:
 5                 return 1
 6             half = help(x,n//2)
 7             if n % 2 == 0:
 8                 return half*half
 9             else:
10                 return half * half * x
11         if n < 0:
12             x = 1 / x
13             n = abs(n)
14         return help(x,n)

2020-01-12 09:02:57