Прыгающие числа

Постановка задачи

Дано положительное число X. Найдите наибольшее число прыжков, меньшее или равное X. Число прыжков: Число называется прыгающим числом, если все соседние цифры в нем отличаются только на 1. Все однозначные числа считаются прыгающими числами. Например, 7, 8987 и 4343456 являются прыгающими числами, а 796 и 89098 – нет.

Тестовые примеры

Пример 1:

Ввод: Вывод: 10 Объяснение: 10 – это наибольшее возможное число прыжков. Пример 2:

Ввод: Вывод: 45 Пояснение: 45 – это наибольшее возможное число прыжков.

Наша Задача

Вам не нужно ничего читать или печатать. Ваша задача – выполнить функцию jumpingNums(), которая принимает целое число X в качестве входных данных и возвращает наибольшее число прыжков, меньшее или равное X.

Ожидаемая сложность во времени и пространстве

Ожидаемая временная сложность: O(k), где k – количество скачущих чисел Ожидаемое вспомогательное пространство: O(k), где k – количество скачущих чисел

Ограничения

1^9

Подход

Здесь нам будет дано число, скажем, n, нам нужно найти способ получить максимальное число прыжков меньше или равно n.

Например, если наш, то прыгающие числа равны [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 21, 23, 32, 34, 43, 45]

Таким образом, из этого списка мы можем найти, что 45 – это самое большое число прыжков, которое есть. Поэтому нам нужно разработать алгоритм, чтобы мы могли получить список этих прыгающих чисел и легко найти из него максимум.

Здесь наше пространство поиска составляет от 0 до 50. 0-10 всегда включаются в качестве прыгающих чисел. Таким образом, для любого ввода n мы можем просто вернуть то число, которое будет желаемым ответом.

Остальные числа можно узнать с помощью алгоритма поиска в ширину или алгоритма поиска в глубину. Здесь я расскажу об алгоритме поиска в глубину.

Алгоритм

для i в диапазоне от 0 до 10 выполните поиск в bfs.

List results = new ArrayList<>();
for (int i=0; i<10 && i <= n; i++) {
        bfs(n, i, results);
}

Теперь внутри bfs мы начинаем с создания очереди, как обычно, и сохраняем текущий я внутри очереди.
пока очередь не пуста, мы продолжаем выполнять следующие действия:
- извлеките текущий номер из очереди.
- проверьте, соответствует ли текущий номер, если да, добавьте его в список
- найдите последнюю цифру текущего номера, выполнив % 10
- если последняя цифра равна 0, то с левой стороны не будет числа, отличающегося на 1, поэтому добавьте ((текущий номер * 10) + последняя цифра + 1 в очередь.
- если последняя цифра равна 9, то с правой стороны не будет числа, отличающегося на 1, поэтому добавьте ((текущий номер * 10) + последняя цифра - 1 в очередь.
- для всех остальных последних цифр может быть одно число слева и одно справа. ie (текущий номер * 10) + последняя цифра - 1 и (текущий номер * 10) + последняя цифра + 1 в очередь.

static void bfs(long n, int i, List results) {
        Queue queue = new LinkedList<>();
        queue.add(i);
        while (!queue.isEmpty()) {
            i = queue.poll();
            if (i <= n) {
                results.add(i);
                int lastDigit = i % 10;
                if (lastDigit == 0) {
                    queue.add((i * 10) + (lastDigit + 1));
                }
                else if (lastDigit == 9) {
                    queue.add((i * 10) + (lastDigit - 1));
                }
                else {
                    queue.add((i * 10) + (lastDigit + 1));
                    queue.add((i * 10) + (lastDigit - 1));
                }
            }
        }
    }

теперь наш список будет заполнен всеми прыгающими числами, все, что нам нужно сделать сейчас, это найти максимум из списка и вернуть ответ.

int max = Integer.MIN_VALUE;
for (int number : results) {
        max = Math.max(number, max);
}
return max;

Полный Код

class Solution {

    static void bfs(long n, int i, List results) {
        Queue queue = new LinkedList<>();
        queue.add(i);
        while (!queue.isEmpty()) {
            i = queue.poll();
            if (i <= n) {
                results.add(i);
                int lastDigit = i % 10;
                if (lastDigit == 0) {
                    queue.add((i * 10) + (lastDigit + 1));
                }
                else if (lastDigit == 9) {
                    queue.add((i * 10) + (lastDigit - 1));
                }
                else {
                    queue.add((i * 10) + (lastDigit + 1));
                    queue.add((i * 10) + (lastDigit - 1));
                }
            }
        }
    }

    static long jumpingNums(long n) {
        // code here
        if (n <= 10)
            return n;
        List results = new ArrayList<>();
        for (int i=0; i<10 && i <= n; i++) {
            bfs(n, i, results);
        }
        int max = Integer.MIN_VALUE;
        for (int number : results) {
            max = Math.max(number, max);
        }
        return max;
    }
}

Rohith v 07/LeetCode Топ-интервьювопросы

Leetcode Лучшие вопросы для интервью, обсуждаемые в Leetcode. Leetcode Лучшие вопросы для интервью, обсуждаемые в Leetcode.

Также ответ на вопрос от CodeSignal.com: https://app.codesignal.com/

Оригинал: “https://dev.to/rohithv07/jumping-numbers-44ob”