字典獲取 vs 在 cansum 代碼中表現不同
def canSum(targetSum, numbers, memo=None):
if memo == None:
memo = {}
if targetSum in memo:
return memo[targetSum]
if targetSum == 0:
return True
if targetSum < 0:
return False
for n in numbers:
remainder = targetSum - n
if canSum(remainder, numbers, memo):
memo[targetSum] = True
return True
memo[targetSum] = False
return False
print(canSum(7, [2, 3])) # True
print(canSum(7, [5, 3, 4, 7])) # True
print(canSum(7, [2, 4])) # False
print(canSum(8, [2, 3, 5])) # True
print(canSum(3000, [7, 14])) # False -> Works fast with large inputs!
當用 if memo.get(targetSum) 替換第 4 行時，該函式對最后一個輸入不起作用，由于時間復雜度巨大而繼續運行
def canSum(targetSum, numbers, memo=None):
if memo == None:
memo = {}
if memo.get(targetSum,False):
return memo[targetSum]
if targetSum == 0:
return True
if targetSum < 0:
return False
for n in numbers:
remainder = targetSum - n
if canSum(remainder, numbers, memo):
memo[targetSum] = True
return True
memo[targetSum] = False
return False
print(canSum(7, [2, 3])) # True
print(canSum(7, [5, 3, 4, 7])) # True
print(canSum(7, [2, 4])) # False
print(canSum(8, [2, 3, 5])) # True
print(canSum(3000, [7, 14])) # False -> Keeps running no output obtained
任何人都可以解釋原因嗎？我知道 .get 和 in 的作業方式如何不同，在下面附上了相關的 SO 執行緒：
為什么此解決方案適用于 Javascript 而不適用于 Python？（動態編程）
Python 詞典：“in”與“get”
uj5u.com熱心網友回復：
您的代碼的兩個版本并不等效。
在 wherememo[targetSum]和 is的情況下False，塊：
if targetSum in memo:
return memo[targetSum]
會回來False，但是
if memo.get(targetSum,False):
return memo[targetSum]
將不執行return，因為memo.get(targetSum,False)是False。在這種情況下，您將在函式末尾運行回圈。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/358191.html