我今天早些时候参加了这个测试,试图聪明过头导致卡住了。不幸的是,我陷入了这种思维困境,浪费了太多时间,在测试的这一部分失败了。之后我解决了它,但希望你们可以帮助我摆脱最初的困境。
问题定义:
给定一个由N个整数组成的未排序、非唯一序列A(均为正数)。来自A的子序列是通过从A中删除零个或多个元素获得的任意序列。序列的振幅是该序列中最大元素与最小元素之间的差值。空子序列的振幅被认为是0。
例如,考虑由六个元素组成的序列A,其中:
如果一个数组A的子序列幅度不超过1,则称其为准恒定子序列。在上面的示例中,子序列[1,2]、[6,6]和[6,6,7]是准恒定的。子序列[6,6,7]是A中可能的最长准恒定子序列。
现在,找到一个解决方案,给定由N个整数组成的非空零索引数组A,返回数组A的最长准恒定子序列的长度。例如,对于上述序列A,函数应该返回3。
我使用没有类的基于排序的方法在Python 3.6中解决了这个问题(下面是我的代码),但我最初并不想这样做,因为在大型列表上进行排序可能会非常慢。它似乎应该有一个相对简单的广度优先基于树的类形式,但我无法做到。你有什么想法吗?
问题定义:
给定一个由N个整数组成的未排序、非唯一序列A(均为正数)。来自A的子序列是通过从A中删除零个或多个元素获得的任意序列。序列的振幅是该序列中最大元素与最小元素之间的差值。空子序列的振幅被认为是0。
例如,考虑由六个元素组成的序列A,其中:
A[0] = 1
A[1] = 7
A[2] = 6
A[3] = 2
A[4] = 6
A[5] = 4
如果一个数组A的子序列幅度不超过1,则称其为准恒定子序列。在上面的示例中,子序列[1,2]、[6,6]和[6,6,7]是准恒定的。子序列[6,6,7]是A中可能的最长准恒定子序列。
现在,找到一个解决方案,给定由N个整数组成的非空零索引数组A,返回数组A的最长准恒定子序列的长度。例如,对于上述序列A,函数应该返回3。
我使用没有类的基于排序的方法在Python 3.6中解决了这个问题(下面是我的代码),但我最初并不想这样做,因为在大型列表上进行排序可能会非常慢。它似乎应该有一个相对简单的广度优先基于树的类形式,但我无法做到。你有什么想法吗?
def amp(sub_list):
if len(sub_list) <2:
return 0
else:
return max(sub_list) - min(sub_list)
def solution(A):
A.sort()
longest = 0
idxStart = 0
idxEnd = idxStart + 1
while idxEnd <= len(A):
tmp = A[idxStart:idxEnd]
if amp(tmp) < 2:
idxEnd += 1
if len(tmp) > longest:
longest = len(tmp)
else:
idxStart = idxEnd
idxEnd = idxStart + 1
return longest
O(n log n)
,并且已经高度优化。大多数树算法具有相同的时间复杂度,但并未进行优化。你为什么认为树算法比基于排序的算法更好呢?(一个好的基于排序的解决方案在排序后是O(n)
的。) - Rory Daulton