Chương trình tìm các số có chênh lệch liên tiếp bằng nhau trong Python

Mô tả bài toán

Tìm tất cả các số có N chữ số sao cho chênh lệch tuyệt đối giữa hai chữ số liên tiếp luôn bằng K. Số không được có số 0 dẫn đầu (trừ số 0 chính nó).

Ví dụ

Nếu N = 4, K = 7, đầu ra là [1818, 2929, 7070, 8181, 9292]. Số 0707 không hợp lệ vì có số 0 dẫn đầu.

Giải thuật (BFS)

1. Nếu N == 1, trả về [0..9].
2. Khởi tạo hàng đợi queue với các số từ 1 đến 9.
3. Lặp N-1 lần:
   • Với mỗi số trong hàng đợi hiện tại, lấy chữ số cuối lsd.
   • Nếu lsd - K >= 0, thêm num*10 + lsd - K vào hàng đợi.
   • Nếu K != 0 và lsd + K <= 9, thêm num*10 + lsd + K vào hàng đợi.
4. Trả về các phần tử trong hàng đợi.

Triển khai Python

from collections import deque

def solve(N, K):
    if N == 1:
        return list(range(10))
    queue = deque(list(range(1, 10)))
    for n in range(N - 1):
        len_queue = len(queue)
        for j in range(len_queue):
            num = queue.popleft()
            lsd = num % 10
            if lsd - K >= 0:
                queue.append(num * 10 + lsd - K)
            if K and lsd + K <= 9:
                queue.append(num * 10 + lsd + K)
    return list(queue)

N = 4
K = 7
print(solve(N, K))

Đầu vào

4, 7

Đầu ra

[1818, 2929, 7070, 8181, 9292]