Chương trình sắp xếp bài để chúng được lộ ra theo thứ tự tăng dần trong Python

Giả sử chúng ta có một danh sách các bài, và chúng ta muốn sắp xếp các bài sao cho khi lộ ra chúng theo thứ tự tăng dần. Quy trình lộ bài như sau: 1. Bài trên cùng được lấy ra và lộ ra, sau đó bài tiếp theo được đưa về cuối. 2. Lặp lại bước 1 cho đến khi không còn bài nào. Chúng ta cần tìm một thứ tự sắp xếp các bài sao cho chúng được lộ ra theo thứ tự tăng dần.

Ví dụ, nếu đầu vào là cards = [1, 2, 3, 4, 5, 6, 7, 8], thì đầu ra sẽ là [1, 5, 2, 7, 3, 6, 4, 8], vì:

• 1 bị loại bỏ và 5 được đưa về cuối, trạng thái hiện tại: [2, 7, 3, 6, 4, 8, 5]
• 2 bị loại bỏ và 7 được đưa về cuối, trạng thái hiện tại: [3, 6, 4, 8, 5, 7]
• 3 bị loại bỏ và 6 được đưa về cuối, trạng thái hiện tại: [4, 8, 5, 7, 6]
• 4 bị loại bỏ và 8 được đưa về cuối, trạng thái hiện tại: [5, 7, 6, 8]
• 5 bị loại bỏ và 7 được đưa về cuối, trạng thái hiện tại: [6, 8, 7]
• 6 bị loại bỏ và 8 được đưa về cuối, trạng thái hiện tại: [7, 8]
• 7 bị loại bỏ và chỉ còn một bài [8]. Sau đó loại bỏ [8]

Để giải quyết bài toán này, chúng ta thực hiện các bước sau:

• Sắp xếp danh sách cards.
• Tạo danh sách idx chứa các chỉ số từ 0 đến độ dài của cards.
• Khởi tạo danh sách order rỗng.
• Sử dụng hàng đợi q và chèn các phần tử của idx vào đó.
• Trong khi q không rỗng, thực hiện:
  • Lấy phần tử bên trái của q và thêm vào order.
  • Nếu q vẫn không rỗng, lấy phần tử bên trái tiếp theo và thêm vào cuối q.
• Tạo danh sách ans có kích thước bằng cards, khởi tạo giá trị 0.
• Duyệt qua từng cặp phần tử i từ order và card từ cards, gán ans[i] = card.
• Trả về ans.

Ví dụ minh họa

from collections import deque

class Solution:
    def solve(self, cards):
        cards.sort()
        idx = [i for i in range(len(cards))]
        order = []
        q = deque(idx)
        while q:
            order.append(q.popleft())
            if q:
                q.append(q.popleft())
        ans = [0 for _ in cards]
        for i, card in zip(order, cards):
            ans[i] = card
        return ans

ob = Solution()
print(ob.solve([1, 2, 3, 4, 5, 6, 7, 8]))

Đầu vào

[1, 2, 3, 4, 5, 6, 7, 8]

Đầu ra

[1, 5, 2, 7, 3, 6, 4, 8]