Description:
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.
Example 1:
Input: 2Output: [0,1,3,2]Explanation:00 - 001 - 111 - 310 - 2For a given n, a gray code sequence may not be uniquely defined.For example, [0,2,3,1] is also a valid gray code sequence.00 - 010 - 211 - 301 - 1
Example 2:
Input: 0Output: [0]Explanation: We define the gray code sequence to begin with 0. A gray code sequence of n has size = 2n, which for n = 0 the size is 20 = 1. Therefore, for n = 0 the gray code sequence is [0].
Solution:
这道题的要求是让我们输出n位格雷码对应的二进制的十进制值
一看这道题描述就觉得很头疼，看了半天没看懂，一搜才知道是格雷码。格雷码似乎是机组还是什么的学过，不过早就忘了= =
格雷码据说是为了通信时避免出错而产生的，在每次+1时只变化一位。举个栗子，普通二进制在3变为4时，由011变成了100，这样需要同时将三个数都进行改变。但是在实际电路中“同时变化”是难以达到的，因此改进创造了格雷码，创造过程是这样的：
· 产生0
· 将字符串与1采取异或操作，得到1，即获得了1位格雷码的所有情况（0,1）
· 将生成的两数（二进制00,01）逆序与2（二进制10）采取异或操作，得到[3,2]（二进制11,10），即获得了2位格雷码的所有情况（0,1,3,2）
· 将生成的四数（二进制000,001,011,010）逆序与4（二进制100）采取异或操作，得到[6,7,5,4]（二进制110,111,101,100），即获得了2位格雷码的所有情况（0,1,3,2,6,7,5,4）
· 以此类推，产生n位格雷码
按照这一思路，既可生成n为格雷码啦~
顺便贴一下我开始想岔了的思路，本来想的是生成2进制再转成格雷码，实际上想复杂了，不过这个二进制转格雷码的思想获取也有可能有用？也贴这里了：
具体怎么产生的呢，还是举个栗子吧，我们产生在题目条件下输入为2时的结果：
首先产生所有的二进制，从右向左编号0~n-1，如果第i位于第i+1位相同，则对应的格雷码第i位为0，若不同，则为1（即为异或操作）；若为首位则在其前方补零，再进行异或操作。
按这样的操作，就产生了格雷码。原题的要求则为输出格雷码对应的十进制，即[0,1,3,2]，具体过程如下：
0 -> 00 -> 第0位与第1位为0，则第0位格雷码为0；第1位与补的0均为0，则第1位为0 -> 00 -> 0
1 -> 01 -> 第0位为1，第1位为0，则第0位格雷码为,1；第1位与补的0均为0，则第1位为0 -> 01 -> 1
2 -> 10 -> 第0位为0，第1位为1，则第0位格雷码为1；第1位为1，补的0为0，则第1位为1 -> 11 -> 3
3 -> 11 -> 第0位与第1位为1，则第0位格雷码为0；第1位为1，补的0为0，则第1位为1 -> 10 -> 2
按照这个思路就可以解题啦，实际上的过程就是（产生2进制数）->（按照格雷码规则将2进制数转化成格雷码）-> （将格雷码以10进制的形式输出）。
Code:
class Solution { public List grayCode(int n) { List res = new ArrayList<>(); res.add(0); for (int i = 0; i < n; i++){ int size = res.size(); for (int j = size-1; j >= 0; j--){ res.add(res.get(j) | 1 << i); } } return res; }}
提交情况: