假设您有以下列表
a_list = [1, 2, 3, 4, 8, 7, 6]
我们想要从列表的任一侧找到包含列表中所有元素的最小递增序列数。
对于上面的示例,我们将得到
顺序= [[1,2,3,4,8],[6,7]]
给出2的答案。这是因为我们可以形成从左到右依次为[1,2,3,4,8]的递增序列。我们还可以从右到左形成一个递增的序列,如[6,7]。
我考虑过创建两个列表,这些列表给出了列表的所有递增顺序以及列表的反向顺序,因此
left_to_right = [[1,2,3,4,8],[7], [6]]
right_to_left = [[6,7,8], [4], [3], [2], [1]]
但我不确定从那里去哪里。有什么想法吗?
编辑:原来下面是不必要的复杂。“从左边开始”增加意味着减少。因此,只需遍历列表一次,使用布尔标志跟踪递增和递减的序列,使它们尽可能长,然后在最后计数。这应该工作。未经测试。
increasing = None
current_item = _list[0]
all_sequences = []
current_sequence = [_list[0]]
for item in _list[1:]:
if increasing is None:
increasing = item > current_sequence[-1]
current_sequence.append(item)
elif (item > current_item and increasing) or (item < current_item and not increasing):
current_sequence.append(item)
elif (item > current_item and not increasing) or (item < current_item and increasing):
all_sequences.append(current_sequence)
current_sequence = [item]
increasing = None
current_item = item
all_sequences.append(current_sequence)
result = len(all_sequences)
原始答案:这是一些想法
首先,我假设您的函数将始终使序列尽可能长。所以你得到这个:
left_to_right = [[1,2,3,4,8],[7], [6]]
而不是例如:
left_to_right = [[1,2],[3],[4,8],[7], [6]]
(从技术上讲,这也是递增序列的列表)。
您的下一项工作是确保您获得列表中的所有数字。因此,您必须选择一些递增的序列。您选择的序列越长,在不增加太多序列的情况下获得“消耗”的数字就越多。举个例子:
left_to_right = [[1,2,3,4,8],[7], [6]]
right_to_left = [[6,7,8], [4], [3], [2], [1]]
将两个列表结合在一起:
all = left_to_right + right_to_left
现在找到最长的序列:
longest = max(all, key=lambda x:len(x))
那会给你
[1,2,3,4,8]
现在重复,获取下一个最长的序列,继续进行直到捕获到列表中的所有数字。那会给你:
[[1,2,3,4,8], [6,7,8]]
最后一步,检查是否重复。然后你会得到
[[1,2,3,4,8], [6,7]]
如预期的
我怀疑这应该总是给您最少的顺序。但是,如果有重复,我可能是错的。
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句