Kiểm tra các phần tử trong hàng đợi có liên tiếp từng cặp không (Python)

Bài toán: Cho một hàng đợi (queue) các số nguyên, kiểm tra xem các phần tử liên tiếp có tạo thành các cặp số liên tiếp nhau (chênh lệch 1) hay không.

Thuật toán

1. Đưa tất cả phần tử vào queue q.
2. Chuyển sang list temp để dễ thao tác.
3. Đảo ngược temp vào temp2 (để lấy từ đầu queue gốc).
4. Duyệt temp2 từng cặp (x, y), kiểm tra |x - y| == 1.
5. Nếu mọi cặp đều thỏa mãn → trả về True, ngược lại False.

Triển khai Python

import queue

def solve(que):
    q = queue.Queue()
    for i in que:
        q.put(i)
    
    temp = []
    while q.qsize() != 0:
        temp.append(q.queue[0])
        q.get()
    
    temp2 = []
    while len(temp) != 0:
        temp2.append(temp[len(temp) - 1])
        temp.pop()
    
    result = True
    while len(temp2) > 1:
        x = temp2[len(temp2) - 1]
        temp2.pop()
        y = temp2[len(temp2) - 1]
        temp2.pop()
        if abs(x - y) != 1:
            result = False
        q.put(x)
        q.put(y)
    
    if len(temp2) == 1:
        q.put(temp2[len(temp2) - 1])
    
    return result

# Test
que = [3, 4, 6, 7, 8, 9]
print(solve(que))  # True

Kết quả

True

Giải thích

• Input [3,4,6,7,8,9] có các cặp: (3,4), (6,7), (8,9) - tất cả chênh lệch 1.
• Phương pháp dùng queue và list để mô phỏng thao tác hàng đợi thực tế.
• Độ phức tạp: O(n) thời gian, O(n) không gian.