Giả sử chúng ta có một danh sách các chuỗi được gọi là đơn đặt hàng. Mỗi phần tử trong danh sách đơn hàng bắt đầu bằng "P" hoặc "D". Chữ "P" cho biết đã được nhận và "D" có nghĩa là "giao hàng". Và những chữ cái này được theo sau bởi số id đơn hàng. Ví dụ:"P6" cho biết đơn hàng lấy hàng 6. Chúng tôi phải kiểm tra xem danh sách đơn hàng có hợp lệ hay không dựa trên các quy tắc này -
- Chúng tôi không thể giao đơn đặt hàng trước khi nhận hàng
- Mọi lần nhận hàng đều phải được giao hàng
- Một đơn đặt hàng đã được nhận và cũng đã được giao không thể nhận hoặc giao lại
Vì vậy, nếu đầu vào giống như đơn đặt hàng =["P1", "D1", "P2", "P3", "D3", "D2"], thì đầu ra sẽ là True, vì đơn đặt hàng đầu tiên được giao sau khi lấy hàng và đối với đơn đặt hàng thứ hai và thứ ba, chúng được nhận cùng một lúc và cuối cùng cũng được giao.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- a:=một bản đồ mới
- nếu đơn đặt hàng có bất kỳ mục nhập trùng lặp nào, thì
- trả về Sai
- đối với mỗi tôi trong đơn đặt hàng, hãy thực hiện
- nếu tôi bắt đầu bằng "P", thì
- a [lấy số thứ tự] =1
- nếu không, khi tôi bắt đầu bằng "D", thì
- nếu số thứ tự không ở trong a, thì
- trả về Sai
- nếu không,
- một [số thứ tự giao hàng] giảm đi 1
- nếu số thứ tự không ở trong a, thì
- nếu tôi bắt đầu bằng "P", thì
- trả về true khi tổng của tất cả các phần tử có trong danh sách tất cả các giá trị của a bằng 0, ngược lại là false
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
def solve(orders):
a = {}
if len(set(orders)) != len(orders):
return False
for i in orders:
if i[0] == "P":
a[i[1:]] = 1
elif i[0] == "D":
if i[1:] not in a:
return False
else:
a[i[1:]] -= 1
return sum(a.values()) == 0
orders = ["P1", "D1", "P2", "P3", "D3", "D2"]
print(solve(orders)) Đầu vào
["P1", "D1", "P2", "P3", "D3", "D2"]
Đầu ra
True