我正在尝试在硬币找零问题中实现贪婪方法,但是由于编译器不会接受我的代码,并且由于无法验证,所以我什至不知道我的代码是否正确,因此需要降低时间复杂度或不。该函数应返回进行更改所需的注释总数。如果无法获得给定金额的零钱,则返回-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))
如果可能,您希望尽量减少列表索引的使用,并遍历列表本身。这是一个有效的代码:
# 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))
这将适用于amount
的非整数值,并将列出四舍五入的更改。