pattern heroPT–23LeetCode Extension

Обход матрицы

Считаем таблицу набором координат «строка, столбец» и находим формулу, куда переходит клетка. Тогда обход или поворот — это проход по клеткам по формуле, без лишних копий таблицы.

Вариант
P10 Обход матрицыСпираль · 1×

Пример задачи: прочитать матрицу 3 × 4 [[2, 7, 4, 9], [6, 0, 5, 3], [8, 11, 1, 10]] по спирали, по часовой стрелке от левого верхнего угла.

012301227496053811110результат
ещё не прочитанотолько что добавилив результатеответ

Начинаем с пустого результата

result = []top = –bottom = –left = –right = –
01/27
сначала · назад · пуск · шаг
Скорость
1function spiral(m):
2 result = []
3 top, bottom, left, right = edges of m
4 while top <= bottom and left <= right:
5 add top row, left to right
6 top = top + 1
7 add right column, top to bottom
8 right = right - 1
9 if top <= bottom and left <= right:
10 add bottom row, right to left
11 bottom = bottom - 1
12 add left column, bottom to top
13 left = left + 1
14 return result

← → шаг · пробел — пауза

Как узнать

двумерная сетка, которую обходят в необычном порядке (спираль, диагонали, слои), поворачивают или отражают, или меняют на месте с O(1) доп. памяти: поворот, обнуление строк, «Жизнь», проверка судоку.

Как решать такие задачи

  1. Запиши, что меняется на каждом шаге: какой индекс движется, а какой стоит на месте.
  2. Описывай оставшуюся часть простыми границами: четыре границы для спирали, номер слоя для колец.
  3. После каждой стороны или прохода сужай границы и проверяй, что они не пересеклись, прежде чем идти дальше.
  4. Проверь матрицу 1 × n и n × 1: ошибки на единицу вылезают именно там.

Вариант: Поворот

То же, но таблицу поворачиваем на месте. Поворот раскладывается на два отражения, а каждое отражение — это обмен клеток парами, поэтому вторая таблица не нужна.

  1. Запиши формулой, куда идёт клетка, и найди отражения, из которых она складывается: транспонирование, разворот строк, разворот столбцов.
  2. Меняй пары так, чтобы каждую пройти один раз: при транспонировании — только клетки правее диагонали.
  3. Чтобы пометить строки и столбцы на месте (обнуление матрицы), храни пометки в первой строке и первом столбце, а то, был ли ноль в них самих, запомни отдельно.
  4. Если каждой клетке нужны старые значения соседей («Жизнь»), храни старое и новое состояние в одной клетке: 2 — была живой, стала мёртвой; 3 — была мёртвой, стала живой. Расшифруй вторым проходом.

Где встречается

  • Картинки в памяти. Несжатую картинку обычно хранят одной длинной строкой пикселей, ряд за рядом. Пиксель в ряду y и столбце x лежит на месте y × ширина + x.
  • NumPy. NumPy хранит таблицу как один ряд чисел плюс два шага: на сколько прыгать к следующей строке и к следующему столбцу. Транспонирование просто меняет шаги местами, данные не копируются.
  • Поворот фотографий. jpegtran поворачивает JPEG на 90° без потери качества: транспонирует и отражает блоки, из которых состоит картинка, а не сжимает её заново.