文章目录

• 89. 格雷编码：
• • 样例 1：
  • 样例 2：
  • 提示：
  • 分析：
  • 题解：
  • • rust：
    • go：
    • c++：
    • python：
    • java：

      ---

      89. 格雷编码：

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

      • 每个整数都在范围 [0, 2ⁿ - 1] 内（含 0 和 2ⁿ - 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

          ---

          分析：

          • 面对这道算法题目，二当家的再次陷入了沉思。
          • 先看看什么是格雷码：

            典型的二进制格雷码（Binary Gray Code）简称格雷码，因1953年公开的弗兰克·格雷（Frank Gray，18870913-19690523）专利“Pulse Code Communication”而得名，当初是为了通信，现在则常用于模拟－数字转换和位置－数字转换中。法国电讯工程师波特（Jean-Maurice-Émile Baudot，18450911-19030328）在1880年曾用过的波特码相当于它的一种变形。1941年George Stibitz设计的一种8元二进制机械计数器正好符合格雷码计数器的计数规律。

            在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同，则称这种编码为格雷码（Gray Code），另外由于最大数与最小数之间也仅一位数不同，即“首尾相连”，因此又称循环码或反射码。

            在数字系统中，常要求代码按一定顺序变化。例如，按自然数递增计数，若采用8421码，则数0111变到1000时四位均要变化，而在实际电路中，4位的变化不可能绝对同时发生，则计数中可能出现短暂的其它代码（1100、1111等）。在特定情况下可能导致电路状态错误或输入错误。使用格雷码可以避免这种错误。格雷码有多种编码形式。

            格雷码（Gray Code）曾用过Grey Code、葛莱码、格莱码、戈莱码、循环码、反射二进制码、最小差错码等名字，它们有的不对，有的易与其它名称混淆，建议不要再使用这些曾用名。

            • 重点是相邻的码只能有一位不同。
            • 这题我姑且说它是经验题或者是脑筋急转弯吧，模拟就可以了。
            • 前人根据规律给出了公式 g_i​ = i ^ (i / 2)，这样可以轻松保证相邻两个码只有一位不同。

              ---

              题解：

              rust：

              impl Solution {
                  pub fn gray_code(n: i32) -> Vec {
                      (0..1 << n).map(|i| {
                          (i >> 1) ^ i
                      }).collect()
                  }
              }
              

              ---

              go：

              func grayCode(n int) []int {
                  ans := make([]int, 1<
              		ans[i] = (i >> 1) ^ i
              	}
              	return ans
              }
              

              ---

              c++：

              class Solution {
              public:
                  vector grayCode(int n) {
                      vector ans(1 << n);
                      for (int i = 0; i < ans.size(); ++i) {
                          ans[i] = (i >> 1) ^ i;
                      }
                      return ans;
                  }
              };
              

              ---

              python：

              class Solution:
                  def grayCode(self, n: int) -> List[int]:
                      ans = [0] * (1 << n)
                      for i in range(1 << n):
                          ans[i] = (i >> 1) ^ i
                      return ans
              

              ---

              java：

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

              ---

              非常感谢你阅读本文~

              欢迎【点赞】【收藏】【评论】三连走一波~

              放弃不难，但坚持一定很酷~

              希望我们大家都能每天进步一点点~

              本文由 二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~

              ---