题目

• n 位格雷码序列 是一个由 2n 个整数组成的序列，其中：

• 每个整数都在范围 [0, 2n - 1] 内（含 0 和 2n - 1）
• 第一个整数是 0
• 一个整数在序列中出现 不超过一次
• 每对 相邻 整数的二进制表示 恰好一位不同 ，且
• 第一个 和 最后一个 整数的二进制表示 恰好一位不同
• 给你一个整数 n ，返回任一有效的 n 位格雷码序列 。

示例

• 示例1

输入：n = 2
输出：[0,1,3,2]
解释：

• [0,1,3,2] 的二进制表示是 [00,01,11,10] 。
• • 00 和 01 有一位不同
• • 01 和 11 有一位不同
• • 11 和 10 有一位不同
• • 10 和 00 有一位不同
• [0,2,3,1] 也是一个有效的格雷码序列，其二进制表示是 [00,10,11,01] 。
• • 00 和 10 有一位不同
• • 10 和 11 有一位不同
• • 11 和 01 有一位不同
• • 01 和 00 有一位不同

• 示例 2：

输入：n = 1
输出：[0,1]

代码

解法：

public List<Integer> grayCode(int n) {
    ArrayList<Integer> list = new ArrayList<>();
    list.add(0);
    return process(n, list);
}

private List<Integer> process(int n, ArrayList<Integer> list) {
    int size = list.size();
    if (size == 1 << n) return list;
    for (int i = size - 1; i >= 0; i--) {
        list.add(list.get(i) + size);
    }
    return process(n, list);
}

代码分析：

找规律：

• 当 n == 1 ，返回 [0,1] .
• 当 n == 2 ，返回 [0,1,3,2] .
• 当 n == 3 ，返回 [0,1,3,2,6,7,5,4] .
• 当 n == …… ，返回 [0,1,3,2,6,7,5,4,……] .

可见当 n == k，就是在 n == k - 1 的情况下增加了一些数字。并且根据题意知道，n每增加1，整数的范围会扩大一倍。（也可以观察结果得到）

• 对应每一个 n == k，由于返回结果总是 2 ^ n 个，所以我们将他的左右分开看。
• 例如，当 n == 3 ，返回 [0,1,3,2,6,7,5,4] .
• 左边： [0,1,3,2]，右边： [6,7,5,4]

你可以发现对称轴两侧，右边的值等于左边对称位置的值加当前长度的一半

• 其他优秀代码

解法：

public List<Integer> grayCode(int n) {
    /**
     关键是搞清楚格雷编码的生成过程, G(i) = i ^ (i/2);
     如 n = 3:
     G(0) = 000,
     G(1) = 1 ^ 0 = 001 ^ 000 = 001
     G(2) = 2 ^ 1 = 010 ^ 001 = 011
     G(3) = 3 ^ 1 = 011 ^ 001 = 010
     G(4) = 4 ^ 2 = 100 ^ 010 = 110
     G(5) = 5 ^ 2 = 101 ^ 010 = 111
     G(6) = 6 ^ 3 = 110 ^ 011 = 101
     G(7) = 7 ^ 3 = 111 ^ 011 = 100
     **/
    List<Integer> ret = new ArrayList<>();
    for(int i = 0; i < 1<<n; ++i)
        ret.add(i ^ i>>1);
    return ret;
}
    

代码分析：1、
2、

题目：gray-code