今天是旅游回来的帅吴:)
今天分享的题目来源于 LeetCode 上的剑指 Offer 系列 面试题16 . 数值的整数次方。
实现 pow(x, n)
,即计算 x 的 n 次幂函数(即,xn)。不得使用库函数,同时不需要考虑大数问题。
示例 1:
输入:x = 2.00000, n = 10
输出:1024.00000
示例 2:
输入:x = 2.10000, n = 3
输出:9.26100
示例 3:
输入:x = 2.00000, n = -2
输出:0.25000
解释:2-2 = 1/22 = 1/4 = 0.25
提示:
我们依旧用 四步分析法 进行结构化的分析。
第一想法就是利用循环,将 n 个 x 连乘起来立马得到答案,比如 x = 2,n = 11,需要进行 11 次循环的乘法,但基于这种做法实现的代码一提交显示超时,所以我们考虑的方向就是如何缩减计算的次数。
当计算到 25 时,它的结果进行平方操作即可得到 210 ,相比较于 25 * (2 * 2 * 2 * 2 * 2)减少了 4 次运算。
面试题 16.数值的整数次方.003
面试题 16.数值的整数次方.005
即 211 = 25 * 25 * 2。
如果 n 为奇数,最终结果为 x * xn - 1
如果 n 为偶数,最终结果为 x2 * (n/2)
递归。
当 n = 0 时,返回 1。
当 n < 0 时,返回 1/ x-n
同时,Java 代码中 int32 变量的范围是 [−2147483648,2147483647],当n = -2147483648,取绝对值为 2147483648 会发生越界的情况,为避免越界提取一个 x ,把 xn 变成了 x * xn-1,即将 n 变成了 n - 1,这样取绝对值是不会越界。
面试题 16.数值的整数次方新.002
面试题 16.数值的整数次方新.003
面试题 16.数值的整数次方新.004
面试题 16.数值的整数次方新.005
面试题 16.数值的整数次方新.006
面试题 16.数值的整数次方新.007
面试题 16.数值的整数次方新.008
面试题 16.数值的整数次方新.009
面试题 16.数值的整数次方新.010
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
class Solution {
public double myPow(double x, int n) {
//当 n = 0 时,返回 1
if(n == 0){
return 1;
}else if(n < 0){
// 当 n < 0 时,返回 1/ x^-n
return 1 / (x * myPow(x, - n - 1));
}else if(n % 2 == 1){
//为避免越界,提取 x
return x * myPow(x, n - 1);
}else{
return myPow(x * x, n / 2);
}
}
}
时间复杂度为 O(logN)。
空间复杂度为 O(logN)。
以上就是本期全部内容,你学会了么?我是帅吴,一个用动画刷题的程序员,下期见!
前不久我加了一个群,里面有帅张、帅地、帅北,他们觉得我长得也挺帅的