LeetCode#891 子序列宽度之和

原题

给定一个整数数组 ,考虑 的所有非空子序列。

对于任意序列 S ,设 S 的宽度是 S 的最大元素和最小元素的差。

返回 A 的所有子序列的宽度之和。

由于答案可能非常大,请返回答案模 10^9+7

示例:

这是第98场周赛上的最后一题,是比较难的。

代码模板:

思路

题目要求一个数组的所有子数组的最大最小值的差之和。

对 Python ,有内建的 函数用于求可迭代对象的最大元素。于是问题就只剩下如何获取 的所有子集,得到 的所有子集,然后将所有子集的“宽度”相加、 就行了。

对于求一个 的全部子集,有两种途径:

Python 标准库给出了现成的函数供调用:。

本题要用到 实际上是初始化了一个 对象,该对象是一个迭代器,示例如下:

这个迭代器的元素是 中两元素组合的所有情形组成的 。、

用递归或迭代等方法自己实现求得 子集的函数。

实现(思路1)

首先我们要写一个 函数来求一个整数数组的宽度(题中所述列表中最大最小元素之差):

如上,7、8 两行即可实现,很简洁。

随后利用 对 进行迭代。由于 是指定元素个数的,我们使用两个 for 循环,第一个循环控制子集的长度,例如 ,则子集长度可能为 ;第二个循环就遍历特定长度的子集,比如 中写的 将遍历 这三个 。

代码:

测试

代码最后面再加几行测试,注意代码不缩进:

可见输出结果正确,但是耗时极长,无法通过LeetCode的测试,在 较长时此算法没有使用价值。不过想想也知道既然 是Python内建函数,想必已经在效率问题上做到几乎最好了吧,而967ms这一成绩所受限制是Python的基因。

实现(思路2)

自己实现求子集的函数,尽管效率很可能不如内建函数,但有重大的学习意义。这里仅简要讨论递归方法,若想深入研究或学习其他求子集算法可参考 CSDN博客:求一个集合所有子集的Python实现。

测试

答案正确,但所耗时长为思路1的两倍。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180821G1J8RD00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券