50. Pow(x, n) [python]

【Description】
Implement pow(x, n), which calculates x raised to the power n (xⁿ).

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]

【Idea】
主要是注意 x和n 在不同取值范围时的计算方式。
首先考虑特殊值：x=0/ n=1/ n=0/x=1，简化计算；
之后，n<0时，可以将x做一下倒置；
最后，如果直接用for i in range(abs(n)) ，时间复杂度过高会报错，这个题的主要考察点也在于简化次方的循环计算次数。O(n)简化直接想O(log(n)) 必然需要二分回溯，就会联想到抽取平方跳步计算了。
一个tips：
奇数次方时，取 self.calPow(a*a, (b-1)/2) * a 就可以实现回溯了。

【Solution】

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n == 0:
            return 1
        if x == 1 or n == 1 or x == 0:
            return x
        if n < 0:
            x = 1.0/x
        res = self.calPow(x, abs(n))
        return res
        
    def calPow(self, a, b):
        if b == 1:
            return a
        if b%2 == 0:
            result = self.calPow(a*a, b/2)
        if b%2 == 1:
            result = self.calPow(a*a, (b-1)/2) * a
        return result