专栏首页健程之道剑指offer 16——数值的整数次方

剑指offer 16——数值的整数次方

这道题可以利用二进制,就可以快速解决了。

原题

实现函数double Power(double base, int exponent),求base的exponent次方。不得使用库函数,同时不需要考虑大数问题。

示例 1:

输入: 2.00000, 10
输出: 1024.00000

示例 2:

输入: 2.10000, 3
输出: 9.26100

示例 3:

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

说明:

  • -100.0 < x < 100.0
  • n 是 32 位有符号整数,其数值范围是 −2^31, 2^31 − 1 。

原题url:https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/

解题

这道题,如果你是用正常计算的话,提交之后会发现报超时,因此,肯定需要寻找捷径的。

因为不能使用库函数,而且上面普通方法也是会超时的,那么问题的关键就是在如何快速计算。

而如果想快的,最好的办法就是可以利用曾经计算的结果,避免重复计算。

我一开始的想法是,比如计算 2^6 ,从数学上来说,等同于计算 4^3。但如果要用这种逻辑的话,就必须要求传入参数 n 是 2^w(其中 w 是正整数),否则计算逻辑会比较复杂。因此放弃该方案。

二进制

重点依旧是放在利用曾经计算的结果,避免重复计算上,那么理想情况也就是计算 x^n 后,之后希望直接计算 x^2n,而x^2n = x^n * x^n = x^(n + n)

从上面的讨论可以看出,计算幂,可以转换成将指数进行合理的加法拆分。所谓合理,就是后一个是前一个的 2 倍,这样的话,就自然联想到要对指数从十进制转为二进制

7 = (111) = 1 * 2^2 + 1 * 2^1 + 1 * 2^0
9 = (1001) = 1 * 2^3 + 0 * 2^2 + 0 * 2^1 + 1 * 2^0

当然,上面是从大到小累加,实际计算时肯定是从小到大进行累加的。

说到二进制,肯定少不了位运算,那么计算每一位二进制上的值,有什么快速的方法呢?

有的,利用n & 1,求出最低位的值(0或者1),然后n >> 1,右移,相当于移除最低位,不停循环,也就能计算出二进制上每一位的值了。

接下来看看代码:

class Solution {
    public double myPow(double x, int n) {
        if (x == 0) {
            return 0;
        }

        // 此处用long,是防止n是Integer.MIN_VALUE时,取反后直接就超过了Integer.MAX_VALUE
        long b = n;
        double res = 1.0;
        if(b < 0) {
            x = 1 / x;
            b = -b;
        }

        while(b > 0) {
            if ((b & 1) == 1) {
                res *= x;
            }
            // 底数扩大
            x *= x;
            // 指数右移
            b >>= 1;
        }
        return res;
    }
}

提交OK。

总结

以上就是这道题目我的解答过程了,不知道大家是否理解了。这道题利用二进制,就可以快速解决了。

本文分享自微信公众号 - 健程之道(JianJianCoder),作者:健健壮

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-05-13

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【剑指Offer】16. 数值的整数次方

    给定一个 double 类型的浮点数 base 和 int 类型的整数 exponent,求 base 的 exponent 次方。

    瑞新
  • 剑指Offer-数值的整数次方

    package Other; import java.math.BigDecimal; /** * 给定一个double类型的浮点数base和int类型的...

    武培轩
  • 剑指offer:数值的整次数方

    本来是打算次条每天更新面试题和算法刷题的,加上头条一共要三篇文章,实在更不来,而且两篇都看的人也不多,所以我就算法刷题和面试题论着更新,更新的时候多更新几道。

    帅地
  • 剑指offer--数值的整数次方

    题目描述 给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

    AI那点小事
  • 剑指offer No.12 数值的整数次方

    给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

    week
  • 剑指OFFER之数值的整数次方(九度OJ1514)

    题目描述: 给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。 输入: 输入可能包含多个测试样例。 ...

    用户1154259
  • 剑指Offer面试题:10.数值的整数次方

      在.NET Framework提供的BCL中,Math类实现了一个Pow方法,例如要求2的三次方,可以通过以下代码实现:

    Edison Zhou
  • 每天一道剑指offer-牛客网数值的整数次方

    今天的题目 每天的题目见github(看最新的日期): https://github.com/gzc426 具体的题目可以去牛客网对应专题去找。

    乔戈里
  • 【go】剑指offer:求一个数的整数次方

    基于以上的思路,其实是有bug的,假如输入的n为0或者小于0呢?因此我们需要对我们的代码进行改进。若n < 0 ,其实我们求出的是一个倒数,即-n次方的倒数。那...

    陌无崖

扫码关注云+社区

领取腾讯云代金券