问题:一组由空格分隔的数字作为输入传递。程序必须打印出数字中存在的最大的蛇形序列。蛇形序列由相邻的数字组成,因此对于每个数字,左侧或右侧的数字为其值的+1或-1。如果可能有多个最大长度的蛇形序列,请打印以自然输入顺序出现的蛇形序列。
输入/输出示例1:
输入:
9 8 7 5 3 0 1 -2 -3 1 2
输出:
3 2 1 0 1
输入/输出示例2:
输入:
-5 -4 -3 -1 0 1 4 6 5 4 3 4 3 2 1 0 2 -3 9
输出:
6 5 4 3 4 3 2 1 0 -1 0 1 2
输入/输出示例3:
输入:
5 6 7 9 8 8
输出:
5 6 7 8 9 8
我在网上搜索过&仅找到了给定数字网格而不是数组时找到蛇序列的参考。
到目前为止,我的解决方案:
创建一个2D数组,其中包含来自输入的所有数字作为1值,第二个值是可以从该数字开始生成的最大长度序列。但这并不总是生成最大长度序列,并且当有两条最大长度的蛇时根本不起作用。
假设原始数字集中的顺序无关紧要,就像您所提的问题一样,这似乎是NP难的最长路径问题的一个实例。
可以这样考虑:您可以根据数字创建图形,所有对节点之间的边之间的差为1。现在,此图中最长的简单(非循环)路径就是您的解决方案。您的第一个示例将与此图和路径相对应。(请注意,输入集中的两个节点有两个1节点。)
虽然这本身并不能解决您的问题,但现在您知道该问题的更好/更通用的名称,它应该可以帮助您开始寻找一种算法来解决(或近似)该问题。
一种算法的工作方式如下:从每个数字开始,确定“相邻”数字,并对图形进行深度优先搜索,以确定最长路径。记住要暂时从图中删除访问的节点。这具有O(2 n) 1)的最坏情况复杂度,但显然对于您的示例而言已足够。
def longest_snake(numbers, counts, path):
best = path
for n in sorted(counts, key=numbers.index):
if counts[n] > 0 and (path == [] or abs(path[-1] - n) == 1):
counts[n] -= 1
res = longest_snake(numbers, counts, path + [n])
if len(res) > len(best):
best = res
counts[n] += 1
return best
例子:
>>> from collections import Counter
>>> numbers = list(map(int, "9 8 7 5 3 0 1 -2 -3 1 2".split()))
>>> longest_snake(numbers, Counter(numbers), [])
[3, 2, 1, 0, 1]
请注意,此算法将可靠地找到最大的“蛇形”序列,使用的次数不超过允许的次数。但是,它可能找不到期望作为输出的特定序列,即“按自然输入顺序出现的蛇形序列”,无论这意味着什么。为了更接近“自然顺序”,您可以按与输入中出现的顺序相同的顺序尝试数字(就像我对进行的操作一样sorted
),但这也不完美。无论如何,我相信您可以自己解决其余的问题。
1)在这种特殊情况下,图的分支因子为2,因此为O(2 n);在更一般的情况下,复杂度将更接近O(n!)。
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句