下载APP
登录
关闭
讲堂
算法训练营
Python 进阶训练营
企业服务
极客商城
客户端下载
兑换中心
渠道合作
推荐作者
当前播放: 22 | 面试题:Pow(x,n)
00:00 / 00:00
标清
  • 标清
1.0x
  • 2.0x
  • 1.5x
  • 1.25x
  • 1.0x
  • 0.5x
网页全屏
全屏
00:00
付费课程,可试看

算法面试通关40讲

共62讲 · 62课时·约600分钟
18804
免费
01 | 合格程序员的第一步:算法...
免费
02 | 如何事半功倍地学习算法与...
免费
03 | 如何计算算法的复杂度
免费
04 | 如何通过LeetCode来进行算...
免费
05 | 理论讲解:数组&链表
06 | 面试题:反转一个单链表&...
07 | 理论讲解:堆栈&队列
08 | 面试题:判断括号字符串是...
09 | 面试题:用队列实现栈&用...
10 | 理论讲解:优先队列
11 | 面试题:返回数据流中的第...
12 | 面试题:返回滑动窗口中的...
13 | 理论讲解:哈希表
14 | 面试题:有效的字母异位词
15 | 面试题:两数之和
16 | 面试题:三数之和
17 | 理论讲解:树&二叉树&二...
18 | 面试题:验证二叉搜索树
19 | 面试题:二叉树&二叉搜索...
20 | 理论讲解:二叉树遍历
21 | 理论讲解:递归&分治
22 | 面试题:Pow(x,n)
23 | 面试题:求众数
24 | 理论讲解:贪心算法
25 | 面试题:买卖股票的最佳时...
26 | 理论讲解:广度优先搜索
27 | 理论讲解:深度优先搜索
28 | 面试题:二叉树层次遍历
29 | 面试题:二叉树的最大和最...
30 | 面试题:生成有效括号组合
31 | 理论讲解:剪枝
32 | 面试题:N皇后问题
33 | 面试题:数独问题
34 | 理论讲解:二分查找
35 | 面试题:实现一个求解平方...
36 | 理论讲解:字典树
37 | 面试题:实现一个字典树
38 | 面试题:二维网格中的单词...
39 | 理论讲解:位运算
40 | 面试题:统计位1的个数
41 | 面试题:2的幂次方问题&...
42 | 面试题:N皇后问题的另一...
43 | 理论理解:动态规划(上)
44 | 理论理解:动态规划(下)
45 | 面试题:爬楼梯
46 | 面试题:三角形的最小路径...
47 | 面试题:乘积最大子序列
48 | 面试题:股票买卖系列
49 | 面试题:最长上升子序列
50 | 面试题:零钱兑换
51 | 面试题:编辑距离
52 | 理论讲解:并查集
53 | 面试题:岛屿的个数&朋友...
54 | 面试题:岛屿的个数&朋友...
55 | 理论讲解: LRU Cache
56 | 面试题:设计和实现一个LR...
57 | 理论讲解:布隆过滤器
58 | 课程重点回顾
59 | FAQ答疑&面试中切题四件...
60 | 回到起点:斐波拉契数列
61 | 白板实战番外篇:斐波拉契...
62 | 最后的一些经验分享
本节摘要

说明

关于第一种解法,直接调用库函数的话,由于库函数的内部实现是 O(log n) 的复杂度,所以严格来讲,第一种解法的复杂度是 O(log n) 。

课件下载地址

https://github.com/geektime-geekbang/algorithm-1

Pow(x,n)

展开

