Сложность: medium
Даны два целых числа n и k, верните массив всех целых чисел длины n, где разница между каждыми двумя последовательными цифрами равна k. Вы можете вернуть ответ в любом порядке.
Учтите, что целые числа не должны начинаться с нулей. Целые числа, такие как 02 и 043, не допускаются.
Пример:
Input: n = 3, k = 7
Output: [181,292,707,818,929]
Explanation: Note that 070 is not a valid number, because it has leading zeroes.
👨💻 Алгоритм:
1⃣Если n равно 1, верните массив от 0 до 9, так как все однозначные числа являются допустимыми.
2⃣Инициализируйте список очередей начальными цифрами от 1 до 9.
3⃣Для каждого уровня (от 1 до n-1) создайте новый список очередей, добавляя к каждому числу в текущей очереди допустимые цифры, которые удовлетворяют условию разницы k.
😎 Решение:
class Solution:
def numsSameConsecDiff(self, N: int, K: int) -> List[int]:
if N == 1:
return list(range(10))
queue = list(range(1, 10))
for _ in range(N - 1):
next_queue = []
for num in queue:
tail_digit = num % 10
next_digits = {tail_digit + K, tail_digit - K}
for next_digit in next_digits:
if 0 <= next_digit < 10:
next_queue.append(num * 10 + next_digit)
queue = next_queue
return queue
Ставь 👍 и забирай 📚 Базу знаний