Всем привет, сегодня мы будем решать задачи по JavaScript на LeetCode.
Достаточно долго я этого не делал, так как делал посты про решение задач от нейросетей, где ИИ генерировал мне задачу на JS, а я её решал. Я посвятил этому 9 статей, кому интересно, можете посмотреть.
А задачам по LeetCode уделил всего 8 статей. Надо это исправлять...
Давайте выберем какую-нибудь интересную задачку и начнём...
Задача: число островов
Очень быстро я пролистал список задачек и случайно нашёл очень интересную задачу. Задача под номером 200. Смотрите
У нас есть массив из нулей и единиц. В этом массиве в виде нулей и единиц записана карта моря и суши.
Нам нужно написать код, который посчитает количество островов на этой карте.
Островом считаются ячейки, соединённые вертикально и горизонтально. По диагонали считаться не будут.
Вот так эта задача выглядит на LeetCode
Наша карта может быть до 300 клеток в высоту. Насчёт ширины не знаю, тут непонятно написано.
Задачу решило 64.4% программистов, которые за неё взялись.
Давайте приступать...
Начинаем размышления и обдумывание
Давайте ка подумаем, как можно решить эту задачу...
Нам нужен механизм, который может проходиться во всем клеткам фигуры из единиц. А ведь фигура может быть не только такой, как я показал вам на картинке.
Она может быть и такой. А ведь вот такое нечто тоже можно считать за остров...
И как это считать?
Можно написать код, который установит начальную точку на острове, а из этой точки будет идти во все возможные направления.
Те клетки, в которые он пришёл, он будет отмечать. Он будет заносить данные о них в другой массив.
[[3, 4], [5, 6], [1, 4]]
Этот код будет проходиться по всей карте (массиву), в каждой клетке ставить начальную точку, и из неё проходиться по всей доступной территории.
По клеткам он будет перемещаться разными путями, и важно помечать, где он уже был. Как только цикл, перебирающий ячейки карты, попадёт начальной точной на остров, другая функция с кодом пройдётся по нему полностью
При следующем перемещении начальной точки на остров, где мы уже были, код не будет срабатывать, и остров не будет сканироваться дважды. Каждый остров сканируется только один раз. Ко всему этому останется только добавить счётчик и вывести данные из функции.
Получается вот так. На этой картинке 4 острова.
Кстати, могут быть ещё такие острова
Этот код от начальной точки должен уметь проходить во всех направлениях, вверх, вниз, влево и вправо. Если бы острова были только квадратные, было бы в разы проще. А они могут быть самых разных и странных форм, и нужно уметь ходить по всем этим "крючкам".
Это красиво только в теории. А как реализовывать это на практике?
Давайте думать
Пишем код, решаем на практике
Зададим ширину и высоту карты в переменные, чтобы каждый раз не пересчитывать и сэкономить ресурсы.
Делаем цикл, который будет проходиться по карте и устанавливать точки, из которых он будет проходиться по острову (как на моей схеме)
Если точка попала в элемент "0", то есть в воду, код для прохождения по острову прервётся, и точка просто переместится дальше.
Теперь нужно сделать так, чтобы код проходился по всем ячейкам острова.
Наши острова, в теории, могут быть самой разной причудливой формы. Нам нужно, чтобы наш код обошёл все ячейки. Нужно сделать так, чтобы вот эти стрелочки могли раздваиваться. Я думаю, сделать это как-то в виде рекурсивных функций.
Я сейчас столкнулся с проблемой. А как проверить, что мы побывали в той точке? Допустим, наши точки с координатами записаны в массив вот так:
[[1, 1], [2, 1], [3, 1]]
Через функцию "includes", если в массив поместить массив, сделать это не получится...
Он не умеет сравнивать массивы... Не получится сделать массив из массивов...
Придумал, а если помещать координаты в виде строк?
Я не знаю, насколько это верное решение, и как это скажется на оптимизации в дальнейшем. Но нужно пробовать...
У нас есть массив "mass" с координатами ячеек, где мы были. При каждом попадании в ячейку в массив будут записываться её координаты в виде строки типа "x-y". Например, "2-1".
Это способ странный, я не знаю, как это скажется на оптимизации. Но я люблю придумывать странные необычные способы 😁.
Вот, начинается рекурсия. Я создал функцию "go_mass", которая будет проходиться по ячейкам острова. Функция внутри функции. Пока я её не доделал, она проходится только вправо. Объясняю, как она работает...
В цикле мы вызываем функцию для прохождения по острову и задаём координаты "x + 1, y", чтобы он вправо шёл. В функции проверяем, не выходят ли индексы за границы массива, иначе ошибка в коде будет. Проверяем, не попали ли мы в воду. Проверяем, были ли мы когда-то в этой ячейке. Если не были, записываем её в массив и вызываем эту функцию ещё раз. Если же эти условия не выполняются, функция просто остановится.
Графически это выглядит так. Я заметил, если людям объяснять информацию графически, они лучше понимают, и им нравится 😁.
У нас в задаче есть пример, на котором это можно проверить
Я выведу наш массив в консоль для самопроверки, как работает функция.
Так... Смотрим...
У нас в массив были записаны одни и те же ячейки. А так быть не должно, память надо экономить. (Я выделил более жирно те ячейки, где мы были несколько раз).
Добавим проверку
А теперь у нас вот так...
Не обращайте внимание на "Wrong Answer", мы пока ответ не выводим, а только проверяем нужные данные.
И ячейки у нас выделились так. Функция "go_mass" прошлась вправо и завершилась. Потом цикл перенёс нас на Y = 1, вниз. Там он выделил ячейки и так далее...
Единственное, что меня смущает, что он не дошёл до оставшейся зелёной ячейки
Я попробовал вывести координаты и понял, что цикл по координате X не идёт дальше, а переходит на следующую строку.
Я напутал с "break", он не итерацию прерывает, а весь цикл... Ну, бывает...
Можно так сделать...
Так, смотрим...
Кружки, это точки, откуда наш цикл начинает сканирование острова, я их буду называть "начальные точки", а синее это ячейки, по которым он прошёлся. Пока нормально. Только вот начальная точка на каждом острове должна быть одна. А мы пока тестируем функцию с ограниченным функционалом, она двигается только вправо. Нужно доработать функцию, и начальная точка будет одна.
Функция теперь будет ходить не только вправо, но и во все стороны
И здесь сделаем также. Хоть бы не сломалась... 😅
Тестим.
Она не сломалась, надо же. Теперь у нас есть только одна точка, из которой код проходится по всем ячейкам острова.
Замечательно. Для лучшего понимания, покажу вам, как код проходится по этим ячейкам.
Надеюсь, понятно. Короче, он ходит во все стороны, но не может идти туда, где был.
Теперь нам нужно добавить счётчик и вывести его результат из функции.
Запускаем...
Да, код работает!!
На самом деле, я не думал, что смогу так быстро его написать. Мне казалось, задача будет сложной.
Ну что сказать... Опыт 😁😎...
Давайте посмотрим на более большой выборке данных, как будет работать наш код.
Так... Ага...
Так уж получается, что на LeetCode время выполнения кода ограничено. Мало того, что в конце задачи мне придётся соревноваться с другими разработчиками по времени выполнения кода, так ещё и рамки есть, минимум времени, за которое должен выполняться код...
А мне такое нравится 😁
Я что-то слышал про спортивное программирование, там пишут крутой и оптимизированный код. Слышал об этом я очень мало, но хотелось бы поучаствовать в чём-то подобном 😀.
Давайте смотреть, что же не так в нашем коде
Приступаем к оптимизации
Я думаю, надо оптимизировать вот эту штуку
Наша функция двигается по ячейкам сразу в четырёх направлениях, даже туда, откуда и пришла. Ну не нормально это...
Если передавать в качестве аргументов только координаты, куда мы перемещаемся, мы не сможем отслеживать направление. Нам нужно как-то передавать направление.
Можно добавить переменные "movex", "movey", которые будут смещать x и y на определённые позиции.
С таким подходом и условия проверки границ массива можно переписать и оптимизировать
Теперь у нас условия по проще. Больше у нас не проверяется одновременно, что x не перешёл левую и правую границу.
Оператор "||" (ИЛИ) работает так: он проверяет первое выражение, если оно верно, второе он не проверяет, так как здесь нужен хотя бы один "true". Это такая оптимизация от языка программирования.
Если мы двигаемся влево, идёт проверка, больше ли X, чем 0. Если вправо, проверяем, не выходим ли мы за правые границы. И с Y также.
.......................
Теперь сделаем новые переменные "x2" и "y2", где обычные "x" и "y" сложим с "movex", "movey", чтобы каждый раз не пересчитывать их.
Так, что-то мы дооптимизировались, что код вообще работать перестал
Давайте в консоль выведем, что же происходит там...
Так, клетки острова те же, что и были, зато начальных точек стало 9.
Я попробовал выводить в консоль массив "mass", каждое выполнение функции "go_mass", функция "go_mass()" перестала заполнять массив.
Я нашёл ошибку. Наш "movex" может быть не только меньше или больше нуля, он же сам может быть нулём. А у нас всегда либо "movex" ноль, либо "movey", поэтому она не работает.
Вот так.
Ещё ошибку нашёл, из "n" и "m" надо вычесть 1, чтобы границы нормально проверялись.
Проверяем код...
Код работает, но он всё равно не успевает, когда ему отправляешь большой массив.
Кстати, как показывает мне мой предыдущий опыт работы с LeetCode, все "console.log()" из кода лучше убрать, так как они тормозят.
Теперь делаем условие. Если мы двигаемся влево (movex = -1), то мы не ставим проверку, которая двигается вправо. Если мы двигаемся вправо (movex = 1), то мы не ставим проверку, которая двигается влево. То есть мы не двигаемся туда, откуда пришли.
Вот, код уже более оптимизирован, наш тестовый пример выполняется не за 47ms, а за 31ms, но через большой массив он всё ещё не может пройти...
Нужно искать другие способы оптимизации...
Нам нужно найти другой способ хранить наши данные, не в строке. Ну глупо это...
Нужно найти способ, чтобы хранить данные в массиве по две переменные в связке, и чтобы можно было быстро проверять наличие таких данных в массиве, желательно функцией от JS, как ".includes()".
Ладно, такую функцию можно написать и вручную.
Теперь мы будем хранить данные в массивах, то есть массив из двух значений в массиве:
[[1, 2], [4, 5], [3, 4]], типо такого.
Напишем простую функцию
Теперь переписываем наш код
Очень странно, а по такому способу наш код стал работать ещё медленнее. Хотя теперь ему нужно работать только с числами, должен быстрее...
Возможно работать с массивами из строк ["1-1", "2-1"] для кода легче, чем работать с массивами из массивов [[1, 1], [2, 1]].
Это в какой-то степени логично, в одномерном массиве по элементам перемещаться легче, чем в двумерном.
Я вот думаю, а можно ли как-то наш двумерный массив преобразовать в одномерный? Если сделать что-то вот такое: [1, 1, 2, 1]. Каждое число на нечётной позиции это x, а каждое число на чётной позиции, это y?
Я думаю, это может ускорить наш код...
Теперь у нашей функции будет три параметра, массив, x и y.
Так как наш массив теперь будет в два раза больше (вместо [x, y] будет x, y) делим нашу n на 2, и с ней запускаем цикл. За одну итерацию мы будем сравнивать сразу два объекта. Если они равны нашим координатам, функция выведет true, иначе false.
Соответственно, меняем механизм загрузки данных в массив
Даа!! Получилось!!!
Только вот у меня настолько неоптимизированный код, что я в каком-то хвосте плетусь. Вообще не порядок. 😡.
Кстати, мы можем здесь смотреть время выполнения задачи, не обязательно запускать тест на больших данных. Ладно, можно и так и так проверять.
Я пришёл к выводу, что когда мы двигаем по карте нашу начальную точку, нет смысла запускать функцию проверки острова влево, так как наша начальная точка там и так уже была. Да и вверх тогда не надо запускать, потому что наша начальная точка уже была вверху и проводила проверку из той точки.
То есть проверка из начальной точки проводиться будет только вправо и вниз, а уже из тех позиций во все стороны.
Я подумал, а если нам сделать не отдельный массив, по которому нам надо каждый раз проходиться и проверять, есть ли там нужная ячейка, а если сделать второй двумерный массив, состоящий из нулей, где мы нужные ячейки будем помечать единичками? Это как оригинальная карта, только дополнительная.
У этого решения есть плюсы. Во-первых, у такого массива будет фиксированный размер, и JavaScript не придётся его каждый раз перерасчитывать. Во-вторых поиск будет проходить достаточно быстро, просто по индексу.
По сути, когда мы в массив добавляем элементы (5, 6), компьютер удаляет старый массив [1, 2, 3, 4], перерасчитывает и делает новый массив [1, 2, 3, 4, 5, 6], а это отнимает время. Представьте, какой-нибудь огромный массив так перерасчитывать и добавлять в него элементы [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]. Думаю, в том огромном примере значений было гораздо больше.
Давайте попробуем. Создаём пустой массив и заполняем его нулями.
Ого, а так в разы быстрее проверять, были ли мы в ячейке.
А функцию "CoordinateInArray()" вообще можно удалить и не занимать память.
Да ладно!! Реально!?!? С 2000 с чем-то миллисекунд разогнаться до 56?? Чтооо??? 😨
Вот, что делают статичные двумерные массивы и дополнительные знания из языков С и Ассемблер!! 😎
О даа!! Такие задачки решать такой кайф!!
Я уже обошёл 81% разработчиков, но можно было и лучше 😃.
Ладно, сегодня у меня много дел, давайте на этом и закончим.
А на этом всё
Ну а на этом всё, подписывайтесь на канал и ставьте лайки 😀 👍