Leecode-89.格雷编码
题目:
格雷编码是一个二进制数字系统,在该系统中,两个连续的数值仅有一个位数的差异。
给定一个代表编码总位数的非负整数 n,打印其格雷编码序列。格雷编码序列必须以 0 开头。
示例 1:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| 输入: 2 输出: [0,1,3,2] 解释: 00 - 0 01 - 1 11 - 3 10 - 2
对于给定的 n,其格雷编码序列并不唯一。 例如,[0,2,3,1] 也是一个有效的格雷编码序列。
00 - 0 10 - 2 11 - 3 01 - 1
|
示例 2:
1 2 3 4 5
| 输入: 0 输出: [0] 解释: 我们定义格雷编码序列必须以 0 开头。 给定编码总位数为 n 的格雷编码序列,其长度为 2n。当 n = 0 时,长度为 20 = 1。 因此,当 n = 0 时,其格雷编码序列为 [0]。
|
思路:
这道题高中数学书看过,
000 -> 001 -> 011 -> 010 -> 110 -> 100 -> 101 -> 111
数学上的定义是这样的:
1 2 3 4 5 6 7 8
| if n equals to 3, binary num gray code 0=000 000 = 000 ^ (000>>1) 1=001 001 = 001 ^ (001>>1) 2=010 011 = 010 ^ (010>>1) 3=011 010 = 011 ^ (011>>1) ... 7=111 100 = 111 ^ (111>>1)
|
所以可以简单的实现;
1 2 3 4 5 6 7 8 9
| class Solution { public List<Integer> grayCode(int n) { List<Integer> res = new LinkedList(); for(int i = 0; i < Math.pow(2, n); i++) { res.add(i^i>>1); } return res; } }
|
完);