烟台公司做网站,网站招标建设,网络营销有什么,爱站网官网剑指 Offer#xff08;第2版#xff09;面试题 16#xff1a;数值的整数次方 剑指 Offer#xff08;第2版#xff09;面试题 16#xff1a;数值的整数次方解法1#xff1a;快速幂 - 递归写法解法2#xff1a;快速幂 - 非递归写法 剑指 Offer#xff08;第2版#xff… 剑指 Offer第2版面试题 16数值的整数次方 剑指 Offer第2版面试题 16数值的整数次方解法1快速幂 - 递归写法解法2快速幂 - 非递归写法 剑指 Offer第2版面试题 16数值的整数次方
题目来源27. 数值的整数次方
不得使用库函数同时不需要考虑大数问题。
只要输出结果与答案的绝对误差不超过 10−2 即视为正确。
注意
不会出现底数和指数同为 0 的情况当底数为0时指数一定为正底数的绝对值不超过 10指数的绝对值不超过 109。
解法1快速幂 - 递归写法
最朴素的想法就是循环一个一个往上乘不过这会超时。
需要注意的是指数为负数的情况只需要把指数取绝对值最后结果取倒数即可。
注意指数 exponent 要转换成 unsigned int 或者 long long有一个数据是 10, −2147483648int 的范围是 −2147483648 ~ 2147483647对 −2147483648 取绝对值会爆掉转成 signed int 也会爆。
算法 代码
class Solution
{
public:double Power(double base, int exponent){if (base 0)return 0.0;if (exponent 0)return quickMul(base, (long long)exponent);elsereturn quickMul(1.0 / base, abs((long long)exponent));}// 辅函数 - 快速幂double quickMul(double base, long long exponent){if (exponent 0)return 1.0;double y quickMul(base, exponent / 2);if (exponent % 2 1)return y * y * base;elsereturn y * y;}
};复杂度分析
时间复杂度O(log(exponent))。
空间复杂度O(log(exponent))。
解法2快速幂 - 非递归写法 详见 Pow(x, n) - LeetCode官方题解。
代码
class Solution
{
public:double Power(double base, int exponent){unsigned int n abs(exponent);double res 1.0;while (n){if (n 01)res * base;base * base;n 1;}if (exponent 0)res 1.0 / res;return res;}
};复杂度分析
时间复杂度O(log(exponent))。
空间复杂度O(1)。
