时间戳

首页 > 解决方案 > Recusive fxn 没有返回预期的结果

python - Recusive fxn 没有返回预期的结果

问题描述

所以我正在研究一个hackerrank简单的问题。这实际上很容易，但我发现了一些我确定很小但我找不到的东西，我希望你们能帮助找出问题所在。

问题的名称是“Jumping on The Clouds”，转述摘要如下：

“玩家可以跳上任何积云，其数字等于当前云的数量加 1 或 2

. 玩家必须避开雷雨云。确定从起始位置跳到最后一朵云所需的最少跳跃次数。总是有可能赢得比赛。

对于每场比赛，您将获得一组云，如果它们是安全的，则编号为0 ，如果必须避免，则编号为1 。"

为简化起见，您会得到一个由 0 和 1 组成的数组，并且您必须找到到达数组末尾所需的最小跳转量。您一次只能跳 1 或 2 个点，并且保证最后一朵云是“安全的”。

我立即看到这可以通过两种方式解决，1. 作为图论问题，2. 作为树实现。

我选择使用树实现。

这是我的代码：

def jumpingOnClouds(c):
    if len(c) <= 1:
        print("at end of string")
        return 0
    
    elif c[0] == 1:
        print("dead end")
        return -1
    
    else:
        one = jumpingOnClouds(c[1:])    
        two = jumpingOnClouds(c[2:])
        if one == -1 and two > 0:
            print("chose 2")
            return two + 1
        elif two == -1 and one > 0:
            print("chose 1")
            return one + 1
        else:
            print("both were viable")
            return min(one, two) + 1

简单吧？

除了它没有正确返回。

我尝试的是： 1：我将字符串末尾的返回值从“1”更改为“0”，就像现在一样。这是因为当我将它设置为 1 时，它总是返回 1 太高的数字。因此，如果最小值为 3，它将返回 4，等等。

2：当我在字符串末尾返回 0 时，它有时会保持原样并返回 0。

这方面的一个例子是输入 [0,0,1,0,0,1,0]，它使用我当前的代码返回 0。

很抱歉这么长的帖子，但我试图遵守社区的规则，而不是激怒任何人。谢谢您的帮助！

示例输入和输出：

[000010] -> 3
[0010010] -> 4
[000100] -> 3
[0100010] -> 3

标签： pythonarrayspython-3.xtree

解决方案

好的，它的测试one和two你绊倒的地方：

def jumpingOnClouds(c):
    if len(c) <= 1:
        #print("at end of string")
        return 0
    
    elif c[0] == 1:
        #print("dead end")
        return -1
    
    else:
        one = jumpingOnClouds(c[1:])    
        two = jumpingOnClouds(c[2:])
        if one == -1 and two >= 0:
            #print("chose 2")
            return two + 1
        elif two == -1 and one >= 0:
            #print("chose 1")
            return one + 1
        else:
            #print("both were viable")
            return min(one, two) + 1

for game in [[0,0,0,0,1,0],[0,0,1,0,0,1,0],[0,0,0,1,0,0],[0,1,0,0,0,1,0]]:
    print(f'{game} -> {jumpingOnClouds(game)}')

给定的输出

推荐阅读