Repository navigation
Expand file tree
/
Copy path_50_myPow.java
More file actions
76 lines (71 loc) · 2.03 KB
/
Copy path_50_myPow.java
File metadata and controls
76 lines (71 loc) · 2.03 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
package pp.arithmetic.leetcode;
/**
* Created by wangpeng on 2019-06-22.
* 50. Pow(x, n)
* <p>
* 实现 pow(x, n) ，即计算 x 的 n 次幂函数。
* <p>
* 示例 1:
* <p>
* 输入: 2.00000, 10
* 输出: 1024.00000
* 示例 2:
* <p>
* 输入: 2.10000, 3
* 输出: 9.26100
* 示例 3:
* <p>
* 输入: 2.00000, -2
* 输出: 0.25000
* 解释: 2-2 = 1/22 = 1/4 = 0.25
* 说明:
* <p>
* -100.0 < x < 100.0
* n 是 32 位有符号整数，其数值范围是 [−2^31, 2^31 − 1] 。
* <p>
* 来源：力扣（LeetCode）
* 链接：https://leetcode-cn.com/problems/powx-n
* 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
public class _50_myPow {
public static void main(String[] args) {
_50_myPow pow = new _50_myPow();
System.out.println(pow.myPow(2.1, 3));
System.out.println(pow.myPow(2, -2));
System.out.println(pow.myPow(0.3, -2));
System.out.println(pow.myPow(0.3, 1));
System.out.println(pow.myPow(0.4127, 0));
System.out.println(pow.myPow(0.00001, 2147483647));
}
/**
* 解析思路：
* 平方不就是n个数相乘么，n为负数的时候，先将x求倒数，再n次相乘(此方法会提交超时O(n))
* <p>
* 优化：
* 将上述循环相乘的方法根据分治思想，一分为二（只需要求一半即可，另一半是相同的，奇数再*x），不断拆分至两个数相乘，时间复杂度优化到O(LogN)
* 这个方法称为"快速幂乘法"
*
* @param x
* @param n
* @return
*/
public double myPow(double x, int n) {
if (n < 0) {
x = 1f / x;
}
n = Math.abs(n);
//分治求解
return fastPow(x, n);
}
double fastPow(double x, long n) {
if (n == 0) {
return 1.0;
}
double half = fastPow(x, n / 2);
if (n % 2 == 0) {
return half * half;
} else {
return half * half * x;
}
}
}