【LeetCode】50、Pow(x,n)

50、Pow(x,n)Pow(x,n)

难度：中等

题目描述

英文：

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

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

示例

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 $[-2^{31},2^{31}-1]$

解题思路

思路一

递归思路，直接用for循环让x乘以自己n次会超时。用递归的思路，对计算过程进行二分计算。每次把n缩小一半，直至n缩小为0。任何数的0次方都为1，这是终止条件。如果n是偶数，返回值算个平方返回即可，如果n是奇数，则平方之后再乘以一次x。

需要注意的是，n可能为负数，如果n是负数的话，就先用绝对值计算，再对结果取倒数。

但按上述思路简单实现后，对于负2的31次方这个测试用例，由于绝对值超过整型最大值，所以溢出了。所以换一种写法，在每次递归中都处理n的正负，然后做相应的变换。

代码提交

C++，用时8ms，内存10M

class Solution {
public:
    double myPow(double x, int n) {
        if (n == 0) return 1;
        double half = myPow(x, n / 2);
        if (n % 2 == 0) return half * half;
        if (n > 0) return half * half * x;
        return half * half / x;
    }
};

进行Recursion探索时完成的，其他解法后续补充。

思路二

用迭代的方法，将i初始化为n，看i是否是2的倍数，如果是，则x乘以自己即可，如果不是，则temp要再乘以x，i逐次减半，直到为0停止循环。最后看n的正负，并做相应处理。

代码提交

C++，用时8ms，内存10M

class Solution {
public:
    double myPow(double x, int n) {
        double res = 1.0;
        for (int i = n; i != 0; i /= 2) {
            if (i % 2 != 0) res *= x;
            x *= x;
        }
        return n < 0 ? 1 / res : res;
    }
};