LeetCode 89 格雷编码

题目如下：

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

每个整数都在范围 $[0,2^n-1]$ 内, 要求：

• 第一个整数是 0
• 一个整数在序列中出现 不超过一次
• 每对 相邻 整数的二进制表示 恰好一位不同 ，且
• 第一个 和 最后一个 整数的二进制表示 恰好一位不同

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

说实话我一开始想的简单了，直接暴力搜索，最后发现不行，只能 refer 一下官方题解了

方法一

我们可以用归纳法，从 $n-1$推到$n$，设序列 $G_n$ 为$n$ 位的格雷码序列, 我们可以从 $G_{n-1}$ 推到 $G_n$。

首先把 $G_{n-1}$ 中所有元素的$n-1$位设为 1，得到$G_{n-1}^T$, 然后拼接 $G_{n-1}$和$G_{n-1}^T$就得到了我们想要的结果。

为什么呢？其实很简单，$G_{n-1}^T$ 中每个数字都与$G_{n-1}$ 有且仅有一位不同, 且 $G_{n-1}$是$[0,2^{n-1}]$的一个排列，$G_{n-1}^T$则是$[2^{n-1},2^n-1]$上的排列。 二者组合后自然就得到了$[0,2^n-1]$上的排列，且依次穿插后二进制位恰有一位不同。

方法二

这个方法是纯粹的找规律，如下：