[LeetCode] 50. Pow(x, n)

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

Example 1:

Input: 2.00000, 10
Output: 1024.00000

Example 2:

Input: 2.10000, 3
Output: 9.26100

Example 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]

题意是求X的N次方。暴力解（把X乘以N次）是过不了的。

思路是用递归。排除了几个 corner case，诸如 N = 0，N = 1和X = 0，剩下的 case 用递归去找X的(N/2)次方的值。同时注意当 N < 0 的时候要取 X 的倒数。

时间O(logn)

空间O(n)

Java实现

 1 class Solution {
 2     public double myPow(double x, int n) {
 3         if (n < 0) {
 4             // n为负返回倒数
 5             return 1 / pow(x, -n);
 6         } else {
 7             // n为正直接返回结果
 8             return pow(x, n);
 9         }
10     }
11 
12     private double pow(double x, int n) {
13         if (n == 0)
14             return 1.0;
15         if (n == 1)
16             return x;
17         double val = pow(x, n / 2);
18         // 根据奇数还是偶数返回不同的值
19         if (n % 2 == 0) {
20             return val * val;
21         } else {
22             return val * val * x;
23         }
24     }
25 }

JavaScript实现

 1 /**
 2  * @param {number} x
 3  * @param {number} n
 4  * @return {number}
 5  */
 6 var myPow = function (x, n) {
 7     // corner case
 8     if (n == 0) return 1;
 9     if (n == 1) return x;
10     if (x == 0) return 0;
11 
12     // normal case
13     if (n < 0) {
14         return myPow(1 / x, -n);
15     } else {
16         if (n % 2 == 0) {
17             return myPow(x * x, parseInt(n / 2));
18         } else {
19             return x * myPow(x * x, parseInt(n / 2));
20         }
21     }
22 };

LeetCode 题目总结