Leetcode 每日一题：86. 格雷编码

自己尝试

对于怎么操作比特，没思路。即使自己知道是考察 位运算符 ，但由于之前没有做过类似的题目，不知道如何下手。。。

别人的算法

格雷码定义公式

最离谱的。。。三行搞定。我猜应该是我没有格雷编码相关的知识所致。。。

class Solution {
    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;
    }
}

对称生成法

题解，题解 2

class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> ans = new ArrayList<>();

        ans.add(0); ans.add(1);
        for (int i = 2; i <= n; i++) {
            for (int j = ans.size() - 1; j >= 0; j--)
                ans.add(ans.get(j) + (1 << (i - 1)));
        }

        return ans;
    }
}

但题解 1 并没有解释为什么要逆序构造？？？

题解只是说明了 n + 1 的格雷编码可以有 n 长度的格雷编码构成

看了题解 2 ，明白了为什么需要逆序对称构造了。

由于相邻的两个数，只能有一位的差异。所以在构造 2^n^ + 1 位时，必须从 2^n^ 构造，这样才满足要求。

这时候，当构造 2^n^ + 2 位时，由于对称的特性，需要从 2^n^ - 1 位构造。这样的话，2^n^ - 1, 2^n^ , 2^n^ + 1, 2^n^ + 2 这 4 个位就都满足相互间两两都只有一个位的差异

这就是逆序对称构造的原因！！！