50. Pow(x, n)

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

二分递归思想:最容易想到的是这个方法。注意一下幂次奇偶性。
不论我们返回时候如何,我们执行第一步,先设立Base Case:
if n == 0: return 1
完了以后,我们要对大问题进行拆分,也就是不断的对b的值折半
拆分:half = self.myPow(x, n // 2)
当拆分到了最小的问题,满足base case n == 0 的时候,我们则进行返回,返回时候有三种可能

Function的三种可能性:
当b为偶数的时候,比如 2 ^ 100,拆分的时候就变成 (2 ^ 50) (2 ^ 50)
当b为基数的时候,比如 2 ^ 25,拆分的时候就变成 (2 ^12)
(2 ^ 12) * 2
当b为负数的时候,返回 1.0 / self.myPow(a, -b)
问题分析草稿

class Solution(object):
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        if n < 0:
            return 1/self.tool( x , -n)
        return self.tool(x,n)

    def tool(self,x,n):
        if n == 0:
            return 1
        t = n // 2
        res = self.myPow(x , t)
        print(res)
        if n % 2 == 0:
            return res * res
        return res * res * x

请多多指教。

文章标题:50. Pow(x, n)

本文作者:顺强

发布时间:2020-04-13, 23:59:00

原始链接:http://shunqiang.ml/leetcode-50-pow/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

目录
×

喜欢就点赞,疼爱就打赏