Где применяется
1. Задача
У тебя есть сетка чисел. Надо выписать все её клетки в один плоский список, проходя сетку по диагоналям. Направление чередуется: одну диагональ читаешь снизу вверх, следующую сверху вниз.
Для [[1,2,3],[4,5,6],[7,8,9]] ответ [1,2,4,7,5,3,6,8,9]. Вся задача в том, чтобы правильно пройти этот зигзаг.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитКак узнать
Эти слова в условии значат этот паттерн
- прочитать или заполнить сетку по спирали
- обойти матрицу по диагоналям
- повернуть матрицу на 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
Задачи на матрицу, где клетки читают или группируют по диагоналям. У клеток одной диагонали общая сумма r + c, а у диагоналей другого направления общая разность r минус c, так что любое из этих чисел годится как ключ.
На главной диагонали r равно c, на другой r + c равно n минус 1. Центр считай один раз, если n нечётное.
Каждая клетка должна быть равна соседке слева сверху, ведь обе лежат на одной диагонали r минус c.
Это diagonalOrder из урока. Чётные диагонали идут вверх, нечётные вниз.
Строки разной длины, так что клади каждую клетку в корзину по r + c, начиная с нижней строки, и читай корзины по порядку.
Собери каждую диагональ r минус c, отсортируй и запиши обратно в те же клетки.