089. 格雷编码

作者：沉默王二
发布时间：2023-10-12T18:57:58.067+0800

本题解同时收录在星球专栏《二哥的 LeetCode 刷题笔记》中，专栏托管在语雀平台上（更方便你沉浸式阅读和做笔记），访问地址和密码：https://t.zsxq.com/6iuzn6I

题意

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

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

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

难度

中等

示例

示例 1：

输入：n = 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

分析

首先，我们需要先来搞清楚什么是格雷编码。来看维基百科的定义。

格雷码（Gray code）是由贝尔实验室的 Frank Gray 在 1940 年提出，用于在 PCM（脉冲编码调变）方法传送讯号时防止出错，并于 1953 年三月十七日取得美国专利。格雷码是一个数列集合，相邻两数间只有一个位元改变，为无权数码，且格雷码的顺序不是唯一的。

再来看一个通俗的解释。数字 0 ～ 7 的编码比较如下，分别是十进制、格雷码和二进制。

0     000    000

2 011 0103 010 0114 110 1005 111 1016 101 1107 100 111

0 和 1 的格雷码和二进制是完全相同的，但从 2 开始，就有所不同。

格雷码每次只会改变一位，而且相邻的两个数的二进制只有一位不同。比如说

从 000 到 001 只改变了最后一位；- 从 001 到 011 只改变了第二位；
从 011 到 010 也只改变了一位，依次类推。

根据以上规律，我们来推理一下题目示例中当 n = 2 时，为什么会输出 [0,1,3,2]，或者 [0,2,3,1]。

记住这个定义：两个连续的数值在二进制表示中只有一个位上有所不同。只要满足这个定义，那么不同的序列都可以认为是有效的格雷编码。

n 位的格雷码可以通过以下方法构造。我们从全 0 格雷码开始，按照下面策略：

翻转最低位（Least Significant Bit, LSB，是二进制数字中的最右边的位）得到下一个格雷码，（例如）；
把最右边的 1 的左边的位翻转得到下一个格雷码，（例如）；
交替按照上述策略生成次，可得到 n 位的格雷码序列。

这是手动构造的方式，再介绍一种镜像的方式。

n 位的格雷码可以从 n-1 位的格雷码以上下镜射后加上新位的方式快速得到，我们通过 LaTeX 来表示下：

我们再通过画图的方式来表示下，分别对应n=0,1,2,3的情况。

我们不难发现，在n>=1（第二列开始）的情况下，红色部分和蓝色部分是对称的，相差的只有首位的0和1。

我们来简单模拟下（上面提到的镜像法）。

第 0 列为最初始的情况：0，也就是当 n = 0 时，0 位的格雷码为 0（题目其实提示了 1 <= n <= 16）。

第 1 列为 n = 1 时的情况：也就是要输出 1 位的格雷码，我们可以直接得出来：0,1。也就是二进制的 00 和 01，符合相邻的两个数的二进制只有一位不同的特征。

从第二列（n = 2）开始，我们反向遍历上一列（由 [0,1] 到 [1,0]），并添加1，得到：11,10，把它并入上一列（加 0）的后面，即00,01,11,10。

第三列，也只需要反向遍历第二列（由[00,01,11,10] 到 [10,11,01,00]），并添加1，则可以得到：110,111,101,100，将其并入上一列（加 0）的后面，即000,001,011,010,110,111,101,100。

OK，来看最后的题解。

当然可以。以下是给定的代码，附加了详细的注释和模拟说明。

class Solution {

        // 初始化结果集合，并添加起始格雷码0        List ret = new ArrayList<>();        ret.add(0);
        // 循环处理每一位        for (int i = 1; i <= n; i++) {            // 获取当前已生成的格雷码的数量            int siz = ret.size();
            // 逆序遍历当前已有的格雷码            for (int j = siz - 1; j >= 0; j--) {                // 对每一个格雷码，加上当前位（i位）的1，然后添加到结果集中                // 这是通过位操作实现的，即将第i位设置为1                ret.add(ret.get(j) | (1 << (i - 1)));            }        }
        return ret;    }}

模拟说明：

假设 n = 2，那么按照我们前面的讨论，格雷码应该是 [0,1,3,2]。下面我们看看这个算法是如何工作的：

初始化 ret = [0]。
当 i = 1（也就是第 1 位）：
siz = 1，因为 ret 中只有 1 个元素。
对 ret 中的数字 0，我们添加 1 位 1，得到 1。
更新后的 ret = [0,1]。
当 i = 2（也就是第 2 位）：
siz = 2，因为 ret 中有 2 个元素。
对 ret 中的数字 1，我们添加 1 位 1，得到 3。
对 ret 中的数字 0，我们添加 1 位 1，得到 2。
更新后的 ret = [0,1,3,2]。

所以，最终得到的格雷码序列为 [0,1,3,2]。

我们来分析一下这个表达式 ret.add (ret.get (j) | (1 << (i - 1)))。

①. (1 << (i - 1))

这部分是位运算。它的意思是将数字1左移(i-1)位。

例如：

当i=1时，1 << 0即将1左移0位，结果为0001（二进制），即十进制中的1。
当i=2时，1 << 1即将1左移1位，结果为0010（二进制），即十进制中的2。
当i=3时，1 << 2即将1左移2位，结果为0100（二进制），即十进制中的4。

简而言之，这个操作的目的是生成一个数，其中只有第i位是1，其他位都是0。

②. ret.get (j) | (1 << (i - 1))

这是一个“按位或”运算。它的作用是合并两个二进制数。对于每一位，如果任何一个数的该位是1，结果的该位也是1。

例如，考虑二进制数0010和0001。它们的按位或结果是0011。

这个操作的目的是将已有的某个格雷码（即ret.get (j)）与只有第i位是1的数进行按位或运算。这会在已有的格雷码上添加一个新的1位。

当我们执行ret.add (ret.get (j) | (1 << (i - 1)));，我们实际上是这样做的：

为数字1的第i位生成一个掩码。
使用该掩码更新我们的当前格雷码，从而在其第i位添加一个1。
将更新后的格雷码添加到ret列表中。

来看一下题解效率。

优化

可能位运算比较难理解，我们可以换成数学运算来完成。

class Solution {

