LeetCode 50. Pow(x, n)

Description

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

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]

描述

实现pow（x，n），即计算x的n次方

思路

• 拿到这道题第一个想到的是循环，但是循环显然不是这道题考察的重点，而且，在此题中，采用循环（或者递归）会超时
• 此题主要考察二分法
• 我们计算xn时(以计算28说明)，如果采用循环需要进行乘法运算约8(O(n))次，但是如果使用二分法，计算2*2得到4，计算4*4得到16，计算16*16得到245，只需要3(log2(8))次
• 即28=(((22)2)2)
• pow(x,n)中，我们每次让x自乘一次，n就可以减半，这里要注意奇数的情况，如果n是奇数，需要在结果中自乘一下当前的x，不然会少一次x

class Solution:
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        # 如果n等于0，则不论x为何值，返回1
        if n == 0:
            return 1
        # 如果n为负数，则转换为(1/x)^(-n)的形式
        if n < 0:
            x = 1/x
            n = -n
        # 初始化res为1
        res = 1
        while n > 1:
            # 如果n为奇数，res则需要乘以x一次
            if n % 2:
                res *= x
            # x自乘一次
            x *= x
            # n整除2
            n //= 2
        return res*x

• 源代码文件在这里