LeetCode 50. Pow(x, n)（二分查找）

文章目录

• • 1. 题目
  • 2. 二分查找
  • • 2.1 递归
    • 2.2 循环

1. 题目

实现 pow(x, n) ，即计算 x 的 n 次幂函数。

示例
输入: 2.00000, 10
输出: 1024.00000

示例
输入: 2.00000, -2
输出: 0.25000
解释: 2^-2 = 1/2² = 1/4 = 0.25
说明:
-100.0 < x < 100.0
n 是 32 位有符号整数，其数值范围是 [−2³¹, 2³¹ − 1] 。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/powx-n
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

《剑指Offer》同题：面试题16. 数值的整数次方…

2. 二分查找

类似题解：LeetCode 372. 超级次方（快速幂）

2.1 递归

class Solution { public:double myPow(double x, int n) {if(n == 0) return 1.0;long N = n;if(N < 0){x = 1/x;N = -N;}return POW(x, N);}double POW(double x, int N) {if(N == 0) return 1.0;double half = POW(x, N/2);if(N%2 == 0)return half*half;elsereturn half*half*x;} }; class Solution {//超时，0.00001，2147483647unordered_map<int ,double> m; public:double myPow(double x, int n) {if(n == 0)return 1.0;long N = n;if(n < 0){x = 1/x;N = -(long)n;//INT_MIN换号后溢出}return MyP(x, N);}double MyP(double x, long N) {if(N == 0)return 1.0;if(N%2 == 0){if(m.count(N))return m[N];double a = MyP(x, N/2)*MyP(x, N/2);m[N] = a;return a;}else{if(m.count(N))return m[N];double b = MyP(x, N/2)*MyP(x, N/2)*x;m[N] = b;return b;}} };

2.2 循环

class Solution { public:double myPow(double x, int n) {if(n == 0) return 1.0;long N = n;if(N < 0){x = 1/x;N = -N;}double ans=1;double product = x;for(long i = N; i; i /= 2){if(i % 2 == 1)ans *= product;product *= product;}return ans;} };

总结

以上是生活随笔为你收集整理的LeetCode 50. Pow(x, n)（二分查找）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。