专栏首页TechFlowLeetCode 87,因为题目晦涩而被点了1500+反对的搜索问题

LeetCode 87,因为题目晦涩而被点了1500+反对的搜索问题

今天是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难度的下界了。但是相比于做对这题而言,更加重要的是思路。以图论的思维来抽象建模是算法题当中一个非常常见的手段,这是比题目本身更加宝贵的东西。

如果你读过昨天的文章的话,会发现昨天的87题,本质上也是用的一个图论建模的方法。但是从表现形式上来说,这两题真的可以说是完全不一样。建议大家能好好做做这两题,体会一下其中思维和解法的闪光点。

本文分享自微信公众号 - TechFlow(techflow2019),作者:梁唐

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-07-19

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 博弈论——Nim取子问题,一行代码解决困扰千年的问题

    这个博弈问题非常古老,延续长度千年之久,一直到20世纪初才被哈佛大学的一个数学家找到解法,可见其思维的难度。但是这个问题本身却很有意思,推导的过程更是有趣,哪怕...

    TechFlow-承志
  • 手把手教你学Numpy【二】基本运算与切片

    上一篇文章当中曾经提到过,同样大小的数据,使用Numpy的运算速度会是我们自己写循环来计算的上百倍甚至更多。并且Numpy的API非常简单,通常只要简单几行代码...

    TechFlow-承志
  • golang——为什么有的语言要把变量类型写在后面?

    Golang当中的变量类型和C/C++比较接近,一般用的比较多的也就是int,float和字符串。Golang当中不一样的地方主要有几点,第一点是严格区分了in...

    TechFlow-承志
  • Python 类装饰器,使用小演示

    实现同样一个功能,用Java语言可能得50行,而用Python可能只需10行,可能很多读者在没有学Python前,就从用过Python的前辈那里,听说过这个,然...

    double
  • “来不及了,快上车”

    职位名称:腾讯云高级产品经理 岗位职责 : 1. 负责腾讯云云监控产品的规划、设计和运营,持续完善产品功能和体验; 2. 洞察整个监控体系和完整周期中的需求和...

    腾讯云监控团队
  • 《Vimtutor的中文版》快速学习Linux的vim命令

    注:本资源收集与网络,版权归原作者所有。 下载地址 ---- = 欢 迎 阅 读 《 V I M 教 程 》 —— 版本 1.5 = vim 是一个具有很多命令...

    张戈
  • 让VIM支持Python2 by update-alternatives

    前言  Ubuntu 16+中$ sudo apt install vim所安装的vim只支持Python3,但很多插件如YCM和powerline均需要Pyt...

    ^_^肥仔John
  • 【干货】Elasticsearch索引性能优化 (2)

    本文翻译自QBox官方博客的“Elasticsearch索引性能优化”系列文章中的第二篇,版权归原作者所有。该系列文章共有三篇,其中第一篇已有同行翻译,参考链接...

    杨振涛
  • 【干货】Elasticsearch索引性能优化 (2)

    本文翻译自QBox官方博客的“Elasticsearch索引性能优化”系列文章中的第二篇,版权归原作者所有。该系列文章共有三篇,其中第一篇已有同行翻译,参考链接...

    杨振涛
  • Outlook点×不退出

    林万程

扫码关注云+社区

领取腾讯云代金券