西安网站建设风尚,到哪里做网站,烟台城乡建设局网站,进入京东商城【问题描述】[第50题][Pow(x, n)][中等]
实现 pow(x, n) #xff0c;即计算 x 的 n 次幂函数。输入: 2.10000, 3
输出: 9.26100
示例 3:输入: 2.00000, -2
输出: 0.25000
解释: 2-2 1/22 1/4 0.25【解答思路】
1.快速幂 时间复杂度#xff1a;O(logN) 空间复杂度#x…【问题描述】[第50题][Pow(x, n)][中等]
实现 pow(x, n) 即计算 x 的 n 次幂函数。输入: 2.10000, 3
输出: 9.26100
示例 3:输入: 2.00000, -2
输出: 0.25000
解释: 2-2 1/22 1/4 0.25
【解答思路】
1.快速幂 时间复杂度O(logN) 空间复杂度O(1) Java 代码中 int32 变量 n \in [-2147483648, 2147483647]n∈[−2147483648,2147483647] 因此当 n -2147483648n−2147483648 时执行 n -nn−n 会因越界而赋值出错。解决方法是先将 nn 存入 long 变量 bb 后面用 bb 操作即可。 class Solution {public double myPow(double x, int n) {if(x 0.0f) return 0.0d;long b n;double res 1.0;if(b 0) {x 1 / x;b -b;}while(b 0) {if((b 1) 1) res * x;x * x;b 1;}return res;}
}
2. 逐次相乘
特殊
n -2147483648 结果 分情况x -1 /1 结果 本身 时间复杂度O(N) 空间复杂度O(1)
public double myPow(double x, int n) {if (x -1) {if ((n 1) ! 0) {return -1;} else {return 1;}}if (x 1.0)return 1;if (n -2147483648) {return 0;}double mul 1;if (n 0) {for (int i 0; i n; i) {mul * x;}} else {n -n;for (int i 0; i n; i) {mul * x;}mul 1 / mul;}return mul;
}
3.递归
public double powRecursion(double x, int n) {if (n 0) {return 1;}//偶数的情况if ((n 1) 0) { double temp powRecursion(x, n / 2);return temp * temp;} else { //奇数的情况double temp powRecursion(x, n / 2);return temp * temp * x;}
}public double myPow(double x, int n) {if (x -1) {if ((n 1) ! 0) {return -1;} else {return 1;}}if (x 1.0f)return 1;if (n -2147483648) {return 0;}double mul 1;if (n 0) {mul powRecursion(x, n);} else {n -n;mul powRecursion(x, n);mul 1 / mul;}return mul;
}
时间复杂度O(logN) 空间复杂度O(1)
【总结】
1.位运算 判相等异或^ 取位判奇偶与1 置位或|1
2. int所表示的范围就是 -2147483648 到 21474836472^31-1,注意 -2147483648边界的考虑
补码「按位取反末位加 1 」
3.类型默认值 4.自动转换类型 强制转换类型 转载链接https://leetcode-cn.com/problems/powx-n/solution/50-powx-n-kuai-su-mi-qing-xi-tu-jie-by-jyd/
参考链接https://leetcode-cn.com/problems/powx-n/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by–15/ 参考链接https://www.runoob.com/java/java-basic-datatypes.html
