Leetcode 891
2018-08-23 本文已影响0人
ahalshai
Leetcode 891 刷题指南
作为刷leetcode界的菜鸡，碰到这道题当时是非常地震惊，哪怕找到了可行的思路，tle也成为了一个障碍，感觉做这题过程中学到了不少。话不多说，一起来看题
image
subsequence这种题我刷的不多，但印象中在leetcode上不少，本题要求得到每个子序列（子序列就不解释了，看题里的例子）中最大值最小值的差值的和，并取它除10^9+7的余数，子序列就一个元素显然是0，如果有两个就是这两个元素之差。
如果枚举子序列的话就是2n次，题目给出n可达20000，这个数字很惊人，于是一开始我想到了O(n2)的方法，将列表排序O（nlogn），对于列表第i个元素，其与第j(i>j)个元素的差会出现
image
次对每个元素进行循环，时间复杂度为O(n^2)，然而通过调用scipy库的组合数碰到了这种玄幻问题s
image
这种问题在discuss里面别人也碰到（19个test case左右，用的是pow），实在搞不明白，想到可能是int float计算中导致的误差，但具体原因不明望有人指正。
后来发现完全可以把一个元素被加的次数减去被减的次数再乘以这个元素的值，而我之前算的组合数的和其实就是2^(i-1)-2 .......
所以每个元素的系数（被加减的净次数）就是2(i-1)-2(n-i)，计算和只需要O（nlogn）于是有O（nlogn），即排序所需的时间如下算法
class Solution:
def sumSubseqWidths(self, A):
"""
:type A: List[int]
:rtype: int
"""
A.sort(reverse=True)
n=len(A)
res=0
for i in range(n):
res+=((1<<(n-i-1))-(1<<i))*A[i]
res=res%(10**9 + 7)
return res
注意这里是倒序排的，当时在四十几个case的时候还是出现了tle的情况，看了别人的讨论才发现<<这种亮瞎眼的方法
再贴一个目前看到的最短时间答案：
class Solution:
def sumSubseqWidths(self, A):
"""
:type A: List[int]
:rtype: int
"""
A.sort()
res=0
for i in range(len(A)):
res*=2
res-=A[i]
res+=A[~i]
res%=10**9+7
return res
从我的思路能够理解，然而自己怕是很难想到，人家的乘2与众不同啊，~也是hacky
