时间戳

首页 > 解决方案 > 递归函数返回值而不分配额外空间？

python - 递归函数返回值而不分配额外空间？

问题描述

所以我一直在尝试优化这个叫做 Frog Jump 的 LeetCode 问题。以下是问题的基本描述：

给定一个按升序排列的石头位置列表（以单位为单位），确定青蛙是否能够通过降落在最后一块石头上过河。最初，青蛙在第一块石头上，并假设第一次跳跃必须是 1 个单位。

如果青蛙的最后一次跳跃是 k 个单位，那么它的下一次跳跃必须是 k - 1、k 或 k + 1 个单位。请注意，青蛙只能向前跳跃。

例如：[0,1,3,5,6,8,12,17]

总共有8块石头。第 0 个单位的第一块石头，第 1 个单位的第二块石头，第 3 个单位的第三块石头，依此类推……第 17 个单位的最后一块石头。

返回真。青蛙可以跳到最后一块石头，方法是先跳 1 个单位到第 2 块石头，然后 2 个单位到第 3 块石头，然后 2 个单位到第 4 块石头，然后 3 个单位到第 6 块石头，4 个单位到第 7 块石头，然后 5 个单位单位到第 8 石。

这是我的解决方案。我需要帮助的是如何在不分配额外的res数组的情况下输出相同的布尔值，该数组使用 DFS 存储所有探索路径的逻辑 OR。

class Solution:
    def canCross(self, stones: List[int]) -> bool:
        
        if stones[1] != 1:
            return False
        
        res = []
        memo = {}
        
        def dfs(curr_stone, last_stone, last_jump):
            
            if curr_stone == last_stone:
                res.append(True)
                return
            
            if curr_stone > last_stone:
                res.append(False)
                return
            
            for i in range(-1,2):
                next_stone = curr_stone + (last_jump + i)
                if next_stone in stones and next_stone > curr_stone and (next_stone, last_stone, last_jump+i) not in memo:
                    memo[(next_stone, last_stone, last_jump+i)] = 1
                    dfs(next_stone, last_stone, last_jump+i)
        
        dfs(1, stones[-1], 1)
        return any(res)

有人可以帮助我解决这些问题吗？我总是在这些问题上苦苦挣扎，最终将值存储在数组中；但是，理想情况下，我希望递归代码的结果是相同的，而不分配额外的 res 数组空间。

标签： pythonrecursiondepth-first-search

解决方案

由于该函数的整个目的似乎归结为 return any(res)，因此您似乎应该从递归函数中返回True/而不是附加它们，然后在找到单个值False后退出所有递归调用，而不必费心保存每个找到的值True.

这将涉及检查从递归调用返回的内容dfs(next_stone, last_stone, last_jump+i)，如果是真的，只需返回True：

from typing import List

class Solution:
    def canCross(self, stones: List[int]) -> bool:

        if stones[1] != 1:
            return False

        memo = {}

        def dfs(curr_stone, last_stone, last_jump):

            if curr_stone == last_stone:
                return True  # Return the results instead of appending them to a list

            if curr_stone > last_stone:
                return False

            for i in range(-1, 2):
                next_stone = curr_stone + (last_jump + i)
                if next_stone in stones and next_stone > curr_stone and (next_stone, last_stone, last_jump + i) not in memo:
                    memo[(next_stone, last_stone, last_jump + i)] = 1
                    rec_result = dfs(next_stone, last_stone, last_jump + i)
                    if rec_result:  # Then check the recursive results at the call-site
                        return True

        return dfs(1, stones[-1], 1)

我会注意到，我没有对此进行广泛的测试，但从一些快速的“头部解释”来看，它似乎是等价的。

推荐阅读