        List ret = new ArrayList<>();        ret.add(0);
        for (int i = 1; i <= n; i++) {            // 获取当前已生成的格雷码的数量            int siz = ret.size();
            // 计算当前的增量，这相当于之前的 (1 << (i-1))            int increment = (int) Math.pow(2, i - 1);                        // 逆序遍历当前已有的格雷码            for (int j = siz - 1; j >= 0; j--) {                // 添加新的值，这相当于之前的按位或操作                ret.add(ret.get(j) + increment);            }        }                return ret;    }}

当 n = 3 时，我们来推导一下整个题解的过程。

我们首先初始化一个列表 ret 并添加起始的格雷码 0，即：

ret = [0]

①、当 i = 1（第一次迭代）：

我们要在格雷码序列中添加新的数字，使得总共有两位。

计算增量：increment = (int) Math.pow (2, i - 1) = Math.pow (2, 0) = 1
逆序遍历：现在的 ret = [0]。对于这个数字0，我们加上增量1得到1。
更新列表：ret = [0, 1]

③、当 i = 2（第二次迭代）：

我们要在已有的格雷码序列上添加更多的数字，使其包含四个数字。

计算增量：increment = (int) Math.pow (2, i - 1) = Math.pow (2, 1) = 2
逆序遍历：现在的 ret = [0, 1]。首先，对于数字1，我们加上增量2得到3。然后，对于数字0，我们加上增量2得到2。
更新列表：ret = [0, 1, 3, 2]

④、当 i = 3（第三次迭代）：

我们要在已有的格雷码序列上添加更多的数字，使其包含八个数字。

计算增量：increment = (int) Math.pow (2, i - 1) = Math.pow (2, 2) = 4
逆序遍历：现在的 ret = [0, 1, 3, 2]。首先，对于数字2，我们加上增量4得到6。然后，对于数字3，我们加上增量4得到7。然后，对于数字1，我们加上增量4得到5。然后，对于数字0，我们加上增量4得到4。
更新列表：ret = [0, 1, 3, 2, 6, 7, 5, 4]

总结

面对大多数难以利用数学公式解决的题目，我们可以将较小的情况手写并排列出来，从中发现一些简单的规律，然后根据规律快速写出题解。

力扣链接：https://leetcode.cn/problems/gray-code/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 3700 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

题意

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

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

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

难度

中等

示例

示例 1：

输入：n = 2

示例 2：

输入：n = 1

分析

首先，我们需要先来搞清楚什么是格雷编码。来看维基百科的定义。

再来看一个通俗的解释。数字 0 ～ 7 的编码比较如下，分别是十进制、格雷码和二进制。

0     000    000

2 011 0103 010 0114 110 1005 111 1016 101 1107 100 111

0 和 1 的格雷码和二进制是完全相同的，但从 2 开始，就有所不同。

格雷码每次只会改变一位，而且相邻的两个数的二进制只有一位不同。比如说

从 000 到 001 只改变了最后一位；- 从 001 到 011 只改变了第二位；
从 011 到 010 也只改变了一位，依次类推。

根据以上规律，我们来推理一下题目示例中当 n = 2 时，为什么会输出 [0,1,3,2]，或者 [0,2,3,1]。

记住这个定义：两个连续的数值在二进制表示中只有一个位上有所不同。只要满足这个定义，那么不同的序列都可以认为是有效的格雷编码。

n 位的格雷码可以通过以下方法构造。我们从全 0 格雷码开始，按照下面策略：

翻转最低位（Least Significant Bit, LSB，是二进制数字中的最右边的位）得到下一个格雷码，（例如）；
把最右边的 1 的左边的位翻转得到下一个格雷码，（例如）；
交替按照上述策略生成次，可得到 n 位的格雷码序列。

这是手动构造的方式，再介绍一种镜像的方式。

n 位的格雷码可以从 n-1 位的格雷码以上下镜射后加上新位的方式快速得到，我们通过 LaTeX 来表示下：

我们再通过画图的方式来表示下，分别对应n=0,1,2,3的情况。

我们不难发现，在n>=1（第二列开始）的情况下，红色部分和蓝色部分是对称的，相差的只有首位的0和1。

我们来简单模拟下（上面提到的镜像法）。

第 0 列为最初始的情况：0，也就是当 n = 0 时，0 位的格雷码为 0（题目其实提示了 1 <= n <= 16）。

从第二列（n = 2）开始，我们反向遍历上一列（由 [0,1] 到 [1,0]），并添加1，得到：11,10，把它并入上一列（加 0）的后面，即00,01,11,10。

OK，来看最后的题解。

当然可以。以下是给定的代码，附加了详细的注释和模拟说明。

class Solution {

模拟说明：

假设 n = 2，那么按照我们前面的讨论，格雷码应该是 [0,1,3,2]。下面我们看看这个算法是如何工作的：

初始化 ret = [0]。
当 i = 1（也就是第 1 位）：
siz = 1，因为 ret 中只有 1 个元素。
对 ret 中的数字 0，我们添加 1 位 1，得到 1。
更新后的 ret = [0,1]。
当 i = 2（也就是第 2 位）：
siz = 2，因为 ret 中有 2 个元素。
对 ret 中的数字 1，我们添加 1 位 1，得到 3。
对 ret 中的数字 0，我们添加 1 位 1，得到 2。
更新后的 ret = [0,1,3,2]。

所以，最终得到的格雷码序列为 [0,1,3,2]。

我们来分析一下这个表达式 ret.add (ret.get (j) | (1 << (i - 1)))。

①. (1 << (i - 1))

这部分是位运算。它的意思是将数字1左移(i-1)位。

例如：

当i=1时，1 << 0即将1左移0位，结果为0001（二进制），即十进制中的1。
当i=2时，1 << 1即将1左移1位，结果为0010（二进制），即十进制中的2。
当i=3时，1 << 2即将1左移2位，结果为0100（二进制），即十进制中的4。

简而言之，这个操作的目的是生成一个数，其中只有第i位是1，其他位都是0。

②. ret.get (j) | (1 << (i - 1))

这是一个“按位或”运算。它的作用是合并两个二进制数。对于每一位，如果任何一个数的该位是1，结果的该位也是1。

例如，考虑二进制数0010和0001。它们的按位或结果是0011。

这个操作的目的是将已有的某个格雷码（即ret.get (j)）与只有第i位是1的数进行按位或运算。这会在已有的格雷码上添加一个新的1位。

当我们执行ret.add (ret.get (j) | (1 << (i - 1)));，我们实际上是这样做的：

为数字1的第i位生成一个掩码。
使用该掩码更新我们的当前格雷码，从而在其第i位添加一个1。
将更新后的格雷码添加到ret列表中。

来看一下题解效率。

优化

可能位运算比较难理解，我们可以换成数学运算来完成。

class Solution {

当 n = 3 时，我们来推导一下整个题解的过程。

我们首先初始化一个列表 ret 并添加起始的格雷码 0，即：

ret = [0]

①、当 i = 1（第一次迭代）：

我们要在格雷码序列中添加新的数字，使得总共有两位。

计算增量：increment = (int) Math.pow (2, i - 1) = Math.pow (2, 0) = 1
逆序遍历：现在的 ret = [0]。对于这个数字0，我们加上增量1得到1。
更新列表：ret = [0, 1]

③、当 i = 2（第二次迭代）：

我们要在已有的格雷码序列上添加更多的数字，使其包含四个数字。

计算增量：increment = (int) Math.pow (2, i - 1) = Math.pow (2, 1) = 2
逆序遍历：现在的 ret = [0, 1]。首先，对于数字1，我们加上增量2得到3。然后，对于数字0，我们加上增量2得到2。
更新列表：ret = [0, 1, 3, 2]

④、当 i = 3（第三次迭代）：

我们要在已有的格雷码序列上添加更多的数字，使其包含八个数字。

计算增量：increment = (int) Math.pow (2, i - 1) = Math.pow (2, 2) = 4
逆序遍历：现在的 ret = [0, 1, 3, 2]。首先，对于数字2，我们加上增量4得到6。然后，对于数字3，我们加上增量4得到7。然后，对于数字1，我们加上增量4得到5。然后，对于数字0，我们加上增量4得到4。
更新列表：ret = [0, 1, 3, 2, 6, 7, 5, 4]

总结

面对大多数难以利用数学公式解决的题目，我们可以将较小的情况手写并排列出来，从中发现一些简单的规律，然后根据规律快速写出题解。

力扣链接：https://leetcode.cn/problems/gray-code/

一步一个脚印

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

题意

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

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

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

难度

中等

示例

示例 1：

输入：n = 2

示例 2：

输入：n = 1

分析

首先，我们需要先来搞清楚什么是格雷编码。来看维基百科的定义。

再来看一个通俗的解释。数字 0 ～ 7 的编码比较如下，分别是十进制、格雷码和二进制。

0     000    000

2 011 0103 010 0114 110 1005 111 1016 101 1107 100 111

0 和 1 的格雷码和二进制是完全相同的，但从 2 开始，就有所不同。

格雷码每次只会改变一位，而且相邻的两个数的二进制只有一位不同。比如说

从 000 到 001 只改变了最后一位；- 从 001 到 011 只改变了第二位；
从 011 到 010 也只改变了一位，依次类推。

根据以上规律，我们来推理一下题目示例中当 n = 2 时，为什么会输出 [0,1,3,2]，或者 [0,2,3,1]。

记住这个定义：两个连续的数值在二进制表示中只有一个位上有所不同。只要满足这个定义，那么不同的序列都可以认为是有效的格雷编码。

n 位的格雷码可以通过以下方法构造。我们从全 0 格雷码开始，按照下面策略：

翻转最低位（Least Significant Bit, LSB，是二进制数字中的最右边的位）得到下一个格雷码，（例如）；
把最右边的 1 的左边的位翻转得到下一个格雷码，（例如）；
交替按照上述策略生成次，可得到 n 位的格雷码序列。

这是手动构造的方式，再介绍一种镜像的方式。

n 位的格雷码可以从 n-1 位的格雷码以上下镜射后加上新位的方式快速得到，我们通过 LaTeX 来表示下：

我们再通过画图的方式来表示下，分别对应n=0,1,2,3的情况。

我们不难发现，在n>=1（第二列开始）的情况下，红色部分和蓝色部分是对称的，相差的只有首位的0和1。

我们来简单模拟下（上面提到的镜像法）。

第 0 列为最初始的情况：0，也就是当 n = 0 时，0 位的格雷码为 0（题目其实提示了 1 <= n <= 16）。

从第二列（n = 2）开始，我们反向遍历上一列（由 [0,1] 到 [1,0]），并添加1，得到：11,10，把它并入上一列（加 0）的后面，即00,01,11,10。

OK，来看最后的题解。

当然可以。以下是给定的代码，附加了详细的注释和模拟说明。

class Solution {

模拟说明：

假设 n = 2，那么按照我们前面的讨论，格雷码应该是 [0,1,3,2]。下面我们看看这个算法是如何工作的：

初始化 ret = [0]。
当 i = 1（也就是第 1 位）：
siz = 1，因为 ret 中只有 1 个元素。
对 ret 中的数字 0，我们添加 1 位 1，得到 1。
更新后的 ret = [0,1]。
当 i = 2（也就是第 2 位）：
siz = 2，因为 ret 中有 2 个元素。
对 ret 中的数字 1，我们添加 1 位 1，得到 3。
对 ret 中的数字 0，我们添加 1 位 1，得到 2。
更新后的 ret = [0,1,3,2]。

所以，最终得到的格雷码序列为 [0,1,3,2]。

我们来分析一下这个表达式 ret.add (ret.get (j) | (1 << (i - 1)))。

①. (1 << (i - 1))

这部分是位运算。它的意思是将数字1左移(i-1)位。

例如：

当i=1时，1 << 0即将1左移0位，结果为0001（二进制），即十进制中的1。
当i=2时，1 << 1即将1左移1位，结果为0010（二进制），即十进制中的2。
当i=3时，1 << 2即将1左移2位，结果为0100（二进制），即十进制中的4。

简而言之，这个操作的目的是生成一个数，其中只有第i位是1，其他位都是0。

②. ret.get (j) | (1 << (i - 1))

这是一个“按位或”运算。它的作用是合并两个二进制数。对于每一位，如果任何一个数的该位是1，结果的该位也是1。

例如，考虑二进制数0010和0001。它们的按位或结果是0011。

这个操作的目的是将已有的某个格雷码（即ret.get (j)）与只有第i位是1的数进行按位或运算。这会在已有的格雷码上添加一个新的1位。

当我们执行ret.add (ret.get (j) | (1 << (i - 1)));，我们实际上是这样做的：

为数字1的第i位生成一个掩码。
使用该掩码更新我们的当前格雷码，从而在其第i位添加一个1。
将更新后的格雷码添加到ret列表中。

来看一下题解效率。

优化

可能位运算比较难理解，我们可以换成数学运算来完成。

class Solution {

当 n = 3 时，我们来推导一下整个题解的过程。

我们首先初始化一个列表 ret 并添加起始的格雷码 0，即：

ret = [0]

①、当 i = 1（第一次迭代）：

我们要在格雷码序列中添加新的数字，使得总共有两位。

计算增量：increment = (int) Math.pow (2, i - 1) = Math.pow (2, 0) = 1
逆序遍历：现在的 ret = [0]。对于这个数字0，我们加上增量1得到1。
更新列表：ret = [0, 1]

③、当 i = 2（第二次迭代）：

我们要在已有的格雷码序列上添加更多的数字，使其包含四个数字。

计算增量：increment = (int) Math.pow (2, i - 1) = Math.pow (2, 1) = 2
逆序遍历：现在的 ret = [0, 1]。首先，对于数字1，我们加上增量2得到3。然后，对于数字0，我们加上增量2得到2。
更新列表：ret = [0, 1, 3, 2]

④、当 i = 3（第三次迭代）：

我们要在已有的格雷码序列上添加更多的数字，使其包含八个数字。

计算增量：increment = (int) Math.pow (2, i - 1) = Math.pow (2, 2) = 4
逆序遍历：现在的 ret = [0, 1, 3, 2]。首先，对于数字2，我们加上增量4得到6。然后，对于数字3，我们加上增量4得到7。然后，对于数字1，我们加上增量4得到5。然后，对于数字0，我们加上增量4得到4。
更新列表：ret = [0, 1, 3, 2, 6, 7, 5, 4]

总结

面对大多数难以利用数学公式解决的题目，我们可以将较小的情况手写并排列出来，从中发现一些简单的规律，然后根据规律快速写出题解。

力扣链接：https://leetcode.cn/problems/gray-code/

一步一个脚印

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

            知识星球
            
    
    
        
        扫码加入星球
        查看更多优质内容
    
    https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412