Cho start và end. Tìm tất cả số trong khoảng [start, end] mà các chữ số của nó tăng liên tiếp (ví dụ: 5678, 123, 89). Số như 169 không tính vì 1→6→9 không tăng 1 đơn vị.
Ví dụ
Input: start = 10, end = 150
Output: [12, 23, 34, 45, 56, 67, 78, 89, 123]
Thuật toán (Sinh tất cả số tăng liên tiếp)
Chuỗi "123456789" chứa tất cả dãy tăng liên tiếp có thể có. Duyệt mọi cặp chỉ số (i, j) với i < j, lấysubstring s[i:j] chuyển thành số, kiểm tra trong khoảng.
Mã nguồn Python
def solve(start, end):
s = "123456789"
a = []
for i in range(9):
for j in range(i + 1, 10):
x = int(s[i:j])
if start <= x <= end:
a.append(x)
return sorted(a)
# Test
start = 10
end = 150
print(solve(start, end)) # Output: [12, 23, 34, 45, 56, 67, 78, 89, 123]Độ phức tạp
- Thời gian:
O(1)— chỉ có 45 substring có thể của "123456789" (9*10/2). - Không gian:
O(1)— kết quả tối đa 45 số.
Lưu ý: Giải pháp này tối ưu vì không gian tìm kiếm rất nhỏ (chỉ 45 số tăng liên tiếp có thể tồn tại trong phạm vi int).