leetcode：89. 格雷编码

题目

n 位格雷码序列 是一个由 [中等] 89. 格雷编码 - 图1 个整数组成的序列，其中：

  • 每个整数都在范围 [中等] 89. 格雷编码 - 图2 内（含 0 和 2n - 1）
  • 第一个整数是 0
  • 一个整数在序列中出现 不超过一次
  • 每对 相邻 整数的二进制表示 恰好一位不同 ，且
  • 第一个 和 最后一个 整数的二进制表示 恰好一位不同

给你一个整数 n ，返回任一有效的 n 位格雷码序列 。

示例：

  1. 输入：n = 2
  2. 输出：[0,1,3,2]
  3. 解释：
  4. [0,1,3,2] 的二进制表示是 [00,01,11,10] 。
  5. - 00 和 01 有一位不同
  6. - 01 和 11 有一位不同
  7. - 11 和 10 有一位不同
  8. - 10 和 00 有一位不同
  9. [0,2,3,1] 也是一个有效的格雷码序列，其二进制表示是 [00,10,11,01] 。
  10. - 00 和 10 有一位不同
  11. - 10 和 11 有一位不同
  12. - 11 和 01 有一位不同
  13. - 01 和 00 有一位不同
  1. 输入：n = 1
  2. 输出：[0,1]

解答 & 代码

镜像反射法：设 n 阶格雷码集合为 G(n)，则 n+1 阶格雷码集合 G(n+1) = G’(n) ∪ R’(n)

  1. 将 n 阶格雷码集合 G(n) 的每个元素的二进制形式的最前面都添加一个 0，得到集合 G’(n)
  • 二进制串最前面加 0 值不变，因此实际上 G’(n) = G(n)
  1. 将 n 阶格雷码集合 G(n) 的每个元素的二进制形式的最前面都添加一个 1，得到集合 T(n)，再将集合 T(n) 翻转（倒序，reverse），得到集合 R’(n)
  • 要将 n 位二进制形式最前面加 1 得到 n + 1 位的二进制编码，只需令 head = 1 << n，再将 head 和各元素相加即可
  1. 合并以上两步得到的 G’(n) 和 R’(n) 就得到 n+1 阶格雷码集合 G(n+1)

因此可以从 0 阶格雷码集合 G(0) = {0} 推导任何阶的格雷码集合 G(n)
image.png

  1. class Solution {
  2. public:
  3.     vector<int> grayCode(int n) {
  4.         vector<int> result = {0};    // 初始化为 0 阶格雷码集合 G(0)={0}
  5.         int head = 1;
  6.         for(int i = 0; i < n; ++i)
  7.         {
  8.             /* 求第 i+1 阶格雷码集合 G(i+1) = G'(i) ∪ R'(i) */
  9.             // G'(i) 是将 G(i) 每一个元素的二进制形式最前面加 0，因此元素值不变，G'(i)=G(i)
  10.             // 因此只需在 G(i) 尾部加上 R'(i) 即可得到 G(i+1)
  11.             // R'(i) 是逆序将 G(i) 每一个元素的二进制形式最前面加 1
  12.             for(int j = result.size() - 1; j >= 0; --j)
  13.             {
  14.                 // i 位二进制形式最前面加 1 就是 1<<i + num
  15.                 result.push_back(head + result[j]);
  16.             }
  17.             head <<= 1;
  18.         }
  19.         return result;                // 返回 n 阶格雷码集合 G(n)
  20.     }
  21. };

复杂度分析：

  • 时间复杂度[中等] 89. 格雷编码 - 图4：
  • 空间复杂度 O(1)：结果数组不计入

执行结果：

  1. 执行结果：通过
  3. 执行用时：4 ms, 在所有 C++ 提交中击败了 88.53% 的用户
  4. 内存消耗：11.6 MB, 在所有 C++ 提交中击败了 38.10% 的用户