Giả sử chúng ta phải tìm một mảng có kích thước N sao cho hiệu số tuyệt đối giữa mọi chữ số liên tiếp là K. Mọi số trong câu trả lời không được có các số 0 ở đầu ngoại trừ chính số 0.
Vì vậy, nếu đầu vào là N =4 K =7, thì đầu ra sẽ là [1818, 2929, 7070, 8181, 9292], ở đây 0707 không hợp lệ vì nó có số 0 đứng đầu.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
nếu N giống 1 thì
-
trả về một danh sách mới từ phạm vi 0 đến 9
-
-
queue:=tạo một hàng đợi với tất cả các phần tử từ 1 đến 9
-
đối với n trong phạm vi từ 0 đến N - 2, thực hiện
-
len_queue:=kích thước của hàng đợi
-
cho j trong phạm vi 0 đến len_queue - 1, thực hiện
-
num:=mục bên trái của hàng đợi và xóa nó khỏi hàng đợi
-
lsd:=num mod 10
-
nếu lsd - K> =0, thì
-
chèn num * 10 + lsd - K vào cuối hàng đợi
-
-
nếu K và lsd + K <=9 thì
-
chèn num * 10 + lsd + K vào cuối hàng đợi
-
-
-
-
trả về các phần tử của hàng đợi
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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]