剑指offer 面试16题

面试16题：

题目：数值的整数次方

题：实现函数double Power(double base, int exponent)，求base的exponent次方、不得使用库函数，同时不需要考虑大数问题。

解题思路：主题考虑底数为0.0，指数为负数的情况，此时可以利用全局变量指出g_InvalidInput为True,同时返回0.0

解题代码：

# -*- coding:utf-8 -*-

class Solution:

    g_InvalidInput = False

    def Power(self, base, exponent):

        # write code here

        if base==0.0 and exponent<0:

            g_InvalidInput=True

            return 0.0

        if exponent>=0:

            return self.PowerWithUnsignedExponent(base,exponent)

        return 1.0/self.PowerWithUnsignedExponent(base,-exponent)

    def PowerWithUnsignedExponent(self,base,exponent):

        result=1.0

        for i in range(exponent):

            result *= base

        return result

解题优化：上述代码PowerWithUnsignedExponent部分还可以优化如下：使用平方的一半*平方的一半来计算平方，此时时间复杂度为O(logn)。同时涉及除以2用右移运算符代替，判断奇偶数时用位与运算代替求余运算符，这样效率高很多。

解题代码：

# -*- coding:utf-8 -*-

class Solution:

    def __init__(self):

        self.g_InvalidInput=False

    def Power(self, base, exponent):

        # write code here

        if base==0.0 and exponent<0:

            self.g_InvalidInput=True

            return 0.0

        if exponent>=0:

            return self.PowerWithUnsignedExponent2(base,exponent)

        return 1.0/self.PowerWithUnsignedExponent2(base,-exponent)

    def PowerWithUnsignedExponent2(self, base, exponent):

        if exponent==0:

            return 1

        if exponent==1:

            return base

        res=self.PowerWithUnsignedExponent2(base,exponent>>1)

        res *= res

        if exponent & 0x1==1:

            res*=base

        return res