格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个二进制的差异。
给定一个非负整数 n ，表示该代码中所有二进制的总数，请找出其格雷编码顺序。一个格雷编码顺序必须以 0 开始，并覆盖所有的 2n 个整数。
对于给定的 n，其格雷编码顺序并不唯一。
当n = 2时，根据上面的定义，[0,1,3,2] 和 [0,2,3,1] 都是有效的格雷编码顺序。
在线评测地址：
https://www.lintcode.com/problem/gray-code/?utm_source=sc-tc-sz0812
样例 1:
输入: 1
输出: [0, 1]
样例 2:
输入: 2
输出: [0, 1, 3, 2]
解释:
0 - 00
1 - 01
3 - 11
2 - 10
最简单的做法是利用位运算. 在《计算机组成与设计》一书上有介绍.
一个数字对应的格雷编码的计算方式是:
将其二进制第一位(从高位数)与0异或, 得到的结果为格雷码的第一位
之后依次将原数的第i位与生成的格雷码第i-1位做异或运算, 即可得到格雷码的第i位.
public class Solution {
public ArrayList<Integer> grayCode(int n) {
ArrayList<Integer> result = new ArrayList<Integer>();
for (int i = 0; i < (1 << n); i++)
result.add(i ^ (i >> 1));
return result;
}}
////////// 递归版本
public class Solution {
public ArrayList<Integer> grayCode(int n) {
ArrayList<Integer> result = new ArrayList<Integer>();
if (n <= 1) {
for (int i = 0; i <= n; i++){
result.add(i);
}
return result;
}
result = grayCode(n - 1);
ArrayList<Integer> r1 = reverse(result);
int x = 1 << (n-1);
for (int i = 0; i < r1.size(); i++) {
r1.set(i, r1.get(i) + x);
}
result.addAll(r1);
return result;
}
public ArrayList<Integer> reverse(ArrayList<Integer> r) {
ArrayList<Integer> rev = new ArrayList<Integer>();
for (int i = r.size() - 1; i >= 0; i--) {
rev.add(r.get(i));
}
return rev;
}}
更多题解参见九章算法官网：
https://www.jiuzhang.com/solution/gray-code/?utm_source=sc-tc-sz0812
