Spiral Matrix

СреднеМатематика и моделирование Массивы и строки

+10

Дана матрица целых чисел с m строками и n столбцами, представленная в виде списка строк. Верните все её значения в порядке обхода по спирали.

Начните с верхнего левого угла и двигайтесь вправо вдоль верхней строки, затем вниз вдоль правого столбца, влево вдоль нижней строки и вверх вдоль левого столбца. Продолжайте двигаться по часовой стрелке, постепенно приближаясь к центру, пока каждое значение не будет прочитано ровно один раз.

Функция

spiralOrder(matrix: integer-2d-array) → integer-array

matrixinteger-2d-array: сетка целых чисел в виде списка строк одинаковой длины
Возвращаетinteger-array: каждое значение матрицы по спирали по часовой стрелке, начиная с верхнего левого угла

Ограничения

1 ≤ m, n ≤ 80, где m = matrix.length и n = matrix[i].length
Каждая строка имеет одинаковую длину n.
-100 ≤ matrix[i][j] ≤ 100

Примеры

Ввод: matrix = [[1, 2, 3], [10, 11, 4], [9, 12, 5], [8, 7, 6]]
Вывод: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
Пояснение: Значения возрастают вдоль спирали. Во внешнем кольце сверху расположены 1, 2, 3, справа вниз идут 4, 5, 6, по низу обратно — 7, 8, а слева вверх — 9, 10. Внутренний слой — это один столбец, который читается один раз сверху вниз: 11, 12.

Ввод: matrix = [[7, 1, 5, 3], [2, 9, -4, 6], [8, 0, 4, -1]]
Вывод: [7, 1, 5, 3, 6, -1, 4, 0, 8, 2, 9, -4]
Пояснение: Внешнее кольцо дает 7, 1, 5, 3, затем 6, -1 вниз по правой стороне, 4, 0, 8 обратно вдоль нижней стороны и 2 вверх по левой. Остается единственная строка 9, -4, которую нужно прочитать один раз слева направо.

+15 скрытых тестов при отправке

Дополнительный вопрос

Можешь вместо этого вернуть значения против часовой стрелки, начиная с верхнего левого угла и сначала проходя вниз по левому столбцу?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Здесь нет никакой хитрой математики; проблема заключается в учёте, и именно на этом этапе решения дают сбой. Каждый угол нужно обработать один раз, а не дважды, а самый внутренний слой может состоять из одной строки или одного столбца, и полный обход в этом случае снова пройдёт по тем же значениям. Можно двигаться как робот, который поворачивает направо, когда путь перекрыт, и запоминает, какие ячейки он уже обработал. Или можно снимать с матрицы по одному кольцу за раз, используя четыре сужающиеся границы; для этого не требуется дополнительная память.

Идите и поворачивайте направо, когда путь преграждён

Идея

Представь путника в верхней левой ячейке, который смотрит направо. Он считывает ячейку, на которой стоит, а затем пытается шагнуть вперёд. Если этот шаг выведет его за пределы матрицы или приведёт в уже считанную ячейку, он поворачивает направо (направо, вниз, налево, вверх, а затем снова направо) и шагает в этом направлении. Это правило задаёт спираль: края матрицы останавливают первый виток, а уже считанные ячейки становятся стенами для всех последующих витков.

Храни направление как индекс d в двух небольших массивах dr = [0, 1, 0, -1] и dc = [1, 0, -1, 0], так что поворот направо — это d = (d+1) % 4. Создай логическую сетку seen размером с матрицу. В первом примере путник считывает 1, 2, 3, доходит до правого края и поворачивает вниз, чтобы считать 4, 5, 6, поворачивает налево, чтобы считать 7, 8, и вверх, чтобы считать 9, 10. Над 10 находится 1, уже считанная ячейка, поэтому путник поворачивает направо и попадает на 11. Справа от 11 находится 4, уже считанная ячейка, поэтому путник поворачивает вниз и попадает на 12.

Выполни цикл ровно m × n раз — по одному разу для каждой ячейки, — и тебе не придётся определять конец обхода. После последнего считывания путник может смотреть на стену, но больше он не шагает. Каждая ячейка считывается один раз, поэтому время работы составляет O(m × n). Сетка seen требует дополнительной памяти O(m × n), от которой позволяет избавиться следующий подход.

Алгоритм

Начни со строки 0, столбца 0, лицом вправо, с сеткой seen, в которой все значения равны false.
Повтори m × n раз: добавь текущее значение и отметь его ячейку как посещённую.
Вычисли следующую ячейку в текущем направлении. Если она находится за пределами матрицы или уже посещена, поверни направо и вычисли её снова.
Перейди в эту ячейку.
Верни значения в том порядке, в котором ты их добавлял.

def spiralOrder(matrix):
    rows, cols = len(matrix), len(matrix[0])
    seen = [[False] * cols for _ in range(rows)]
    # Directions in clockwise order: right, down, left, up.
    dr = [0, 1, 0, -1]
    dc = [1, 0, -1, 0]
    r = c = d = 0
    result = []
    for _ in range(rows * cols):
        result.append(matrix[r][c])
        seen[r][c] = True
        nr, nc = r + dr[d], c + dc[d]
        # Blocked by the edge or by a cell already read: turn right.
        if not (0 <= nr < rows and 0 <= nc < cols) or seen[nr][nc]:
            d = (d + 1) % 4
            nr, nc = r + dr[d], c + dc[d]
        r, c = nr, nc
    return result

Снимите слои с помощью четырёх границ

Идея

