十进制转格雷码

方法一(异或)：

公式表示： G[i] = B[i] ^ B[i+1]（G：格雷码，B：二进制码）
也就是第i位格雷码等于当前二进制位和前面更高为的异或。
那怎么实现让当前位和更高位异或呢？
第一种方法是先把所有的向左移，在把所有位同时异或。
假入我们要求10110(b)的格雷码，我们可以通过先将它向左移1位，也就是先把高位降1位，这样就可以直接通过10110 ^ 1011得到对应的格雷码。
代码实现

class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> ans = new LinkedList<>();
        int tot = 1 << n;
        for(int i = 0; i < tot; i++){
            ans.add(i ^ (i >> 1));
        }
        return ans;
    }
}

第二种是对二进制码进行按位遍历，逐个求出每一位格雷码。

方法二(递归)：

1. 1位格雷码有两个码字
2. (n+1)位格雷码中的前2n个码字等于n位格雷码的码字，按顺序书写，加前缀0
3. (n+1)位格雷码中的后2n个码字等于n位格雷码的码字，按逆序书写，加前缀1
4. n+1位格雷码的集合 = n位格雷码集合(顺序)加前缀0 + n位格雷码集合(逆序)加前缀1

可以参考：格雷码
代码实现：

class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> ans = new LinkedList<>();
        int head = 1;
        ans.add(0);
        code(ans, head, n);
        return ans;
    }
    public void code(List<Integer> ans, int head, int n){
        if(n <= 0) return;
        for(int i = ans.size() - 1; i >= 0; i--){
            ans.add(head + ans.get(i));
        }
        code(ans, head << 1, n - 1);
    }
}

方法三(递推)：

只是将递归用递推实现，和递归是一样的思路。
代码实现：

class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> ans = new LinkedList<>();
        int head = 1;
        ans.add(0);
        for(int i = 1; i <= n; i++){
            for(int j = ans.size() - 1; j >= 0; j--){
                ans.add(head + ans.get(j));
            }
            head <<= 1;
        }
        return ans;
    }
}

本文地址：https://blog.csdn.net/qq_44621577/article/details/109556312