剑指 Offer16-数值的整数次方

剑指Offer16-数值的整数次方

实现 pow(x, n) ,即计算 x 的 n 次幂函数(即,xn)。不得使用库函数,同时不需要考虑大数问题。

示例 1:


输入:x = 2.00000, n = 10

输出:1024.00000

示例 2:


输入:x = 2.10000, n = 3

输出:9.26100

示例 3:


输入:x = 2.00000, n = -2

输出:0.25000

解释:2-2 = 1/22 = 1/4 = 0.25

提示:

-100.0 < x < 100.0

-2^(31) <= n <= 2^(31)-1

-10^4 <= x^n <= 10^4

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof

一解

使用快速幂解决:

将上述运算用符号表示:

由于 bi 有01两种情况:

bi = 0时:

x2ibi = 1

bi = 1时:

x2ibi = x2i


class Solution:

    def myPow(self, x: float, n: int) -> float:

        if x == 0:

            return 0

        # n < 0 时,x^-2 = (1/x)^2

        if n < 0:

            n, x = -n, 1/x

        res = 1

        while n:

            # 判断二进制最右面的数是否为 1

            if n & 1:

                 # x^(2^i)

                res *= x

            # x^(2^(i+1))

            x *= x

            # 右移一位

            n >>= 1

        return res

很多人不理解,快速幂快在哪里?

下面的算法,要进行n次运算,而快速幂只需要n的二进制的长度次:

比如9876

  • 普通算法:9876

  • 快速幂:987610 0110 1001 0100(二进制),长度为14,计算14


class Solution:

    def myPow(self, x: float, n: int) -> float:

        if n < 0:

            n, x = -n, 1/x

        result = 1

        while n != 0:

            result *= x

            n -= 1

        return result

1 Like
import time
from functools import wraps


def timethis(func):
    @wraps(func)
    def wrapper(*args, **kwargs):
        start = time.time()
        result = func(*args, **kwargs)
        end = time.time()
        print(f"func {func.__name__} run {end - start} s")
        return result

    return wrapper


class Solution:

    @timethis
    def myPow(self, x: float, n: int) -> float:
        if x == 0:
            return 0
        # n < 0 时,x^-2 = (1/x)^2
        if n < 0:
            n, x = -n, 1 / x
        res = 1
        while n:
            # 判断二进制最右面的数是否为 1
            if n & 1:
                # x^(2^i)
                res *= x
            # x^(2^(i+1))
            x *= x
            # 右移一位
            n >>= 1
        return res


print(Solution().myPow(22, 500))


@timethis
def my_pow(x: float, n: int) -> float:
    if x == 0:
        return 0
    if n < 0:
        x, n = 1 / x, -n
    elif n == 0:
        return 1
    else:
        res = 1
        while n > 0:
            res *= x
            n -= 1
        return res


print(my_pow(22, 500))

这个比正常乘积快很多,应该数值越大越明显

func myPow run 1.6927719116210938e-05 s
162682340185280589684399673739785336375464574929263083585020771269597641831590836674610436789332474924071305129427327247893917148681006208568781193983328435209736520891570695193808702178081883775191857370045854699638255840761178047937534795398619179991734821370147275102175630623780378929380280957610636947404398456796904514361070431673380738436551665305817580663310264776564510905087403380320860030247314634374797327243866439609828825321528550916862229724645348080285831007224322697120912040419898692902360077248415336302479967871146438553740502543845353859715671396462388844772002496955199206462308455849823195683382036430621297380424060001784641049649781081395876069376
func my_pow run 0.00012421607971191406 s
162682340185280589684399673739785336375464574929263083585020771269597641831590836674610436789332474924071305129427327247893917148681006208568781193983328435209736520891570695193808702178081883775191857370045854699638255840761178047937534795398619179991734821370147275102175630623780378929380280957610636947404398456796904514361070431673380738436551665305817580663310264776564510905087403380320860030247314634374797327243866439609828825321528550916862229724645348080285831007224322697120912040419898692902360077248415336302479967871146438553740502543845353859715671396462388844772002496955199206462308455849823195683382036430621297380424060001784641049649781081395876069376

快速幂计算吗? 但是实际运行发现没比直接计算快多少额?为什么?

def pow(x,n):
    if n==0:
        return 1
    elif n<0:
        return 1/pow(x,-n)
    elif n%2==1:
        return x*pow(x,n-1)
    else:
        return pow(x*x,n//2)

你这个跑不通: 2.00000 -2

考虑这个输入:

2.00000 -2147483648

def my_pow(x: float, n: int) -> float:
    if x == 0:
        return 0
    if n < 0:
        x, n = 1 / x, -n
    elif n == 0:
        return 1
    res = 1
    while n > 0:
        res *= x
        n -= 1
    return res

确实,多谢指正,逻辑有错误

关闭