python – 数组中最长的Snake序列
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了python – 数组中最长的Snake序列,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2133字,纯文字阅读大概需要4分钟。
内容图文
![python – 数组中最长的Snake序列](/upload/InfoBanner/zyjiaocheng/699/945c13b8d7af4c87b288c7488c886536.jpg)
问题:由空格分隔的一组数字作为输入传递.程序必须打印数字中存在的最大蛇序列.蛇序列由相邻的数字组成,对于每个数字,右边或左边的数字是它的值的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
我在线搜索过& amp;在给出数字网格时,我们只找到了找到蛇序列的参考文献.不是一个数组.
到目前为止我的方案:
创建一个2D数组,其中包含输入中的所有数字作为1值,第二个值是可以从该数字开始生成的最大长度序列.但是这并不总是生成最大长度序列,并且当有2条最大长度的蛇时根本不起作用.
解决方法:
假设原始数字集中的顺序无关紧要,就像你的问题中的情况一样,这似乎是Longest Path Problem的一个实例,这是NP难的.
可以这样想:您可以根据数字创建一个图形,所有节点对之间的边缘相差一个.现在,此图中最长的简单(非循环)路径就是您的解决方案.您的第一个示例将对应于此图表和路径. (请注意,输入集中的两个节点有两个节点.)
虽然这本身并不能解决您的问题,但它应该可以帮助您开始寻找解决(或近似)它的算法,现在您已经知道了问题的更好/更常见的名称.
一种算法的工作原理如下:从每个数字开始,确定“相邻”数字,并在图表中进行深度优先搜索,以确定最长路径.请记住暂时从图表中删除受访节点.这具有O(2n)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]
请注意,此算法将可靠地找到最大的“蛇”序列,使用的数量不会超过允许数量.然而,它可能找不到预期作为输出的特定序列,即“以自然输入顺序出现的蛇序列”,无论该意图是什么意思.
为了更接近“自然顺序”,您可以按照它们在输入中出现的顺序尝试数字(就像我对排序所做的那样),但这也不能完美地工作.无论如何,我相信你可以自己弄清楚剩下的.
1)在这种特殊情况下,图形的分支因子为2,因此O(2n);在更一般的情况下,复杂性将更接近O(n!).
内容总结
以上是互联网集市为您收集整理的python – 数组中最长的Snake序列全部内容,希望文章能够帮你解决python – 数组中最长的Snake序列所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。