LeetCode刷题实战89：格雷编码-轻识

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 格雷编码，我们先来看题面：

https://leetcode-cn.com/problems/gray-code/

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

题意

格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。

给定一个代表编码总位数的非负整数 n，打印其格雷编码序列。即使有多个不同答案，你也只需要返回其中一种。

格雷编码序列必须以 0 开头。

样例

输入: 2
输出: [0,1,3,2]
解释:
00 - 0
01 - 1
11 - 3
10 - 2

对于给定的 n，其格雷编码序列并不唯一。

例如，[0,2,3,1] 也是一个有效的格雷编码序列。

00 - 0
10 - 2
11 - 3
01 - 1

解题

https://www.cnblogs.com/techflow/p/13432414.html

题解

当然以上的问题其实也不是事，我们不确定试一次也就知道了，核心还是怎么想出解法来。

干想是没有结果的，还是要先分析搜集一些信息。首先，题目给定的n，限制了每个数能够使用的二进制位的数量。n个二进制位一共能表示的数字有

2 n " role="presentation" style=" display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border-width: 0px; border-style: initial; border-color: initial; "> 2 n 2 n

种，我们无法得知是否这么多数字都能串联起来。假设可行的话，那么这个问题其实就是这

2 n " role="presentation" style=" display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border-width: 0px; border-style: initial; border-color: initial; "> 2 n 2 n

个数如何摆放的问题。

所以问题的关键就是要寻找这样一个序列，根据我们之前解全排列以及各种排列的方法，可以联想得到，这大概率是一个搜索问题。

顺着搜索的思路继续往下，剩下的事情就容易了，我们的起始搜索点是0。题目中要求了每两个相邻的数的二进制位只相差一个，那么我们可以遍历这些二进制位，寻找0的后继节点。同样对于每一个后继节点来说，我们都可以用同样的方法寻找它的后继们。再加上gray code不能包含重复的元素，我们可以在搜索的时候加上剪枝。

这一套其实是一个经典的搜索问题的流程。

如果我们换个思路，虽然也能得到一样的解法，但是思考的过程会不太一样。怎么换思路呢，其实也简单，我们把它想象成一个图论问题。也就是说，每一个数字都是图中的一个节点。如果两个数字之间满足只相差了一个二进制位，那么说明它们之间有一条边相连。整个问题就转变成了我们从0这个点出发，找出所有连通的节点。

对于图上的遍历问题，方法就很固定了就是搜索。也就是说从这个角度思考的话，更加容易想到搜索上面了，整个思考的链路会更短。这也是为什么很多大神建模的时候喜欢从往图上考虑的原因。

这些都想明白了再来写代码真的就水到渠成了，整个核心代码真的不长：

class Solution:
    def grayCode(self, n: int) -> List[int]:
        ret = [0]
        elements = {0}
        
        def dfs(cur):
            # 遍历与cur唯一不同的二进制位
            for i in range(n):
                # 针对这一维做亦或，将0变1，1变0
                nxt = cur ^ (1 << i)
                if nxt in elements:
                    continue
                # 记录答案，继续往下遍历
                elements.add(nxt)
                ret.append(nxt)
                dfs(nxt)
        dfs(0)
        return ret