Спираль — это набор вложенных колец. Опишите текущее кольцо четырьмя границами: строки от top до bottom, столбцы от left до right. За один обход считайте верхнюю строку от left до right, правый столбец — от top+1 вниз до bottom, нижнюю строку — от right-1 обратно до left, а левый столбец — от bottom-1 вверх до top+1. Каждая сторона начинается на одну ячейку дальше конца предыдущей стороны, поэтому каждый угол считывается ровно один раз. Затем сдвиньте все четыре границы на один шаг внутрь и повторяйте, пока top ≤ bottom и left ≤ right.

Ловушка — кольцо толщиной всего в одну строку или один столбец, где обратный проход проходит по уже считанным ячейкам. Во втором примере после обхода внешнего кольца границы такие: top = bottom = 1, left = 1 и right = 2: единственная строка 9, -4. Верхняя строка считывает оба значения, а в правом столбце ниже top ячеек нет. Но нижняя строка — это та же строка, и обратный проход по ней добавил бы 9 во второй раз. Поэтому проходите по нижней строке и левому столбцу только при условии top < bottom и left < right. Третий пример — зеркальный случай: в единственном столбце 4, 1, 7 обратный проход вверх по левому столбцу считал бы 1 повторно.

Каждое значение считывается один раз, поэтому временная сложность равна O(m × n) — меньше быть не может, поскольку ответ содержит все значения. Помимо памяти для ответа, требуются четыре целых числа.

Алгоритм

Установите top = 0, bottom = m-1, left = 0, right = n-1.
Пока top ≤ bottom и left ≤ right, прочитайте верхнюю строку от left до right и правый столбец от top+1 до bottom.
Если top < bottom и left < right, прочитайте нижнюю строку от right-1 до left и левый столбец от bottom-1 до top+1.
Увеличьте top и left на единицу, уменьшите bottom и right на единицу.
Верните значения в том порядке, в котором вы их прочитали.

def spiralOrder(matrix):
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1
    result = []
    while top <= bottom and left <= right:
        # Top row, left to right, then right column, top to bottom.
        for c in range(left, right + 1):
            result.append(matrix[top][c])
        for r in range(top + 1, bottom + 1):
            result.append(matrix[r][right])
        # A layer one row or one column thick has no way back:
        # walking back would read the same cells again.
        if top < bottom and left < right:
            # Bottom row, right to left, then left column, bottom to top.
            for c in range(right - 1, left - 1, -1):
                result.append(matrix[bottom][c])
            for r in range(bottom - 1, top, -1):
                result.append(matrix[r][left])
        # Step in to the next layer.
        top += 1
        bottom -= 1
        left += 1
        right -= 1
    return result

Ловушки и крайние случаи

Циклы короткие, поэтому ошибки возникают в углах и на последнем слое.

Повторное чтение последнего слоя, если он состоит из одной строки или одного столбца. Без проверки top < bottom и left < right второй пример заканчивается последовательностью 9, -4, 9, а третий считывает 4, 1, 7, 1.
Повторное чтение угла. Если каждая сторона проходит от своей первой ячейки до своей последней, каждый угол считывается двумя сторонами. Начинайте каждую сторону на одну ячейку дальше того места, где закончилась предыдущая.
Цикл с условием top < bottom вместо top ≤ bottom. Он останавливается, не доходя до середины нечётного квадрата: в матрице 3 × 3 центральное значение никогда не считывается.
Путаница между строками и столбцами в неквадратной матрице. Использование matrix.length для обеих границ работает на всех квадратных тестах, но не сработает для матрицы 3 × 4.
Не забывайте о матрицах малого размера: одна строка, один столбец, одна ячейка. Каждая из них — это один слой, который никогда не доходит до нижней строки или левого столбца.
В R a:b отсчитывает в обратном направлении, когда a > b, поэтому пустой диапазон, например 3:2, даёт 3, 2 вместо пустого результата; добавьте проверку или используйте seq_len. В Lua и R строки и столбцы начинаются с 1.

Частые вопросы4

Какова временная и пространственная сложность задачи «Спиральная матрица»?

Оба подхода считывают каждое значение один раз, поэтому время работы составляет O(m × n), и ни одно решение не может работать быстрее, потому что ответ содержит каждое значение. Для послойного обхода с четырьмя границами требуется O(1) дополнительной памяти помимо памяти для ответа. Для обхода с поворотом при блокировке требуется сетка размером O(m × n), чтобы запоминать, какие ячейки уже считаны.

Как избежать повторного чтения значения при обходе по спирали?

Повторы возникают в двух местах. В углах начинайте каждую сторону на одну ячейку после той, на которой закончилась предыдущая сторона, чтобы каждый угол относился только к одной стороне. В последнем слое считывайте нижнюю строку и левый столбец только тогда, когда в слое больше одной строки и больше одного столбца, поскольку в противном случае обратный путь проходит по ячейкам, которые вы уже считали.

Как заполнить матрицу по спирали, а не читать её?

Используй те же четыре границы и те же четыре стороны, но записывай вместо чтения. Веди счётчик, который начинается с 1, и записывай его в каждую ячейку по мере прохода, каждый раз увеличивая на единицу. Для матрицы n × n счётчик заканчивает на значении n², и первый пример выше показывает результат для сетки 4 × 3.

Почему поворот направо при препятствии приводит к спирали?

На первом круге обходчик поворачивает у четырёх краёв матрицы. На каждом следующем круге клетки, считанные до этого, становятся стенами, поэтому каждый круг поворачивает на одну клетку раньше кольца, которое он обошёл в прошлый раз. Так каждый круг остаётся внутри предыдущего — получается спираль. Обходчику не нужно знать, на каком он слое, — только свободна ли следующая клетка.

Python

def spiralOrder(matrix):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

matrix = [[1, 2, 3], [10, 11, 4], [9, 12, 5], [8, 7, 6]]

Ожидается

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]