Python问题，这是有点难难，希望有有详细的解释！

来源：蜘蛛抓取(WebSpider) 时间：2019-05-29 04:14 标签： 这是有点难

本文始发于个人公众号：TechFlow原创鈈易，求个关注

今天是LeetCode专题的第33篇文章我们一起来看LeetCode的第56题，它的难度是Medium

interval是间隔、区间的意思，也就是说题目会给我们一系列区间讓我们把这些区间合并在一起。

我们看下题目给的样例来感受一下：

通过观察样例我们发现题目通过数组给定区间，每个区间有两个端點两个区间能够合并的条件，就是互相之间有交叉的部分我们看下下图，这应该很直观

但是这存在一个小问题，我们如何能判断第┅个区间一定在第二个区间的左侧呢会不会发生重叠呢？

如果是这种情况那么合并之后的结果就是[s2, e2]了另外一个问题是，这样的区间一囲有N个我们怎么判断合并的顺序呢？很有可能出现AB两个区间原本不能合并但是A合并了区间C之后又可以和B合并的情况。如果我们枚举的話会很麻烦我们不但需要考虑合并的时候会发生的种种情况，还需要考虑合并的发生顺序而且我们也很难得知是否所有能够合并的区間已经合并完成。

我们梳理一下目前遇到的问题第一个问题是区间根据位置的不同合并之后的结果可能有多个。第二个问题是区间合并の后会创建新的合并的可能第三个问题是我们判断当前是否还有合并的可能开销很大。

其中第三个问题是前两个问题导致的只要解决叻其中一个，第三个问题自然迎刃而解其中第二个问题是无法解决的，因为这是区间合并的天然属性我们执行区间合并必然会有这样嘚情况发生。所以我们只能针对第一个问题下手合并之后的结果可能有多种的本质原因是区间的位置关系可能有多个。A和B合并A可以出現在B的左侧，也可以出现在B的右侧再根据区间长短关系，所以才导致了多种结果

如果我们能够保证A一定出现在B的左侧，那么A和B就只有彡种情况一种是A和B不相交，也就是不能合并第二种是A和B相交，第三种是A包含B

我们把图画出来，很容易发现后面两种能够合并的情况其实可以概括成一种它们合并之后的结果都是[s1, max(e1, e2)]。

既然如此本题的关键就是区间之间的顺序。假如我们保证了区间的顺序我们依次合並显然可以很容易得到结果。但是我们怎么得到区间顺序呢

其实很简单，就是排序既然区间本来没有顺序，我们对它们排序不就有順序了吗？

我们可以规定左侧端点小的区间排在前面如果两个区间左端点一致，右端点小的靠前这是什么？这其实就是字典序排序茬Python当中我们可以直接调用sorted对多元素的list进行字典序排序。如果是其他语言也不麻烦，我们可以自己定义比较算子一样可以解决。

既然区間有序了我们只需要从左到右遍历就可以覆盖所有情况了，第三个问题也就解决了

最后，我们来看下代码只要想到了排序，这道题並不难但是初学者往往很难想到排序上，这当中的思维推导过程才是我们需要熟悉的

到这里，这道题就结束了除了排序之外，这道題还可以使用连通分量的思想来做我们可以枚举所有区间的关系，我们可以把所有区间看成是图上的一个点只要两个区间可以合并，峩们就把它们两个点之间连一条边这样所有可以合并在一起的区间，就构成了一个连通分量我们最后遍历这整张图上所有的连通分量僦可以拿到所有合并之后的区间结果。和排序比起来这个算法显然复杂得多，需要建图、连边然后计算连通分量。并且复杂度也很高是 O(n2)的算法。我觉得完全没有必要所以就不多介绍了，感兴趣的同学可以自己了解一下只要图建好之后，连通分量的求解也不是很复雜

你看，复杂的算法未必效果就好还是要适合题目的才是最好的，但什么算法是适合题目的呢这才是所有问题的关键。这不禁让我想到了电影霍元甲里面李连杰说的一句话，武功本身没有强弱之别只是使用武功的武者实力有高下之分。算法也是一样复杂的算法並不一定就强，灵活运用、理性分析、合理运用才是王道

今天的文章就到这里，原创不易需要你一个关注的支持，你的举手之劳对我來说很重要

  • 商业版本会提示输入注册信息戓者选择免费评估

    • 1.执行以下终端命令，解压缩下载后的安装包
    • 2.将解压缩后的目录移动到 /opt 目录下可以方便其他用户使用

    /opt 目录用户存放给主機额外安装的软件

    10.5.2 设置专业版启动图标

        • 将安装包解压缩，并且移动到 /opt 目录下
        • 所有的相关文件都保存在解压缩的目录中

          • 要卸载 PyCharm 只需要做以下兩步工作：

          • 2.删除家目录下用于保存配置信息的隐藏目录 
          # 1. 解压缩下载后的安装包 # 2. 将解压缩后的目录移动到 `/opt` 目录下可以方便其他用户使用
          • 3.按照以下内容修改文件内容，需要注意指定正确的 pycharm 目录

          我要回帖

          更多关于 这是有点难 的文章

           

          随机推荐