FilesExpand file tree

master

/

_89_grayCode.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

71 lines (65 loc) · 1.88 KB

master

/

_89_grayCode.java

Copy path

Top

File metadata and controls

• Code
• Blame

71 lines (65 loc) · 1.88 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

package pp.arithmetic.leetcode;

import pp.arithmetic.Util;

import java.util.ArrayList;

import java.util.List;

/**

* Created by wangpeng on 2019-11-09.

* 89. 格雷编码

* <p>

* 格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。

* <p>

* 给定一个代表编码总位数的非负整数 n，打印其格雷编码序列。格雷编码序列必须以 0 开头。

* <p>

* 示例 1:

* <p>

* 输入: 2

* 输出: [0,1,3,2]

* 解释:

* 00 - 0

* 01 - 1

* 11 - 3

* 10 - 2

* <p>

* 对于给定的 n，其格雷编码序列并不唯一。

* 例如，[0,2,3,1] 也是一个有效的格雷编码序列。

* <p>

* 00 - 0

* 10 - 2

* 11 - 3

* 01 - 1

* 示例 2:

* <p>

* 输入: 0

* 输出: [0]

* 解释: 我们定义格雷编码序列必须以 0 开头。

*   给定编码总位数为 n 的格雷编码序列，其长度为 2^n。当 n = 0 时，长度为 2^0 = 1。

*   因此，当 n = 0 时，其格雷编码序列为 [0]。

* <p>

* 来源：力扣（LeetCode）

* 链接：https://leetcode-cn.com/problems/gray-code

* 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

*/

public class _89_grayCode {

public static void main(String[] args) {

_89_grayCode grayCode = new _89_grayCode();

Util.printList(grayCode.grayCode(2));

}

/**

* 解题思路：

*

* @param n

* @return

*/

public List<Integer> grayCode(int n) {

List<Integer> gray = new ArrayList<>();

gray.add(0); //初始化 n = 0 的解

for (int i = 0; i < n; i++) {

int add = 1 << i; //要加的数

//倒序遍历，并且加上一个值添加到结果中

for (int j = gray.size() - 1; j >= 0; j--) {

gray.add(gray.get(j) + add);

}

}

return gray;

}

}