Где применяется
1. Задача
Матрица это таблица значений из строк и столбцов. Иногда нужно прочитать все клетки в определённом порядке или переставить каждую клетку на новое место. Для этого есть два классических приёма: прочитать таблицу по спирали по часовой стрелке и повернуть всю таблицу на четверть оборота по часовой стрелке.
Спираль: начни в левом верхнем углу, пройди верхнюю строку, спустись по правому столбцу, пройди нижнюю строку справа налево, поднимись по левому столбцу. Потом перейди на кольцо внутрь и сделай то же самое. Продолжай, пока каждая клетка не будет прочитана один раз.
Поворот: поверни таблицу на 90 градусов по часовой стрелке, чтобы верхняя строка оказалась правым столбцом.
В обоих приёмах ты идёшь по таблице по её устройству: помнишь, где сейчас края, и сдвигаешь их по ходу.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитspiralOrder([[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]])| 0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 |
| 1 | 5 | 6 | 7 | 8 |
| 2 | 9 | 10 | 11 | 12 |
| 3 | 13 | 14 | 15 | 16 |
Читаем матрицу по спирали. Четыре границы отмечают кольцо, которое ещё предстоит обойти: top, bottom, left и right.
Как узнать
Эти слова в условии значат этот паттерн
- прочитать или заполнить сетку по спирали
- обойти матрицу по диагоналям
- повернуть матрицу на 90 градусов
- посетить каждую ячейку в фиксированном геометрическом порядке
Похоже, но не то
- Поиск в матрице (отсортированная сетка) (Matrix search (sorted grid))
Там порядок используют, чтобы пропустить большую часть сетки. Здесь посещается каждая клетка.
- Поиск слова в матрице (DFS/backtracking по сетке) (Matrix word search (grid DFS/backtracking))
Там идёт перебор с откатом и разворотами. Здесь путь задан заранее.
- Обход графа BFS / DFS (Graph BFS / DFS)
Обход идёт по рёбрам из стартовой вершины. Здесь порядок задаёт геометрия.
- Преобразование массива на месте (In-place array transform)
Поворот матрицы на месте это та же идея в двух измерениях. Правило про один буфер то же самое.
Сетка r на c даёт O(rc), потому что каждая клетка посещается один раз. Память O(1) сверх ответа.
На LeetCode
Задачи на матрицу, где сетку читают или заполняют кольцо за кольцом или поворачивают на четверть оборота. Четыре маркера края обходят внешнее кольцо и сдвигаются внутрь, а поворот переводит клетку (i, j) в (j, R минус 1 минус i).
Скопируй клетку (i, j) в (j, i) в новой сетке, где строки и столбцы поменялись местами.
Поверни mat до четырёх раз через rotate90 из урока и сравнивай с target после каждого поворота.
Это spiralOrder из урока вместе с защитой от одиночной строки или столбца.
Те же четыре маркера обходят спираль и записывают числа от 1 до n^2.
LeetCode требует поворот на месте, так что транспонируй матрицу и потом разверни каждую строку.