Всем привет. Сегодня у нас вот такая задача. Нам дан двумерный массив, который надо повернуть на 90 градусов. При этом нельзя создавать вспомогательный двумерный массив, нужно изменять исходный массив напрямую.
Задачу решили 80% разработчиков, которые взяли её решать. Посмотрим, сможем ли мы её решить?
Обдумываем задачу
Нам даны два примера.
Давайте на их примере обдумаем, как можно было бы хорошо повернуть такой массив.
Возьмём семёрку на углу. Эту семёрку нам нужно поставить на место единицы. Единицу нужно куда-то передвинуть, сделаем это по ходу движения, поставим её на место тройки. Тройку на место девятки, а девятку на место семёрки.
После таких действий ячейки по углам можно больше вообще не трогать, мы их все повернули.
Дальше те же самые действия делаем с 2 6 8 и 4. В итоге у нас остаётся 5, которая находится в центре.
С матрицей 4 на 4 чуть сложнее. Подобные действия нужно будет выполнить 5 раз. Возникают вопросы, а как посчитать, сколько нужно переставить элементов, как посчитать, в какое место их нужно передвинуть?
А что, если попробовать написать координаты этих ячеек, посмотреть, как они меняются, и вывести какую-нибудь формулу или алгоритм?
Когда мы поворачиваем матрицу на 90 градусов, наши ячейки переносятся на другие координаты. Можно попробовать сделать вторую матрицу, чтобы посмотреть, как меняются наши координаты. На жёлтой матрице показаны старые координаты передвинутых элементов.
Наши координаты меняются достаточно удобно для вычисления. X становится как Y, а Y почти как X, только координаты идут в другую сторону.
Это сильно помогает разобраться.
Если подумать, мы двигаем матрицу на 90 градусов, получается, нам нужно пройтись по одной четверти матрицы, а потом двигать эти ячейки по кругу (покажу чуть ниже)
Помните, мы не можем создавать вспомогательные матрицы, нам придётся гонять и переставлять эти ячейки по кругу внутри уже существующей матрицы
А размер у матрицы может быть чётным, а может быть нечётным, это тоже надо учитывать.
Мы создадим цикл, которым пройдёмся только по четверти матрицы. Это участок, который я разукрасил жёлтым. Каждый элемент из этого участка нужно будет переместить на другое место, как будто мы повернули матрицу на 90 градусов, а элемент оттуда снова переместить на другое место, и так 4 раза. Таким образом у нас получится вращение матрицы. Но только в матрице, у которой нечётная длина и высота, центр поворачивать не нужно.
В общем, работаем с этими элементами
Если посмотреть в условия, у нас есть только одна n-ка, которая задаёт длину стенки матрицы, из чего можно сделать вывод, что матрица может быть только квадратная, что упрощает задачу.
Так, ну а теперь можно приступать к написанию кода
Пишем код
Поделим нашу матрицу, возьмём от неё четверть и пройдёмся по ней циклом
Создадим две переменные, в одну запишем длину стороны массива, в другую половину от этой длины. Если будет ситуация, где длина нечётная, то это число округлится в большую сторону. (Например, 5 / 2 = 2.5; n2 = 3)
Создадим цикл, который будет проходиться по этой четверти.
Смотрим на эту таблицу. Если мы повернём матрицу на 90 градусов, то наши ячейки поменяют своё местоположение. В жёлтой таблице указаны их изначальные координаты.
Наш X превращается в Y, а Y в X, но идёт наоборот.
Попытаемся узнать координаты будущей ячейки, после переворота. Например так.
После переворота наш Y получает значение от X, а X это 3 - Y.
Смотрим ещё пример
Y = x
X = 3 - y
X, Y - новые координаты
x, y - координаты первоначальной ячейки
Можем ещё рассмотреть пример
Y = x. Y = 3
X = 3 - y. X = 3 - 1 = 2.
То есть X = (n - 1) - y
Получается, мы нашли формулы, по которым можно угадывать расположение ячейки после поворота. Мы можем двигаться дальше.
Пишем код.
На этом шаге мы в i записали значение из второй ячейки, а во вторую ячейку записали первую.
Теперь нам нужно перейти из второй ячейки в третью.
Нам нужно взять наши формулы и сделать из них новые
Y = x
X = (n - 1) - y.
Если их прогнать снова через себя же, будет так:
Y = (n - 1) - y
X = (n - 1) - x
Проверим это на табличке
Y = 3 - 1 = 2
X = 3 - 0 = 3
Да, всё верно. Замечательно!!
Записываем код для замены третьей ячейки. Я решил, что нам нужно ввести ещё одну вспомогательную переменную j
Если кто не понял, покажу на картинке, что мы сделали
Теперь эту j = 12 нужно перенести в другую ячейку.
Есть формулы для поворота на 90 градусов:
Y = x
X = 3 - y
Есть формулы третьей ячейки:
Y = (n - 1) - y
X = (n - 1) - x
Поворачиваем
Y = (n - 1) - x
X = (n - 1) - (3 - y) = n - 1 - 3 + y = n - 4 + y
Надеюсь, работать будет
Теперь самое простое, загружаем нашу i в первую ячейку
Запускаем. Я думаю, ошибки будут.
Ошибки всё таки есть. Наш код умудрился решить первый кейс, но дальше возникают трудности
Я ожидал чего угодно, но не такого 😨
Так, давайте думать, что же произошло. Я заинтересовался числом 2, каким образом оно оказалось в углу?
У нас проблема в последней формуле, из за неё наше число уходит в угол. Сама двойка становится на своё место при первых итерациях цикла, но эту двойку потом уносят другие числа.
Попробую чисто на глаз решить. Из Y нужно ещё одну единичку вычесть, чтобы восьмёрка встала на место. 😁
Y = n - 2 - x
Теперь у нас первый кейс не решается. Ничего страшного
А вот это совсем нонсенс.
Зелёным я пометил ячейки, которые правильно перевернулись.
Попробую посмотреть, что происходит с первой ячейкой (их всего 4)
Да уж. Лучше переписать последнюю формулу, она всё ломает постоянно...
Я подумал, а давайте лучше все формулы переделаем? Что-то здесь не чисто...
Формула координат для первого поворота:
Y = x
X = (n - 1) - y
Формула координат для второго поворота:
Y = (n - 1) - y
X = (n - 1) - x
Формула координат для третьего поворота:
Y = (n - 1) - x
X = (n - 1) - ((n - 1) - y) = n - 1 - n + 1 + y = y
Формула координат для четвёртого поворота:
Y = y
X = (n - 1) - ((n - 1) - x) = n - 1 - n + 1 + x = x
(Так, так это же конец, действительно получается x и y. Если мы в конце получили x и y, значит мы всё сделали правильно)
Да, мы сдвинулись с места!! Наш код смог решить 12 кейсов
Забавно получается. Правильно повернулись только элементы по диагонали. И что самое интересное, в первом или во втором кейсе была абсолютно такая же задача, которая почему-то решилась...
Небольшое отступление: В своих статьях я не пытаюсь показать безупречное идеальное решение. Я также показываю и процесс решения задач, свои размышления и попытки исправить ошибки. Я считаю, что это тоже может быть очень полезно, и из этого можно что-то для себя узнать. Так что не критикуйте меня за то, что я ошибаюсь и решаю ошибки при вас. Такова задумка моего блога...
Продолжаем.
Это очень странно. По расчётам получается всё нормально
Так, ну а теперь я начал понимать. Теперь ошибка не в формулах, теперь это чисто логическая ошибка. После того, как мы передвинули нашу четвёрку, начинается очередь восьмёрки, и она так же двигает наши ячейки, хотя это не требуется второй раз.
Получается, я ошибался, что можно циклом пройтись по этим областям.
Я сейчас считаю клеточки и понимаю, что в матрице с чётной длиной такая штука невозможна. Ячейки не накладываются друг на друга при вращении.
А вот с матрицей с нечётной длиной такое может быть. Линии по середине выбираются два раза и проходят по одному и тому же пути при повороте, поэтому одну линию нужно исключить.
У меня появилась идея. А если я заменю n2 на две переменные, ширина и высота для жёлтой области. Допустим, наша матрица ширины и высоты 5. Размеры для жёлтой области будут считаться так:
Ширина: делим 5 на 2, получается 2,5. Округляем до большего, получаем 3.
Высота: делим 5 на 2, получается 2,5. Округляем до меньшего, получаем 2.
Да, у нас получилось решить эту задачу
Но производительность оставляет желать лучшего.
Оптимизация
Ну что ж, приступим к оптимизации. Я думаю, нет смысла пытаться округлять n / 2. Если у нас будет матрица с чётным размером (6 на 6), округлять будет не нужно, мы потратим время на функцию. Лучше разделить код на два случая, когда размер матрицы чётный, и когда нечётный.
Так, думаем дальше.
В конце кода есть одна странная штука. Если подумать, она тоже отнимает какое-то количество ресурсов. В прошлой статье я делал цикл, который очень много считал и выводил данные через "console.log()", очень много выводил. Стоило было его убрать, производительность сильно улучшилась. Можно попробовать.
Да ладно!!
Нет, это LeetCode, он может чудить, перезапустим.
Даже после перезапуска
Иногда бывает такое, что LeetCode выдаёт разное время выполнения кода, от 0 до 5 мс, вполне может быть. Может быть такое, что ваш код медленный, выполняется за 5 мс, а на сайте произошла ошибка, и показало один раз, что 0 или 1 мс.
Я перезапустил код 4 раза, он всё ещё выдаёт 0 мс.
Получается, я решил задачу, и сделал код очень быстрым.
Закругляемся
Ну а наша задача подходит к концу. Кому понравилось, ставьте лайки, пишите комментарии и подписывайте друзей на мой канал. 😀
Всем удачи, всем пока