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]

描述

實現(xiàn)pow（x，n），即計算x的n次方

思路

• 拿到這道題第一個想到的是循環(huán)，但是循環(huán)顯然不是這道題考察的重點，而且，在此題中，采用循環(huán)（或者遞歸）會超時
• 此題主要考察二分法
• 我們計算x^{n時(以計算2}8說明)，如果采用循環(huán)需要進行乘法運算約8(O(n))次，但是如果使用二分法，計算2*2得到4，計算4*4得到16，計算16*16得到245，只需要3(log2(8))次
• 即2⁸⁼⁽⁽⁽²2)²⁾2)
• pow(x,n)中，我們每次讓x自乘一次，n就可以減半，這里要注意奇數(shù)的情況，如果n是奇數(shù)，需要在結(jié)果中自乘一下當前的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為負數(shù)，則轉(zhuǎn)換為(1/x)^(-n)的形式
        if n < 0:
            x = 1/x
            n = -n
        # 初始化res為1
        res = 1
        while n > 1:
            # 如果n為奇數(shù)，res則需要乘以x一次
            if n % 2:
                res *= x
            # x自乘一次
            x *= x
            # n整除2
            n //= 2
        return res*x

• 源代碼文件在這里
• ?本文首發(fā)于何睿的博客，歡迎轉(zhuǎn)載，轉(zhuǎn)載需保留文章來源，作者信息和本聲明.