LeetCode——Pow(x, n)

这篇具有很好参考价值的文章主要介绍了LeetCode——Pow(x, n)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、题目

50. Pow(x, n) - 力扣(Leetcode)

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

示例 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⁻² = 1/2² = 1/4 = 0.25

提示:

  • -100.0 < x < 100.0
  • -2³¹ <= n <= 2³¹-1
  • n 是一个整数
  • 要么 x 不为零,要么 n > 0 。
  • -10 <= x <= 10

 二、题目解读

题目要求我们实现 pow(x, n) 函数,即求解x的n次方,当n过大时,肯定是会超时的,这时我们便需要使用到快速幂。

介绍快速幂:

众所周知,如果我们要求a的n次方,最朴素的想法一定是把它们乘起来,这样的复杂度是O(n),显然太差了。

然后我们想到一种优化,如果我们能求得 2的k次方=n的话,我们只需要将a的平方相乘k次,这样的复杂度是O(log2n),但是我们很难找到这样的k。

于是我们将这一想法再一次优化,我们只要能找到 2的k1次方+2的k2次方+...=n就好了,这样的复杂度还是O(log2n)

这一想法可以通过数的二进制位运算轻易解决,比如9的二进制是1001,也就是从右往左数第i位,我们的答案就乘上a的2的i次方

于是就有了快速幂算法。

三、代码

class Solution {
    public double myPow(double x, int n) {
        return Math.pow(x,n);
    }
}

 看到一个段子😂

面试的时候遇到这个题目,

然后我思考🤔了片刻,写出了 return pow(x,n);

面试官问我,为啥这么写?

我说,这是软件工程的代码复用;不重复造轮子;

于是,面试官就要把我挂了😂;

说了一句,我们决定复用公司原来的员工(❁´◡`❁)。

 二进制快速幂:

class Solution {
    public double myPow(double x, int n) {
        boolean neg=n<0;//判断n是正数还是负数
        double ans=1;
        for(long m=Math.abs((long)n);m!=0;m>>=1){
            if(m%2==1){
                ans*=x;
                }
            x=x*x;
        }
        return neg?1/ans:ans;//负数返回ans的倒数
    }
}

二分思想递归,复杂度是对数级的。

class Solution {
    public double myPow(double x, int n) {
        if (n == 0) {
            return 1;
        }
        if (n == 1) {
            return x;
        }
        if (n == -1) {
            return 1 / x;
        }
        double half = myPow(x, n / 2);
        double rest = myPow(x, n % 2);
        return half * half * rest;

    }
}

快速幂递归

class Solution {
    public double myPow(double x, int n) {
        //x的0次方为:1
        if(n==0) return 1.0;

        //x的1次方为本身:x
        if(n==1) return x;

        //x的-1次方为本身的倒数:1/X
        if(n==-1) return 1.0/x;

        //如果n为偶数 -> 2^10 = 2^5 * 2^5 
        double temp = myPow(x,n>>1);
        double res = temp*temp;

        return res*myPow(x,n&1);
    }
}

LeetCode——Pow(x, n)

 文章来源地址https://www.toymoban.com/news/detail-491691.html

 

到了这里,关于LeetCode——Pow(x, n)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • c++中的pow函数

    目录 简介: 实例: 可能出现的错误: 负指数问题:pow 函数可以计算负指数,但它不处理负数的复数结果。如果计算负指数并且结果应该是复数,您需要使用复数库或手动处理。 2 溢出问题: 3头文件不包含: 简介: 在C++中, pow 函数用于计算一个数的指数幂(就是几次方

    2024年02月07日
    浏览(47)
  • 区块链实现之POW分析

    本代码的全部实现已在github上面同步开源,项目地址: link 工作量证明(Proof Of Work,简称POW),简单理解就是一份证明,用来确认你做过一定量的工作。监测工作的整个过程通常是极为低效的,而通过对工作的结果进行认证来证明完成了相应的工作量,则是一种非常高效的方式

    2024年02月04日
    浏览(41)
  • PoW 、PoS , DPoS 算法

    PoW 、PoS , DPoS 算法 在区块链领域,多采用 PoW 工作量证明算法、PoS 权益证明算法,以及 DPoS 代理权 益证明算法,以上三种是业界主流的共识算法,这些算法与经典分布式一致性算法不同的是 融入了经济学博弈的概念。 PoW:通常是指在给定的约束下,求解一个特定难度的数

    2024年02月02日
    浏览(36)
  • 区块链学习Day03(Pow算法)

    声明:笔记用作自己学习,本人也不太讲的清,请见谅。 生成新的区块,再返回新的块,也会包含上面的属性,前一个哈希也会变得,就是preHash:前一个节点得哈希。 代码继续跟着上一章文章,不懂得看下面 链接:区块链学习Day02(Pow算法) 结果: 省略… 4b5ffc524ced8f17059a

    2024年02月04日
    浏览(42)
  • 求数值的整数次方(模拟pow函数)

    实现函数 double Power(double base, int exponent),求base的exponent次方。 注意: 1.保证base和exponent不同时为0。 2.不得使用库函数,同时不需要考虑大数问题 3.有特殊判题,不用考虑小数点后面0的位数。 具体实现: 本方法中利用不断扩大原本的base,实现在O(logn)的时间复杂度。其中判

    2024年02月11日
    浏览(41)
  • eth入门之工作量证明 (POW)

    文档:工作量证明 (PoW) | ethereum.org 以太坊目前使用的共识协议被称为工作量证明 (PoW)。 这允许以太坊网络的节点就以太坊区块链上记录的所有信息的状态达成共识,并防止经济攻击。 接下来一年,工作量证明将被逐步淘汰,这有利于权益证明 (PoS) 的发展。 向权益证明 (Po

    2024年02月06日
    浏览(45)
  • 基于Python实现一个PoW的仿真程序

    资源下载地址:https://download.csdn.net/download/sheziqiong/86831335 资源下载地址:https://download.csdn.net/download/sheziqiong/86831335 利用 Python 实现一个 PoW 的仿真程序,模拟一定数量的节点生成区块链的状态。 设置参数包括:节点数量和每个轮次出块的成功率,测量区块链的增长速度。 设

    2024年02月08日
    浏览(37)
  • 区块链学习Day06(PoW在比特币中的实现)

    https://githun/bitcoin/bitcion bitcoin0-15.1 源码中区块头和区块定义: 用C++写的,不是GO 我们用GO模仿源码去写的, bitcoin0-15.1 源码中Pow算法实现 用挖矿算法形成新的区块 bitcoin0-15.1 源码中计算挖矿难度的实现 以上代码了解即可

    2024年01月23日
    浏览(89)
  • 学习C#必备的编程软件——pow_na的博客

    c#可有的编程软件:Visual Studio、Visual Studio Code、MonoDevelop、SharpDevelop、Rider、SlickEdit、C# Pad、Jdoodle、.NET Fiddle、Scriptcs等等。 C#是微软公司发布的一种面向对象的、运行于.NET Framework和.NET Core(完全开源,跨平台)之上的高级程序设计语言。 C#是一种安全的、稳定的、简单的、优雅

    2024年02月05日
    浏览(37)
  • GO语言实现区块链POW共识算法- -区块定义与数据串行化

    持续创作,加速成长!这是我参与「掘金日新计划 · 6 月更文挑战」的第9天,点击查看活动详情 区块链分布式系统,共识算法系统是它的灵魂,pow也就是工作量证明,证明你做过一定量的工作。(按劳分配,拼算力) 在我们实现pow之前,需要对区块链的基本架子先搭起来(相当

    2024年02月08日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包