Giả sử có một quán bán nước chanh, mỗi ly giá 5$. Khách hàng xếp hàng mua lần lượt một người một.
Mỗi khách chỉ mua một ly và trả bằng tờ 5$, 10$ hoặc 20$. Chúng ta phải trả tiền thừa chính xác cho mỗi khách sao cho giao dịch thực tế là khách chỉ trả 5$. Ban đầu chúng ta không có tiền thừa.
Ta cần kiểm tra xem có thể trả tiền thừa chính xác cho mọi khách hay không.
Ví dụ, nếu đầu vào là [5,5,5,10,20], đầu ra sẽ là True, vì từ 3 khách đầu tiên ta thu được ba tờ 5$. Khách thứ 4 trả tờ 10$ và ta trả lại 5$. Khách thứ 5 trả 20$, ta trả lại một tờ 10$ và một tờ 5$. Vì tất cả khách đều được trả đúng tiền thừa, nên kết quả là True.
Để giải quyết, ta thực hiện các bước sau:
- n5 := 0, n10 := 0, n20 := 0
- Với mỗi i trong bills, thực hiện:
- Nếu i bằng 5, thì:
- n5 := n5 + 1
- Ngược lại, nếu i bằng 10, thì:
- n10 := n10 + 1
- Ngược lại n20 := n20 + 1
- Nếu kích thước bills > 0 và n5 bằng 0, thì:
- Trả về False
- Nếu i bằng 20 và n10 > 0 và n5 > 0, thì:
- n10 := n10 - 1
- n5 := n5 - 1
- Ngược lại, nếu i bằng 20 và n10 bằng 0 và n5 < 3, thì:
- Trả về False
- Ngược lại, nếu i bằng 20 và n10 bằng 0 và n5 >= 3, thì:
- n5 := n5 - 3
- Nếu i bằng 10 và n5 > 0, thì:
- n5 := n5 - 1
- Ngược lại, nếu i bằng 10 và n5 bằng 0, thì:
- Trả về False
- Nếu i bằng 5, thì:
- Trả về True
Hãy xem triển khai sau để hiểu rõ hơn:
Ví dụ
class Solution: def lemonadeChange(self, bills): n5 = 0 n10 = 0 n20 = 0 for i in bills: if i == 5: n5 += 1 elif i == 10: n10 += 1 else: n20 += 1 if len(bills) > 0 and n5 == 0: return False if i == 20 and n10 > 0 and n5 > 0: n10 -= 1 n5 -= 1 elif i == 20 and n10 == 0 and n5 < 3: return False elif i == 20 and n10 == 0 and n5 >= 3: n5 = n5 - 3 if i == 10 and n5 > 0: n5 -= 1 elif i == 10 and n5 == 0: return False return True ob = Solution() print(ob.lemonadeChange([5,5,5,10,20]))
Đầu vào
[5,5,5,10,20]
Đầu ra
True