第六周主题：数字 之 GrayCode in LeetCode (in java)

题目：

http://oj.leetcode.com/problems/gray-code/


要求：


The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:
00 - 0
01 - 1
11 - 3
10 - 2


Note:
For a given n, a gray code sequence is not uniquely defined.

For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.

For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.




解答：

画画就出来了。为了好分析，我们看n=4的情况，那么一共有2^4=16种codes


 
 


  
0
  
0
  
0
  
0
 

  
0
  
0
  
0
  
1
 

  
0
  
0
  
1
  
1
 

  
0
  
0
  
1
  
0
 

  
0
  
1
  
1
  
0
 

  
0
  
1
  
1
  
1
 

  
0
  
1
  
0
  
1
 

  
0
  
1
  
0
  
0
 

  
1
  
1
  
0
  
0
 

  
1
  
1
  
0
  
1
 

  
1
  
1
  
1
  
1
 

  
1
  
1
  
1
  
0
 

  
1
  
0
  
1
  
0
 

  
1
  
0
  
1
  
1
 

  
1
  
0
  
0
  
1
 

  
1
  
0
  
0
  
0
 

规律：

（1）第一列对半分成up 和down 部分， up都是0，down都是1；

（2）从二列开始，在前一列子列的基础上，再对半细分成up和down部分，如果在第一列的down部分，则需要把01序列倒过来。

References:

[1] 代码在

https://github.com/RockyNiu/LeetCode/blob/master/src/leetcode/java/GrayCode.java