สมมติว่าต้องหาอาร์เรย์ขนาด N ที่ความต่างสัมบูรณ์ระหว่างหลักติดกันทุกคู่เท่ากับ K ตัวเลขทุกตัวต้องไม่มีศูนย์นำหน้า (ยกเว้น 0 เอง)
ตัวอย่าง: N = 4, K = 7 ผลลัพธ์ [1818, 2929, 7070, 8181, 9292] (ไม่รวม 0707 เพราะมีศูนย์นำหน้า)
วิธีแก้ปัญหา (BFS)
- ถ้า
N == 1คืน0..9 queue := deque(1..9)- วน
N-1รอบ:- ดึงตัวเลขจากคิว คำนวณหลักสุดท้าย
lsd - ถ้า
lsd - K >= 0เพิ่มnum*10 + lsd - K - ถ้า
K != 0 และ lsd + K <= 9เพิ่มnum*10 + lsd + K
- ดึงตัวเลขจากคิว คำนวณหลักสุดท้าย
- คืนค่าทั้งหมดในคิว
ตัวอย่างโค้ด
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))
อินพุต
4, 7
เอาต์พุต
[1818, 2929, 7070, 8181, 9292]
