FilesExpand file tree

 master

/

offer16.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

72 lines (70 loc) · 2.3 KB

 master

/

offer16.java

Copy path

Top

File metadata and controls

• Code
• Blame

72 lines (70 loc) · 2.3 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

/**

* [16] 数值的整数次方

*

* 题目: 给定一个 double 类型的浮点数 base 和 int 类型的整数 exponent. 求 base 的 exponent 次方.

*

* 思路: 1. 快幂算法: a ^ n = (a ^ (n / 2)) * (a ^ (n / 2)) if n 为偶数;

* = (a ^ ((n - 1) / 2)) * (a ^ ((n - 1) / 2)) * a if n 为奇数.

* 2. 位运算计算幂: 二进制表示 exponent ,若当前位置上的值为1, 表示当前位置有值.

* 二进制的最后一位对应的值是 base; 倒数第二位对应的是 base平方; 倒数第三位 base 平方的平方, 以此类推.

* 设结果的初始值为 res = 1, 发现对应位置上的数为 1, 就将 res 乘以对应的值.

*

*/

class Solution {

/**

* 时间复杂度: O(logn)

* 空间复杂度: O(logn)

*/

public double myPow1(double x, int n) {

if (n == 0) {

return 1;

}

if (n == 1) {

return x;

}

if (n == -1) {

return 1 / x;

}

// calculate a ^ (n / 2)) * (a ^ (n / 2).

double half = myPow1(x, n / 2);

// if n is odd number n / 2 will rest 1 or -1,

// then calculate the rest part a ^ (n % 2)).

double mod = myPow1(x, n % 2);

return half * half * mod;

}

/**

* 时间复杂度: O(m) (m 为 n 的二进制位数)

* 空间复杂度: O(1)

*/

public double myPow2(double x, int n) {

if (n == 0) {

return 1;

}

if (n == 1) {

return x;

}

if (n == -1) {

return 1 / x;

}

boolean flag = n > 0 ? true : false;

// if x is negative number.

// first calculate the value when it is positive,

// then just return 1 divide this value.

n = Math.abs(n);

// initialize res as 1.

double ret = 1;

while (n != 0) {

// from back to front, judge every position is 1 or 0.

// if it's 1, ret multiply current x.

if ((n & 1) == 1) {

ret *= x;

}

// calculate next position's x.

x *= x;

// move to next position.

n >>>= 1;

}

// set return value according to flag.

return flag ? ret : 1 / ret;

}

}