精选留言(18)

  • 2018-11-01
    Java在做正负值转换的时候要注意溢出,MIN_VALUE 直接转为正就溢出了。还有偶数的时候最好还是单独乘以X,用n-1转为偶数就不能保证logN的时间复杂度了,实际测试时间几乎翻倍
    7
  • 2018-11-23
    add , mov, jump
    2
  • 2018-10-30
    非递归的解法视频只是在念代码,建议加点解释
    2
  • 2019-05-19
    循环的思路是 x^n 等价于 (x * x) ^ (n/2) 【如果n除以2余1就得在后面乘以一个x补上】, 继续等价于 (x^2 * x^2) ^ (n/4) 【如果n除4余1再乘以一个x^2补上】,用纯文字描述就是随着n不断地除以2减小,x不断地平方来扩大,直到n为1结束,这个时候的x就是最后的结果了,但是每次循环都要对n为奇数的情况做一个填补。因为x是以不断平方自己的方式来到达最后的终点,所以复杂度是logN
    不考虑边界情况和复数的java代码如下
            double result = 1.0d;
            while(n > 0) {
                if((n & 1) == 1) {
                    result = result * x;
                }
                x = x*x;
                n = n/2;
            }
            return result;
    展开
    1
  • 2019-02-20
    老师,你的第一种解决方案递归的结束条件没有判断,导致出现死循环。

    作者回复: Sorry for the bug.

    1
  • 2018-12-24
    按老师的递归算法直接扑街了!java的直接上代码,处理(0.00001,2147483647)直接提示超时
        public double myPow(double x, int n) {
            if (n == 0) return 1;
            if (n < 0){
                return 1/myPow(x,-n);
            }
            if (n % 2 ==0){
                return myPow(x,n/2)*myPow(x,n/2);
            }else{
                if (n % 2 !=0) return x*myPow(x,n/2)*myPow(x,n/2);
            }

            return 0;
        }
    展开
    1
    1
  • 2018-11-07
    @包包 n&1这个地方不是判断奇偶的吧,我理解的是判断n的二进制数此位是否是1,如果是1的话,pow才能乘以x。比如n为10,二进制为1010,其实结果就是X的8次方乘以X的2次方,两个零的位置是不需要处理pow值,只需要将x *= x计算出就行(下一位代表的值)。

    作者回复: Yes and no. 你说的有道理。不过也需要指出判断二进制位最后位0或1,也就是判断它的奇偶性。

    1
  • 2018-11-02
    老师第二种算法 n&1 那里太简单带过了啦,后面看discussion看了很久才明白,原来还是用来判断奇偶的。。。
    1
  • 2019-09-26
    反复平方的办法(没对溢出做处理)    
    public static int pow(int a,int b) {
            int ret = 1;
            int base = a;
         while (b != 0) {
         if ((b & 1) != 0)
         ret *= base;
         base *= base;
         b >>= 1;
         }
         return ret;
        }
    展开
  • 2019-07-18
    没看懂 mark下
  • 2019-06-18
    function myPow(x, n){
        if(n === 0){
            return 1
        }

        if(n < 0){
            return 1 / myPow(x, -n)
        }

        if(n % 2){
            return x * myPow(x, n-1)
        }

        return x*x * myPow(x, n - 2) // 这一步视频里面应该不对吧?
    }
    展开
  • 2019-04-30
    按照递归来写的,结果报栈溢出。修改下方法,基本逻辑都没变,就没有栈溢出了,求答案。
    public static void main(String[] args) {
            double x = 2;
            int n = -2147483648;
            System.out.println(myPow(x,n));
        }

    public static double myPow(double x, int n) {
            if(x == 0.0 || x == 1.0) {
                return x;
            }
            
            if(n==0) {
                return 1;
            }
            
            if(n<0) {
                x = 1/x;
                n = -n;
            }
            
            return pow(x,n);
        }
        
        public static double pow(double x, int n) {
            if(n == 0) {
                return 1;
            }
            if(n == 1) {
                return x;
            }
            
            if(n%2 == 0) {
                double y = pow(x, n/2);
                return y * y;
            }
            else{
                double y = pow(x, (n-1)/2);
                return y * y * x;
            }
        }

    修改后
    public static void main(String[] args) {
            double x = 2;
            int n = -2147483648;
            System.out.println(myPow2(x,n));
        }
    public static double myPow2(double x, int n) {
            if (n == 0) {
                return (double) 1;
            }
            
            if (n == 1) {
                return x;
            } else if (n == -1) {
                return 1 / x;
            }
            
            if ((n % 2) == 0) {
                double r = myPow(x, n / 2);
                return r * r;
            } else {
                double r = myPow(x, n / 2);
                return r * r * (n > 0 ? x : 1 / x);
            }
            
        }
    展开
  • 2019-02-14
    可能是我的理解不到位吧。感觉刚刚看完老师教的模版后,再看老师给出的题解,出入有点大。不知道老师能不能照着模版一步一步来演示一下怎么解这道题呢?这样感觉能让人更好地理解递归模版以及递归的思想。直接给出最优最简化的写法有时会感觉很迷惑。
  • 2019-02-10
    GO语言版本实现:

    func myPow(x float64, n int) float64 {
        if n < 0 {
            x = 1 / x
            n = -n
        }
        var pow float64 = 1
        for n > 0 {
            if n&1 == 1 {
                pow *= x
            }
            x *= x
            n >>= 1
        }
        return pow
    }
    展开

    作者回复: 酷!!

  • 2019-01-28
    最后一种其实是快速幂的算法,和白板上讲的都不一样,为什么不仔细的讲一讲?
  • 2019-01-28
    n&1 这个判断条件怎么理解?

    作者回复: 后面有一节讲位运算的时候里面有详细地解释,可以跳到位运算那章先看。

  • 2019-01-22
    循环的方法不好理解啊
  • 2019-01-01
    非递归的方法原来就是我们以前数学里面通过二进制算10进制方法的衍生版本呀

    例如 x 的 n 次方,按照n的二进制转成十进制的方法去 转换 x的n次方公式

    x^1010 = x^(2^3 + 2^1) 这就是那个非递归算法的公式了