Всем привет, сегодня мы снова решаем задачки на LeetCode с помощью JavaScript.
Сегодня у нас вот такая задача
Мы получаем строку, которая должна быть IP адресом, но она поломалась, и мы должны будем её восстановить.
Например, нам пришла строка "25525511135", а мы должны её восстановить и вывести все возможные IP адреса, например, "255.255.11.135" и "255.255.111.35".
Давайте попытаемся решить эту задачу
Погружаемся в размышления
IP адрес это четыре числа, разделённые точками, изменяющиеся от 0 до 255.
Посмотрим примеры
Нам нужно придумать способ, который будет разделять данную строку на числа для IP адреса.
Давайте посмотрим пример 3
Нам нужно сделать цикл, который будет проходиться по всей строке с числом и выбирать 4 числа разных размеров. Он будет перебирать размер числа в символах и проверять, будет ли это подходить.
Допустим, если из 101023 попытаться взять 4 числа по 1 знаку, будет остаток 23, это будет не правильно (картинка 1). А если мы из 101023 возьмём 4 числа, 3 из которых по 1 знаку, а последнее 3 знака, то получится IP адрес "1.0.1.23". (картинка 3)
Мы работали с самым последним числом IP адреса (я выделил его салатовым), и мы меняли его размер от 1 до 3, теперь будем работать с предпоследним числом (жёлтый цвет) и будем менять его размер от 1 до 3.
Таким образом мы получим ещё 2 IP адреса, "1.0.10.23" и "1.0.102.3".
Потом берём второе число (оранжевое) и меняем его размер от 1 до 3, там берём третье число (жёлтой) и четвёртое число (салатовое) и тоже меняем им размер. Перебираем возможные числа
Ну и так далее.
Вот по такому принципу мы будем проверять наши IP адреса. Давайте попробуем всё это реализовать в виде кода
Приступаем к решению
Сделаем четыре вложенных цикла, чтобы менять четыре области, которые я вам показал на схеме
Запишем в переменную длину строки
Нам нужно сделать так, чтобы четыре области, которые мы выбираем, по своему размеру были равны размеру строки.
Сделаем это условие. Мы будем суммировать длину четырёх областей и если она будет равна длине строки, тогда будем проводить какие-то действия
Так, в скобках "(i1 + 1)" выше я написал, чтобы было понятно. Единички можно сложить
Нам нужно получить первое число IP адреса. Давайте выведем первое число нашего IP адреса в консоль.
Давайте проверим, что получится, если мы сделаем так.
Код выводит нам числа "25" и "255", первое число, которое возможны в IP адресе "25525511135". И это правильно. Числа "2" быть не может, потому что даже если остальные числа будут максимальной длины, получится адрес "2.552.551.113", и остаток "5".
Кстати, совсем забыл, числа не должны быть больше 255.
Теперь попытаемся получить второе число. Если кто забыл, функция ".substr()" работает так: функция из строки берёт подстроку. Принимает два аргумента: позиция, откуда начинаем брать строку, и длина этой строки. (а я думал конечная позиция).
Чтобы получить второе число, нужно начать брать строку с позиции "i1 + 1", а длина должна быть "i2 + 1", так как наши i2 перебираются от 0 до 2, нужно прибавлять, чтобы получить нормальную длину.
И такие ответы верные, почти. Работу с числами, больше 255, как 525, будем вести потом.
А вот третье число будем получать так. Для начальной позиции нам надо сложить предыдущие две (i1 + 1) и (i2 + 1). Это будет "i1 + i2 + 2"
Правильно
Работа со строками такое дело, где всё нужно проверять, ошибиться легко. Поэтому каждый свой шаг я проверяю через "console.log()".
Вот, все числа правильные, если смотреть по их длине. Но если смотреть по величине, такие числа, как "511" не подходят.
И в примере это показано. Мы посчитали числа правильно, нужно только избавиться от чисел, которые больше "255".
Для этого нам нужно перевести их в int. После этого мы их проверим и обратно преобразуем в строку.
Там есть ещё такой момент: нам может попасться число с нулём спереди, как "011", а в IP адрес оно должно попасть, как ".11". Когда мы переводим строку в int, этот ноль должен исчезнуть. Наверное. Нужно проверить.
Преобразуем строки в числа, сделаем проверку, а потом сделаем из всего этого одну строку и вставим в массив. Я уберу "str1" и сделаю из них "num1".
И выведем это из функции
Вот блин... Я немного заработался с пайтоном и по привычке поставил ".append()". Такое бывает, когда пишешь на нескольких языках сразу.
Запустим проверку. У нас выполнилось правильно 2 кейса из 3.
А IP адреса "1.0.1.23" быть не может?
Вот это хороший момент для обдумывания... В этом моменте строка "023" превратилась в 23, и это стало ошибкой. Возможно, так нельзя делать, и лишние нули убирать нельзя. Получается, числа в IP не должны начинаться с нуля, если после этого самого нуля есть другие цифры.
Мы поспешили убрать "str" и сделать из них сразу num. Я предлагаю такой механизм: Сначала мы получаем строки, сохраняем их, потом получаем из них числа, сравниваем их с 255. Только потом мы возвращаемся к "str" и проверяем, если у них в начале "0".
Проверка будет такая, если первый символ строки "0", а у строки длина не равна 1, тогда этот символ неправильный, и IP адрес отвергается.
Для проверки я буду делать вот такие условия. Таких скобок будет 4 для каждого "str". У нас должна быть строка длины 1, если нет, эта строка не должна начинаться с 0.
И так 4 раза. Либо строка длины 1, либо в этой строке начало не 0. И всё это стоит в конструкции "() И () И () И ()".
Мне кажется, это может быть сложным для понимания, ну, вот так...
У нас получилось. Первые три тренировочных кейса были решены.
Теперь давайте посмотрим, что будет на более большой выборке входных данных.
Так, неплохо...
2 мс, 62% побитых рекордов. Это очень хорошо. Но я знаю, мы можем лучше 😁. Ооо, я так хочу попробовать спортивное программирование, я слышал, там нужно сделать крутой оптимизированный код. Но об этом я знаю очень мало.
Ладно, приступаем к оптимизации.
Приступаем к оптимизации
Можно ли оптимизировать эти циклы?
Наверное можно сделать какую-нибудь конструкцию, которая считает не 0-3, 0-3, 0-3, 0-3, а 0-12, а потом эти числа делит и получает нужный результат. Но как бы сам процесс такого деления и вычисления не съел нашу оптимизацию. Этот способ оставим на крайний случай, а пока попробуем что-нибудь менее радикальное.
Кстати, давайте для начала несколько раз запустим наш код и посмотрим его скорость. На LeetCode скорость бывает разная, она постоянно меняется. Поэтому нужно перепроверять и запускать его несколько раз.
Я запустил код ещё 4 раза (в сумме 5) и у нас такие результаты: два раза он выполнился за 3 мс, два раза за 2 мс, один раз за 1 мс. В итоге он выполняется за 1-3 мс.
Я думаю, надо оптимизировать что-то другое
Я заметил, сначала мы получаем строки, потом из них делаем числа, потом эти числа сравниваем, а потом проверяем строки.
А если сделать по-другому?
Если сначала получить строки и проверить эти самые строки, а потом получить числа и проверить числа?
То есть, если мы проверим строки, а они не подходят, мы не потратим лишнее время на получение чисел.
Вот так
Код начал выполняться даже медленнее. За 2-4 мс.
Я понял. Дело в том, что ситуаций, где число больше 255 намного больше, чем ситуаций, где строки "011". Поэтому раньше отсекалось много случаев, и код выполнялся быстрее.
Я придумал ещё способ. Вот наша проверка на нули в начале.
Я придумал другой способ.
При преобразовании такой строки, как "011" в int, получается 11. А почему бы просто не сравнить длину "str1" и "num1"?
Вот так. Только условий должно быть 4.
Код не ускорился.
А вот если сравнить их вот так, код работает быстро
Я запустил код 4 раза, он выполняется от 0 до 1 мс.
1 раз за 0 мс, 3 раза за 1 мс.
Довольно быстро, но нужно ещё лучше.
У меня есть ещё мысль, что можно оптимизировать. У нас числа в виде int складываются со строками "." и всё это преобразовывается в строки. Это неявное преобразование. А если нам преобразовать int вручную в string?
Иногда, если написать какие-то функции вручную, вместо использования встроенных функций от языка программирования, может получиться быстрее. Язык программирования же сначала считывает, что у них разные типы, int и string, потом он подбирает, какой способ преобразования использовать (для int, float), потом он делает какие-либо проверки, преобразовывает типы и складывает.
Поэтому я хочу попробовать сразу их преобразовать и сложить.
Очень странно, код даже замедлился. Возможно, у JS способ преобразования работает как-то быстрее. Этого я точно не знаю.
Алиса AI пишет, что неявное преобразование действительно быстрее. Я понимаю, что лучше не доверять всегда нейропоиску, а перепроверять по реальным источникам, но у нас есть реальный рабочий пример, который подтверждает этот ответ.
У меня идея. Если мы проверили числа и сделали невозможным использование чисел типа "012" в IP, тогда мы можем без проблем подставлять "str1" подставлять напрямую сразу, без каких-либо преобразований.
Я не делал этого, чтобы у нас не было адреса, типа "255.012", но мы исключили эту возможность, и теперь можно туда напрямую добавить "str2".
Странно. Сделали вроде бы проще, по идее, а код выполняется не 1 мс, а 2мс. Сайт зависает что ли?
Есть ещё один способ. У нас каждую итерацию цикла заново объявляется переменная через "let". А это дополнительная нагрузка на вычислительное устройство.
Более хорошим способом будет объявить переменные вне цикла, а уже в самом цикле с ними работать.
Когда мы объявляем переменную, для неё выделяется место в памяти. И каждую итерацию цикла мы объявляем место в памяти для 8 переменных. У нас 4 вложенных цикла, по 3 итерации каждый, в итоге итераций 81. 81 * 8 = 648 объявлений переменной в памяти, что добавляет нагрузки.
И мы достаточно хорошо разогнали наш код
Код выполняется от 0 до 2 мс. Я запустил его 7 раз, 3 раза он отработал за 0 мс, 4 раза за 2 мс. Ещё не идеально 0 мс, но значение 0 мс уже начало появляться чаще.
Кстати, можно не объявлять "i1", "i2", "i3", "i4" каждую итерацию цикла, а тоже вынести их за пределы.
Уже чуть лучше
Мне кажется подозрительным этот способ. Давайте всё же его перепишем и напишем что-то ещё более лёгкое
Сравнение элементов таким способом будет более долгое, вернёмся к старому способу, но поменяем его
Я понял, что необязательно получать длину строки через "str1.length", для этого же есть переменные "i1", "i2", "i3", "i4".
Код также выполняется за 0-2 мс.
Я понял ещё кое что. Если нам постоянно приходится прибавлять 1, почему бы не перебирать числа от 1 до 3, а не от 0 до 2?
Запустил код 6 раз, 4 раза за 0 мс, 2 раза за 1 мс.
Очень хорошо. Мы оптимизировали наш код
Подведём итоги
На этом всё. Мы написали код, который восстанавливает IP адрес и выдаёт все возможные варианты.
И да, сейчас я понял, что было бы странным не показать результаты его работы.
Ну а на этом всё, подписывайтесь на канал и ставьте лайки 😃😁.