【剑指Offer】数值的整数次方

题目描述

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
保证base和exponent不同时为0

解法1

最直接的思路,计算base的exponent次方,则将base连乘exponent次即可,时间复杂度为O(exponent)
但是要注意处理特殊情况:

  • 如果底数base等于0则直接返回0
  • 非0数的0次方等于1
  • 当指数为负数时的结果,相当于用1除以指数为正数时的结果

还有一个坑需要注意,下面的代码中使用了long y = exponent;,需要将exponent转换为long类型
是因为exponent可以等于-2147483648(int类型的最小值),如果直接进行-exponent操作,由于int类型的最大值是2147483647,则会导致越界,出现错误的结果

实现代码

public double Power(double thebase, int exponent)
{
    if(thebase == 0) return 0;
    long y = exponent;  // 避免越界
    if(y < 0){
        thebase = 1 / thebase;
        y = -y;
    }
    double ret = 1;
    for(double i = 0; i < y; i ++){
        ret *= thebase;
    }
    return ret;
}

解法2

可以根据二分的思路,利用递归每次求指数的一半的次方结果,然后再将递归的结果相乘得到完整的指数次方
由于求指数的一半,即整数除以2的结果会自动向下取整,所以需要特殊处理指数为奇数时的情况,当指数为奇数时,需要在递归结果相乘的基础上再乘以一次底数
代码中使用的位运算e >> 1相当于e / 2来计算指数的一半
代码中通过位运算(e & 1) == 1 来判断指数是奇数还是偶数(奇数的二进制表示最低位一定是1,偶数的二进制表示最低位一定是0),相当于(e % 2) == 1
使用位运算会有更快的执行效率

实现代码

public double Power2(double thebase, int exponent)
{
    if(thebase == 0) return 0;
    if(exponent == 0) return 1;
    long e = exponent;  // 避免越界
    if(exponent < 0){
        e = - e;
        thebase = 1 / thebase;
    }
    if(e == 1) return thebase;
    double ret = Power2(thebase, (int)(e >> 1));
    return (e & 1) == 1 ? thebase * ret * ret : ret * ret;
}

解法3

求解整数m的n次方,一般是mn = m * m * m .....,连乘n次,算法复杂度是O(n),这样的算法效率太低,我们可以通过减少相乘的次数来提高算法效率,即快速幂
对于n我们可以用二进制表示,以14为例,14 = 1110

\[m^{14} = m^{1110} = m^{2^{3} * 1 + 2^{2} * 1 + 2^{1} * 1 + 2^{0} * 1} = m^{2^{3} * 1} * m^{2^{2} * 1} * m^{2^{1} * 1} * m^{2^{0} * 0} \]
\[= m^{8} * m^{4} * m^{2} * m^{0} = m^{8} * m^{4} * m^{2} * 1 \]

可以发现这样的规律,指数n的二进制从低位到高位依次对应底数m的1次方,2次方,4次方,8次方...,当该二进制位是1的时候,则乘以底数对应的次方数,如果该二进制位是0,则不能乘以底数对应的次方数,即乘以1。
例如,m8对应的二进制位是1,所以最终结果中有m8
m1对应的二进制位是0,所以最终结果中只有m0,即1
使用快速幂后,原本需要的14次连乘,现在只需要4次连乘。
那么怎样得到一个整数的二进制位呢,又怎样判断该二进制位是0还是1呢
可以使用与运算和右移运算,例如对于14 = 1110

  • 和1按位与得到0,即第一个二进制位是0
  • 1110右移一位,得到0111,和1按位与得到1,即第二个二进制位是1
  • 0111右移一位,得到0011,和1按位与得到1,即第三个二进制位是1
  • 0011右移一位,得到0001,和1按位与得到1,即第四个二进制位是1
  • 0001右移一位,得到0000,等于0则,算法结束

实现代码

public double Power3(double thebase, int exponent)
{
    if(thebase == 0) return 0;
    long y = exponent;  // 避免越界
    if(y < 0){
        thebase = 1 / thebase;
        y = -y;
    }
    double ret = 1;
    while(y > 0){
        if((y & 1) == 1){
            ret *= thebase;
        }
        thebase *= thebase;
        y >>= 1;
    }
    return ret;
}

更多算法题目的完整描述,AC代码,以及解题思路可以查看GitHub仓库Algorithm

(0)

相关推荐

  • 三进制计算机(中国三进制计算机)

    最佳回答 三进制计算机理论上优于二进制计算机.但是,自然界具有三态的物质很少,三态现象也不多,所以三进制计算机目前没有发展前途,三态转换需要材料集成度和运算速度. 三进制 编辑 定义 曾经被莫斯科大学 ...

  • 【剑指Offer】链表中倒数第k个结点

    题目描述 输入一个链表,输出该链表中倒数第k个结点. 解法 基本思路是使用两个辅助指针p, q,让p先走k - 1步后,p, q两个指针再一起走 这样当p指针走到链表的末尾时,q指针刚好走到的就是倒数 ...

  • 【剑指Offer】反转链表

    题目描述 输入一个链表,反转链表后,输出新链表的表头. 解法1 可以使用三个辅助指针pHead, last,next pHead记录当前节点,last记录上一个节点,next记录下一个节点 首先使用n ...

  • 剑指 Offer 14- I. 剪绳子

    我服了.动态规划杀我. 可以说一说解决动态规划的思路(只做了两三道就总结了emmm) 1.识别动态规划问题 --重叠子问题:大问题可以分为一个个子问题.和分治策略分割的子问题不同(分治问题的子问题是相 ...

  • 剑指offer

    03 数组中重复的数字 public int findRepeatNumber(int[] nums){ //排序后的数组,重复元素必然相邻 Arrays.sort(nums); //结果集 int ...

  • 剑指 Offer 30. 包含min函数的栈

    定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中,调用 min.push 及 pop 的时间复杂度都是 O(1). 示例:MinStack minStack = ne ...

  • 剑指offer笔记面试题2----实现Singleton模式

    题目:设计一个类,我们只能生成该类的一个实例. 解法一:单线程解法 //缺点:多线程情况下,每个线程可能创建出不同的的Singleton实例 #include <iostream> usi ...

  • 每日一题 剑指offer(包含min函数的栈)

    编程是很多偏计算机.人工智能领域必须掌握的一项技能,此编程能力在学习和工作中起着重要的作用.因此小白决定开辟一个新的板块"每日一题",通过每天一道编程题目来强化和锻炼自己的编程能力 ...

  • 每日一题 剑指offer(从上往下打印二叉树)

    编程是很多偏计算机.人工智能领域必须掌握的一项技能,此编程能力在学习和工作中起着重要的作用.因此小白决定开辟一个新的板块"每日一题",通过每天一道编程题目来强化和锻炼自己的编程能力 ...

  • 每日一题 剑指offer(二叉搜索树的后序遍历序列)

    编程是很多偏计算机.人工智能领域必须掌握的一项技能,此编程能力在学习和工作中起着重要的作用.因此小白决定开辟一个新的板块"每日一题",通过每天一道编程题目来强化和锻炼自己的编程能力 ...