LintCode 428. x的n次幂

发表于 更新于 分类于 阅读次数： Disqus： 本文字数： 188 阅读时长 ≈ 1 分钟

题意

实现 pow(x,n)

注意事项

不用担心精度，当答案和标准输出差绝对值小于1e-3时都算正确

样例

1
2
3
Pow(2.1, 3) = 9.261
Pow(0, 1) = 0
Pow(1, 0) = 1

思路

从数学上来说，(x)的4次方 等于 (x的平方)的平方。我们使用这个思想来做这道题就行了。

其实就和把十进制数转成二进制的思想是一样的。

需要注意的地方是，n可能为负数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    """
    @param: x: the base number
    @param: n: the power number
    @return: the result
    """
    def myPow(self, x, n):
        if n == 0:
            return 1
        if x == 0:
            return 0
        t = x
        if n < 0:
            t = 1 / t
            n = -n
        ans = 1
        while n != 0:
            if n % 2 != 0:
                ans *= t
            t *= t
            n = int(n / 2)
        return ans