​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个二进制位一共能表示的数字有2n2n种，我们无法得知是否这么多数字都能串联起来。假设可行的话，那么这个问题其实就是这2n2n个数如何摆放的问题。所以问题的关键就是要寻找这样一个序列，根据我们之前解全排列以及各种排列的方法，可以联想得到，这大概率是一个搜索问题。顺着搜索的思路继续往下，剩下的事情就容易了，我们的起始搜索点是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

总结

单纯从思路以及最后的AC代码来看的话，这道题难度应该是很低的，实际上也的确如此，这题的通过率接近50%，已经是Medium难度的下届了。但是相比于做对这题而言，更加重要的是思路。以图论的思维来抽象建模是算法题当中一个非常常见的手段，这是比题目本身更加宝贵的东西。如果你读过昨天的文章的话，会发现昨天的87题，本质上也是用的一个图论建模的方法。但是从表现形式上来说，这两题真的可以说是完全不一样。建议大家能好好做做这两题，体会一下其中思维和解法的闪光点。好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力。

上期推文：

LeetCode50-80题汇总，速度收藏！
LeetCode刷题实战81：搜索旋转排序数组 II
LeetCode刷题实战82：删除排序链表中的重复元素 II
LeetCode刷题实战83：删除排序链表中的重复元素
LeetCode刷题实战84： 柱状图中最大的矩形
LeetCode刷题实战85：最大矩形
LeetCode刷题实战86：分隔链表
LeetCode刷题实战87：扰乱字符串
LeetCode刷题实战88：合并两个有序数组