剑指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/probl…
解题
这道题,如果你是用正常计算的话,提交之后会发现报超时,因此,肯定需要寻找捷径的。
因为不能使用库函数,而且上面普通方法也是会超时的,那么问题的关键就是在如何快速计算。
而如果想快的,最好的办法就是可以利用曾经计算的结果,避免重复计算。
我一开始的想法是,比如计算 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) { if ((b & 1) == 1) { res *= x; } // 底数扩大 x *= x; // 指数右移 b >>= 1; } return res; } }
提交OK。
总结
以上就是这道题目我的解答过程了,不知道大家是否理解了。这道题利用二进制,就可以快速解决了。
有兴趣的话可以访问我的博客或者关注我的公众号、头条号,说不定会有意外的惊喜。
公众号:健程之道