Leetcode:50.Pow(x, n)
实现 pow(x, n) ，即计算 x 的 n 次幂函数。
示例 1:
输入: 2.00000, 10 输出: 1024.00000
示例 2:
输入: 2.10000, 3 输出: 9.26100
示例 3:
输入: 2.00000, -2 输出: 0.25000 解释: 2-2 = 1/22 = 1/4 = 0.25
解题思路：
递归。double的指数范围[-1024,1024]。递归一定是单层的，不然很慢。
1. 当n为奇数时，return x*pow(x,(n-1)/2)；
2. 当n为偶数时，return pow(x,n/2)；
注意负数的奇数对2求余是-1。如果想避开负数这个点，可以return 1/pow(x,-n)；经测试，4ms的代码在此刻运行中也是8ms,时间复杂度为log(n)。
| class Solution { public: double myPow(double x, int n) { if (x == 0) return 0; if (x == 1) return 1; if (x == -1) return (n % 2 == 0 ? 1 : -1); if (n == 0) return 1; if (n == 1) { mp[n] == x; return x; } if (n == -1) { mp[n] == 1 / x; return 1 / x; } double d; if (visit[n / 2] == true) d = mp[n / 2]; else { d = myPow(x, n / 2); visit[n / 2] = true; mp[n / 2] = d; } double res = d*d; int sgn = n % 2; if (sgn != 0) { if (n > 0) res *= x; if (n < 0) res *= (1 / x); } return res; } private: unordered_map<int, double> mp; unordered_map<int, bool> visit; }; |