LeetCode 50. Pow(x, n) (Tag:Binary Search)

1. 问题描述

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

Example 1:

代码语言：javascript复制

Input: 2.00000, 10
Output: 1024.00000

Example 2:

代码语言：javascript复制

Input: 2.10000, 3
Output: 9.26100

Example 3:

代码语言：javascript复制

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次方。

2. 解题思路

• 以x的平方为最小算子
• 若n为负数，注意note中的提示，求 1/x 的 -(n)次方 , 然后再乘以 1/x , 不然当 n=-2^31时，直接取-n会导致int溢出。
• 若n为2，则返回n*n
• 若n为偶数，myPow(myPow(x, n / 2), 2)
• 若为奇数，x * myPow(myPow(x, n / 2), 2);

3. 代码

代码语言：javascript复制

class Solution {
    public double myPow(double x, int n) {
        if (n < 0) {
            return  1 / x * myPow(1 / x, -(n   1));
        }
        if (n == 0) {
            return 1.0;
        }
        if (n == 2) {
            return x * x;
        }
        if ( n % 2 == 0) {
            return myPow(myPow(x, n / 2), 2);
        }else{
            return x * myPow(myPow(x, n / 2), 2);
        }
    }
}

bit int integer range

0 人点赞