Yarn regex performance parsing video printing redis常用语句 jboss 建筑资质 seo计费系统 js的点击事件 jquery触发change事件 jquery绑定change事件 spark大数据处理技术 maven配置eclipse mysql汉化包 mser算法 linux撤销 python相对路径怎么写 nfc卡片 小程序下拉刷新样式 python中set的用法 python教程推荐 eclipse安装python java编程基础 java中scanner java中random java删除目录 vb编程 sql实例 图吧导航怎么样 莫愁脚本 vs2010sp1 给视频加字幕的软件 R语言初学者指南 pr怎么放大视频画面 斑驳纹理 磁芯大战 截取字符串 剑灵龙骨卷轴
当前位置: 首页 > 学习教程  > 编程语言

【LeetCode】50.Pow(x, n) (快速幂)

2020/11/4 15:07:56 文章标签:

快速幂,附带快速幂模板的链接:快速幂讲解 题目 实现 pow(x, n) ,即计算 x 的 n 次幂函数。 示例 1: 输入: 2.00000, 10 输出: 1024.00000 示例 2: 输入: 2.10000, 3 输出: 9.26100 示例 3: 输入: 2.00000, -2 输出: 0.25000 解释: 2-2 1/…

快速幂,附带快速幂模板的链接:快速幂讲解

题目

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

示例 1:

输入: 2.00000, 10
输出: 1024.00000

示例 2:

输入: 2.10000, 3
输出: 9.26100

示例 3:

输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25

说明:

  • -100.0 < x < 100.0
  • n 是 32 位有符号整数,其数值范围是 [−231, 231 − 1] 。

快速幂求解

利用快速幂的思想求解,时间复杂度O(logn)。由于考虑到n可能是负数,要分情况讨论:

  • n是负数,则 x -n = 1 / x n
  • n是正数,则直接求x n

代码

class Solution {
public:
    double myPow(double x, int n) {
        typedef long long LL ;
        double res = 1;
        //确定符号
        bool is_minus = n < 0;

        //求快速幂
       for (LL k = abs((LL)n) ; k ; k >>= 1 ){
           if (k & 1) res *= x;
           x *= x;
       }
        //负数
        if (is_minus) res = 1 / res;
        
        return res;
    }
};

本文链接: http://www.dtmao.cc/news_show_350342.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?