leetcode 50 Pow(x, n)
z
 2017-12-15 20:29:08  

50. Pow(x, n)

Implement pow(x, n).

Example 1:

1
2
3
Input: 2.00000, 10
Output: 1024.00000

Example 2:

1
2
Input: 2.10000, 3
Output: 9.26100
  • 最要考察递归，初始的idea是pow(x, n) = x*pow(x, n-1) 但是这样的递归势必会造成栈溢出
  • 如果n是2的倍数，则可以进一步转换为pow(x, n) = pow(x,n/2)*pow(x, n/2) 但是这样有包含重复计算的子问题
  • 进一步转换 pow(x, n) = pow(x*x,n/2)
  • 同时，考虑当n小于0时，$x^n = \frac{1}{x}^{-n}$ 所以我们需要将x = 1/x, 同时 n = -n;
  • 注意： 在对一个int类型取反的时候，一定要考虑溢出问题，对于一个int类型的数，范围为[$-2^{31}, 2^{31}-1$], 如果对$-2^{31}$ 取反，就会造成溢出问题，因此需要考虑当n== Integer.MIN_VALUE的问题。
  • 当n== Integer.MIN_VALUE,如果x==1的话，1的任何次方都为1，当x != 1 的话，相当于是$\frac{1}{x}^{+∞}$ == 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public double myPow(double x, int n) {
        if (n== Integer.MIN_VALUE ){
            if (x == 1 || x == -1){
                return 1;
            }
            else{
                return 0;
            }
        }
        
        if (n==0){
            return 1;
        }
        if (n<0){
            x = 1/x;
            n = -n;
        }
        if (n%2 == 0)
            return myPow(x*x, n/2);
        return x*myPow(x,n-1);
    }
}
1