我正在嘗試在硬幣找零問題中實現(xiàn)貪心方法，但需要降低時間復雜度，因為編譯器不會接受我的代碼，而且由于我無法驗證我什至不知道我的代碼是否真的正確. 該函數(shù)應返回進行更改所需的注釋總數(shù)。如果無法獲得給定金額的找零，則返回 -1。如果金額等于面額列表中可用的一種貨幣，則返回 1。def make_change(denomination_list, amount): denomination_list.sort() n = len(denomination_list) i = n - 1 ans = 0 x = 0 while i>= 0 : while denomination_list[i]<= amount: ans = +1 amount -= denomination_list[i] i -= 1 if amount == 0: x = 1 elif amount<0: x = -1 return x amount= 20 denomination_list = [1,15,10] print(make_change(denomination_list, amount))
1 回答
白豬掌柜的
TA貢獻1893條經驗 獲得超10個贊
如果可能，您希望盡量減少列表索引的使用，并迭代列表本身。這是一個有效的代碼：
# Pre-process denomination list before function, sorting in decreasing order
denomination_list = [1,15,10]
denomination_list.sort(reverse = True)
# Ensure ones are available for change (or infinite loop may result)
if denomination_list[-1] != 1:
denomination_list.append(1)
def make_change(denomination_list, amount):
change = []
# Iterate through coins
for coin in denomination_list:
# Add current coin as long as not exceeding ampoiunt
while amount:
if coin <= amount:
change.append(coin)
amount -= coin
else:
break
return change
amount= 43
print(make_change(denomination_list, amount))
這將適用于 的非整數(shù)值，amount并將列出向下舍入金額的變化。
添加回答
舉報
0/150
提交
取消