时间戳

首页 > 解决方案 > Python以给定的索引跳转或更少的方式递归地跳过列表，同时避免零

python - Python以给定的索引跳转或更少的方式递归地跳过列表，同时避免零

问题描述

我正在尝试编写一个只有一个参数的函数，一个正整数列表。

它必须是递归的，并找出是否可以从头到尾同时避免落在 0 上。它必须从第一个值开始，list[0]但您可以跳跃全部或更少。

例如

list1 = [3,1,2,0,4,0,1]
list2 = [3,2,1,0,2,0,2]

列表 1 应该返回True，因为您可以从 3 跳到 2 再从 4 跳到 1。

清单 2 应该返回False，因为无论您如何跳跃，您都会在第一个 0 处着陆。

到目前为止，这是我的尝试：

def check_level(level):
    jump = level[0]
    if level[-1] == 0:
        return False
    elif jump == 0:
        return False
    
    elif jump == 0:
        return False
    
    elif len(level) > 1:
        if level[jump] > len(level):
            return True

        elif level[-1] == 0:
            return False
        
        elif level[0] != 0:
            if level[jump] == 0:
                level[0] -= 1
                return check_level(level)
            else:
                jump_index = level.index(level[jump])
                new_level = level[jump_index:]
                return check_level(new_level)

    else:
        return True

它不适用于所有示例，并且与其他示例一起出现错误：

if level[jump] > len(level):
TypeError: '>' not supported between instances of 'list' and 'int'```

I am out of ideas on how to approach this and whether my approach is failed from the start... I hate recursion, hence I need to practice it.

标签： pythonlistrecursion

解决方案

一般逻辑是：

“如果你能跳到一个True位置，那么当前位置也是True”

像这样实现：

def checklevel(lst):
    if not lst:
        # no list is True (we are done)
        return True  
    return any( checklevel(lst[i:]) for i in range(1,lst[0]+1))

list1 = [3,1,2,0,4,0,1]
list2 = [3,2,1,0,2,0,2]

assert checklevel(list1)
assert not checklevel(list2)

请注意，这对于大型列表来说是一个糟糕的解决方案，在这种情况下您应该尝试迭代 dp-table。

推荐阅读