【每日一题】89. 格雷编码

文章目录

• • 题目
  • 解题思路
  • 代码（C++）
  • • 规律+栈
    • 公式
    • 其他
  • 总结

---

题目

题目链接：89. 格雷编码

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]

提示：

• 1 <= n <= 16

解题思路

格雷码应该有不少人都知道吧，学过数电的应该感到很亲切吧。

不知道也没关系，做完这题你就知道了。

格雷码的特点题目已经说的很清楚了。

👉栈+规律

这种思路是我从洛谷里的题解看到的。

用例子看吧

n = 2

//二进制表示：
0  0
1  0
1  1
0  1

n = 3

//二进制表示：
0  0    0
1  0    0
1  1    0
0  1    0
    
0  1    1
1  1    1
1  0    1
0  0    1

注意 n = 3 的二进制结果的左上方是和 n = 2 一样的，而且下方还是对称的只是右边的一行上一半是 0 ，下一半是 1 。

这就很直接了， n = 3 的结果是 n = 2 的结果向下方对称，并且整体左移，下面一半再加一。

可以看看 n = 1 和 n = 2 也是这样的，这也是规律所在。

n 每加一，都是前一个向下对称，整体左移，对称的一半再加一。

这里对于放入下面对称的值可以用栈的先进后出解决，这样就没有难度了。

👉公式

这么有规律又伟大的发现一定和公式脱不了关系，所以格雷码的公式是：G(i) = B(i) ^ B(i + 1)。

中间的符号是异或（位运算。

两个二进制值，相同取0，不同取1）。

把当前的值和当前的值乘以2后的值取异或即可。

可以直接看代码，因为我不可能把公式给你推一遍，背下来就好了。

还有其他的方法也都大同小异了，都离不开异或，要是记其他的方法还不如记公式。

代码还是贴一个吧。

代码（C++） 规律+栈

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> nums(1 << n);
        nums[0] = 0, nums[1] = 1;
        if (n == 1)
            return nums;
        for (int i = 2; i <= n; ++ i) {
            int m = 1 << i, j;
            stack<int> stack;
            for (j = 0; j < m / 2; ++ j) {
                stack.push(nums[j]);
                nums[j] *= 2;
            }
            for (; j < m; ++ j) {
                int t = stack.top();
                stack.pop();
                nums[j] = t * 2 + 1;
            }
        }
        return nums;
    }
};

公式

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> nums;
        for (int i = 0; i < (1 << n); ++ i) {
            int j = i >> 1;
            nums.push_back(i ^ j);
        }
        return nums;
    }
};

其他

class Solution {
public:
    vector<int> num;
    vector<bool> f;
    vector<int> grayCode(int n) {
        f.resize(1 << n);
        dfs(0, n);
        return num;
    }

    bool dfs(int m, int n) {
        if (num.size() == (1 << n))
            return true;
        num.push_back(m);
        f[m] = true;
        for (int i = 0; i < n; ++i) {
            int next = m ^ (1 << i);
            if (!f[next] && dfs(next, n))
                return true;
        }
        f[m] = false;
        return false;
    }
};

总结

格雷码把它弄明白了就不会觉得难了，公式就一个。

如果不想记公式可以看看方法一的规律，自己推一遍就能记住了。

官方给的两种方法和我的也都差不多，多看看，写几遍就会了。