Nic*_*chD 5 python tree subsequence
今天早些时候我做了这个测试，我试图太聪明并撞上了路障。不幸的是，我陷入了这种思维模式并浪费了太多时间，未能通过这部分测试。后来我解决了它，但也许你们都可以帮助我摆脱最初的习惯。
问题定义：
给出了一个由 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
我不知道 BFS 应该如何在这里提供帮助。
为什么不简单地运行一次序列并计算每个可能的准常数子序列将有多少个元素？
from collections import defaultdict
def longestQuasiConstantSubseqLength(seq):
d = defaultdict(int)
for s in seq:
d[s] += 1
d[s+1] += 1
return max(d.values() or [0])
s = [1,7,6,2,6,4]
print(longestQuasiConstantSubseqLength(s))
印刷：
3
正如预期的那样。
解释：每个非常数准常数子序列都由它包含的最大数唯一标识（只能有两个，取较大的一个）。现在，如果您有一个数字，它可以对具有或作为最大数字的s准常数子序列做出贡献。因此，只需添加到由和标识的子序列即可。然后输出所有计数中的最大值。ss + 1+1ss + 1
您无法比 更快地获得它O(n)，因为您必须至少查看输入序列的每个条目一次。
正如 Andrey Tyukin 指出的那样，您可以及时解决这个问题，这比您通过排序或任何基于树的解决方案可能获得的时间O(n)要好。O(n log n)诀窍是使用字典来计算输入中每个数字出现的次数，并使用计数来找出最长的子序列。
我和他有类似的想法，但我的实现方式略有不同。经过一些测试，看起来我的方法要快得多，所以我将其作为我自己的答案发布。相当短啊！
from collections import Counter
def solution(seq):
if not seq: # special case for empty input sequence
return 0
counts = Counter(seq)
return max(counts[x] + counts[x+1] for x in counts)
我怀疑这比 Andrey 的解决方案更快，因为我们两个解决方案的运行时间确实需要O(n) + O(k)时间，其中是输入中不同k值的数量（并且是输入中值的总数）。我的代码通过将序列交给构造函数（用 C 实现）来非常有效地处理该部分。处理该部分可能会慢一些（基于每个项目），因为它需要一个生成器表达式。Andrey 的代码执行相反的操作（它为该部件运行较慢的 Python 代码，并为该部件使用更快的内置 C 函数）。由于总是小于或等于（如果序列有很多重复值，则可能会少很多），因此我的代码总体上更快。但这两种解决方案仍然存在，并且都应该比对大输入进行排序要好得多。nO(n)CounterO(k)O(n)O(k)knO(n)