Pow(x, n)

Posted on |

问题描述（难度中等）

Implement pow(x, n), which calculates x raised to the power n (xn).

Example 1:

1
2
Input: 2.00000, 10
Output: 1024.00000

Example 2:

1
2
Input: 2.10000, 3
Output: 9.26100

Example 3:

1
2
3
Input: 2.00000, -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25

Note:

  • -100.0 < x < 100.0
  • n is a 32-bit signed integer, within the range [−231, 231 − 1]

递归经典范式

递归的写法主要包括四个部分，第一个recursion terminater终止条件，第二个process logic in current level当前level需要执行的逻辑，第三个drill down进入到下一层，第四个reverse the current level status if needed内层结束后继续执行。

cmd-markdown-logo

方法一：递归方式一

通过递归的方式将n次方的问题拆分成n/2的子问题，时间复杂度减少到logn。x的n次转换为x^2的n/2次子问题。

方法一代码

1
2
3
4
5
6
7
8
9
10
11
12
public double myPow(double x, int n) {
        if(n == 0){
            return 1;
        }else {
            //偶数直接转化为子问题
            if((n & 1)==0){
                return myPow(x*x,n/2);
            }else {
                return n<0?1/x*myPow(1/x*1/x,n/2):x*myPow(x*x,n/2);
            }
        }
    }

方法二：递归方式二

利用递归范式的第四步，子问题返回的结果乘以自身。

方法二代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public double myPow1(double x, int n) {
    	//
        if(n == 0){
            return 1;
        }else {
            double temp=myPow(x,n/2);

            //偶数直接转化为子问题
            if((n & 1)==0){
                return temp*temp;
            }else {
                return n<0?1/x*temp*temp:x*temp*temp;
            }
        }
    }

方法三：非递归方式

不采用递归的方式。

方法三代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
double myPow(double x, int n) { 
    if(n==0) return 1;
    if(n<0) {
        n = -n;
        x = 1/x;
    }
    double ans = 1;
    while(n>0){
        if(n&1) ans *= x;
        x *= x;
        n >>= 1;
    }
    return ans;
}

总结

这道题主要是理解递归的范式，递归虽然简洁还是需要灵活运用。