問題陳述：給定一個整數陣列 nums。您最初位于陣列的第一個索引處，陣列中的每個元素都代表您在該位置的最大跳躍長度。如果可以到達最后一個索引，則回傳 true，否則回傳 false。
如何更改我的代碼，以便在找到適用于此問題的路徑時立即回傳，而不是通過我之前進行的所有遞回呼叫
def canJump(self, nums: List[int]) -> bool:
solve = [False]
def backtrack(i):
if solve[0] == True:
return
if i == len(nums)-1:
solve[0] = True
return
if i >= len(nums) or nums[i] == 0:
return
for x in range(1, nums[i] 1):
backtrack(i x)
backtrack(0)
return solve[0]
uj5u.com熱心網友回復：
遞回函式的一般形式
遞回函式的一般形式有兩種互斥型別的條件，可以在遞回的每次迭代中滿足。這些是：
- 終端條件，或
- 非終端條件。兩種型別的條件都會導致回傳陳述句。
終端條件
終止條件中的 return 陳述句通常采用return <value>.
您嘗試解決的問題的解決方案需要兩個可能的終端條件：
- 您知道可以到達最后一個索引的情況。
return True - 您知道無法到達最后一個索引的情況。
return False
非終止條件
非終結條件將發生在兩個終結情況都不為真的迭代中。在這種情況下，您將呼叫遞回函式并回傳它回傳的內容。
這個答案更詳細地涵蓋了終端和非終端條件。
例子
考慮一個對陣列的數字求和的遞回函式。
def sum(position, array, end):
if(position == end): # terminal condition
return 0
else: # non-terminal condition
return array[position] sum(position 1, array, end)
另一個例子
根據我可能錯過的對您的問題的任何限制，解決方案可能如下：
def jump(current_position, nums, finish_line):
"""
greedy algorithm:
choose the next position with the largest sum of (jump_range index)
"""
jump_range = nums[current_position]
choice = current_position jump_range
if(jump_range == 0): # terminal condition
return False
if(choice >= finish_line): # terminal condition
return True
else: # non-terminal condition
utility = 0
for next_position in range(current_position 1, jump_range 1):
next_jump_range = nums[next_position]
if(utility <= next_position next_jump_range):
utility = next_position next_jump_range
choice = next_position
return jump(choice, nums, finish_line)
input1 = [2,0,0,10,3]
input2 = [2,3,0,10,3]
current_position = 0
finish_line = len(input1)
print(jump(0, input1, finish_line)) # False
finish_line = len(input2)
print(jump(0, input2, finish_line)) # True
與您的解決方案最值得注意的區別是return 陳述句總是回傳一個 value。
uj5u.com熱心網友回復：
如何更改我的代碼，以便在找到適用于此問題的路徑時立即回傳，而不是通過我之前進行的所有遞回呼叫
一種特別直接的方法是拋出例外，這將立即展開堆疊。
def can_jump(nums: list[int]) -> bool:
if not nums:
return False
class _Success(Exception):
pass
def backtrack(i):
if i >= len(nums):
return
if i == len(nums) - 1:
raise _Success()
for x in range(1, nums[i] 1):
backtrack(i x)
try:
backtrack(0)
return False
except _Success:
return True
我們創建了一個本地例外型別_Success，稱為回溯搜索可以拋出以指示它找到了解決方案。
如果它永遠找不到解決方案，該backtrack函式將簡單地回傳并且該return False行將運行。否則，它將運行raise _Success()，然后該return True行將運行。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/495652.html
上一篇：AttributeError：“函式”物件沒有遞回函式的屬性“isSubtree”
下一篇：遞回DFS列印嵌套串列