前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Leetcode No.50 Pow(x, n)

Leetcode No.50 Pow(x, n)

作者头像
week
发布2022-01-07 14:02:51
1580
发布2022-01-07 14:02:51
举报
文章被收录于专栏:用户画像

题目描述

实现 pow(x, n) ,即计算 x 的 n 次幂函数(即,x^n)。

示例 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

思路1:暴力破解(超时)

代码语言:javascript
复制
class Solution {
    public double myPow(double x, int n) {
        int flg=1;
        if(x<0&&n%2==1){
            flg=-1;
        }
        x=Math.abs(x);
        int p=1;
        if(n<0){
            p=-1;
            n=-n;
        }
        double rs=1;
        while((n--)>0){
            rs=rs*x;
            System.out.println(rs);
        }
        if(p<0){
            rs=1/rs;
        }
        return flg*rs;
    }
}

思路2:快速幂 + 递归

「快速幂算法」的本质是分治算法。举个例子,如果我们要计算 x^64,我们可以按照:

x --> x^2 --> x^4 --> x^8 --> x^16 --> x^32--> x^64

的顺序,从 x开始,每次直接把上一次的结果进行平方,计算 6 次就可以得到 x^64的值,而不需要对 x 乘 63 次 x。

再举一个例子,如果我们要计算 x^77,我们可以按照: x→x^2 →x^4→x^9→x^19→x^38 →x^77的顺序,在 x→x^2,x^2→x^4 ,x^19→x^38 这些步骤中,我们直接把上一次的结果进行平方,而在 x^4→x^9,x^9→x^19,x^38 →x^77 这些步骤中,我们把上一次的结果进行平方后,还要额外乘一个 x。

直接从左到右进行推导看上去很困难,因为在每一步中,我们不知道在将上一次的结果平方之后,还需不需要额外乘 x。

但如果我们从右往左看,分治的思想就十分明显了:

当我们要计算 x^n时,我们可以先递归地计算出 y=x^⌊n/2⌋ ,其中 ⌊a⌋ 表示对 a 进行下取整;

根据递归计算的结果,如果 n 为偶数,那么 x^n = y^2 ;如果 n 为奇数,那么 x^n = y^2 * x

递归的出口为 n = 0,任意数的 0 次方均为 1。

由于每次递归都会使得指数减少一半,因此递归的层数为 O(logn),算法可以在很快的时间内得到结果。

代码语言:javascript
复制
class Solution {
    public double quickPow(double x, long n){
        if(n==0){
            return 1.0;
        }
        double y=quickPow(x,n/2);
        System.out.println(y);
        if(n%2==1){
            return y*y*x;
        }else{
            return y*y;
        }
    }
    public double myPow(double x, int n) {
        long N=n;
        if(n>=0){
            return quickPow(x,N); 
        }else{
            return 1.0/quickPow(x,-N);
        }
    }
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2021/02/11 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目描述
  • 思路1:暴力破解(超时)
  • 思路2:快速幂 + 递归
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档