一道被点了 1500+ 反对的算法题

今天药忘吃喽~ 2023-03-01 08:41 33阅读 0赞

点击**上方蓝字**，关注并星标，和我一起学技术。

![format_png][]

今天是**LeetCode专题**第55篇文章，我们一起来看看LeetCode中的第89题 Gray Code（灰色代码）。

这题的官方难度是**Medium**，通过率是48.9%，点赞639，反对1545。又是一道反对比点赞多得多的题目，我个人发现其实这些反对很多的题目都有一个特点，就是题意比较晦涩，出题人的意图不太容易get到。不知道是不是老外理解能力不太行，所以都给出了这么多的反对。

我们就来看看这道题的真面目吧。

## 题意 ##

题目中说gray code，灰色代码是一连串n位二进制表示的数字。这一串的数字有一个特点就是第一个数字是0，从0开始后面的每一个数字和前一个数字**只有一个二进制位**不同。

题目会给定我们一个非负整数n，要求我们生产n位的灰色代码，也就是产生这些数字。并且这些数字是以10进制存储的。

不知道大家看明白没有，我们来看一个样例。

#### 样例 ####

Input: 2
    Output: [0,1,3,2]

在上面这个例子当中，输入是2，表示这些数字是两位二进制位构成的，输出是\[0, 1, 3, 2\]。我们把0，1，3，2翻译成二进制，0是00，1是01，3是11，2是10。排列在一起的话就是00， 01， 11， 10。我们可以发现每一个数和前一个数相差的都是一个二进制位。

题目当中相关的描述就这么多，但其实有很多隐藏的信息没有给，要我们自己猜测。比如说每一个数字只能出现一次，不然的话这个序列就是无穷无尽的。另外一个隐藏信息是，这样的序列应该也不是唯一的，但是题目并没有说是否所有合法的序列都可以通过测试，还是说一定要返回字典序最小的结果。

题目比较晦涩也就算了，这些隐藏信息没有交代清楚，也难怪大家会费解。

## 题解 ##

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

干想是没有结果的，还是要先分析搜集一些信息。首先，题目给定的n，限制了每个数能够使用的二进制位的数量。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

## 总结 ##

单纯从思路以及最后的AC代码来看的话，这道题难度应该是很低的，实际上也的确如此，这题的通过率接近50%，已经是Medium难度的下界了。但是相比于做对这题而言，更加重要的是思路。以图论的思维来抽象建模是算法题当中一个非常常见的手段，这是比题目本身更加宝贵的东西。

\---

由 五分钟学算法 原班人马打造的公众号：图解面试算法，现已正式上线！
    接下来我们将会在该公众号上，为大家分享优质的算法解题思路，坚持每天一篇原创文章的输出，视频动画制作不易，感兴趣的小伙伴可以关注点赞一下哈！

[format_png]: /images/20230209/6a5b05dbaf6345b29e5437342e2a05f9.png