Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания
СегодняСтатья 32 Темы LeetCodeВ статье мы рассматриваем 54-й вопрос LeetCode — Spiral Matrix.
Прежде всего объясните смысл вопроса.Это Спираль означает спираль.Говорят,что в английской версии комикса Спиральная Пилюля Наруто переводится как Спиральная Сфера...
Уходи, вернись к делу. Через спиральную таблетку мы все знаем, что означает спираль, поэтому так называемая спиральная матрица — это обход массива или матрицы в порядке спирали. Мы можем посмотреть на картинку ниже:
Порядок стрел — это порядок спиралей, а то, о чем мы спрашиваем в этом вопросе, — результат прохождения по порядку спиралей.
задний план
Смысл этого вопроса очень прост, я думаю, его сможет понять каждый, но если вы действительно хотите начать, то обнаружите, что это довольно сложно. Основная трудность в том, что мыПорядок обхода постоянно меняется, меняется и скорость изменений. В какой-то степени эти изменения прослеживаются, но даже при этом абстрагироваться от этих законов и писать простой и понятный код без ошибок непросто.
Если я правильно помню, на школьном конкурсе ACM на втором курсе был вопрос, точно такой же, как и исходный вопрос. Хотя это очень просто и все знают, как это сделать, финальный проходной балл не высок.
Это не совсем злой умысел спрашивающего, на самом деле такого рода проблемы до сих пор очень распространены на соревнованиях по акм. Часто есть какие-то темы, которые очень четкие и понятные, и вам нужно следить только за теми темами, которые можно реализовать. Это игроки, которые расследуютАбстракция и способность кодировать, хотя смысл вопроса не сложный, но все равно очень сложно быстро написать программу с сотнями строк, содержащую ряд сложной логики без багов в напряжённой сцене соревнований. Поскольку ключ к этому типу вопросов заключается в том, чтобы позволить нам имитировать смысл вопроса, его также называют вопросом-симулятором.
Если вы хотите написать этот вопрос гладко, вам нужен очень распространенный навык или соглашение, которое также является ключом к этой статье.
массив направлений
Среди многих задач мы часто сталкиваемся с такой задачей, например, нам нужно пройти лабиринт, и нам нужно двигаться в направлении вверх, вниз, влево, вправо, юг, юг и север в реальном мире. В процессе движения естественно задействованы различные направления, поэтому нам нужно использовать код для представления направления.
Например, когда мы рисуем злодея, его координаты (x, y), и у него есть четыре направления на выбор. Мы предполагаем, что он каждый раз перемещается на единицу расстояния, и мы можем легко получить новые координаты после того, как он переместится во всех направлениях.
Согласно математическому определению вектора, мы можем записать единичный вектор этих четырех направлений: [0, 1], [0, -1], [1, 0], [-1, 0].
Мы сохраняем эти векторы в постоянный массив и получаем массив направлений. Когда нам нужно пройти по всем направлениям, нам нужно пройти только по этому массиву.
Мало того, что если у нас есть требования к порядку обхода направлений, его еще и можно добиться. Например, в этом вопросе мы можем обнаружить, что обход спиралиКаждый раз, когда порядок изменяется, он фактически поворачивается на 90 градусов влево..
Вращение, которое первоначально было направлено на восток, стало югом, юг стал западом, запад стал севером, а север стал востоком. Затем нам нужно только расположить направления в порядке юго-восток, северо-запад, и каждый раз мы увеличиваем нижний индекс массива направлений на один бит и берем по модулю 4, чтобы получить следующее направление.
Этот прием несложно понять, но он может значительно упростить наш код.
отвечать
После понимания массива направлений, остальное намного проще.Давайте рассмотрим процесс обхода спирали выше.Хотя длина каждого обхода смены направления разная,ноПричина каждого изменения одна и та же, то есть это направление пройдено до конца, значит надо изменить направление. На самом деле это очень легко понять, нам нужно только поддерживать конечную точку в каждом направлении и менять направление каждый раз, когда мы достигаем конечной точки. Поскольку количество элементов в матрице фиксировано, мы знаем количество обходов, поэтому, пока обрабатывается изменение направления, эта проблема будет решена.
Давайте посмотрим на код:
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
# 定义方向数组
fx = [[0, 1], [1, 0], [0, -1], [-1, 0]]
n = len(matrix)
if n == 0:
return []
m = len(matrix[0])
ret = []
# 定义边界数组
# 边界数组和旋转的顺序也是对应的
# 第一次旋转之后上边界+1，所以第0位是上边界
# 第二次旋转之后，右边界-1
# 以此类推
condition = [0, m-1, n-1, 0]
x, y, dt = 0, 0, 0
for i in range(n * m):
ret.append(matrix[x][y])
x_, y_ = x + fx[dt][0], y + fx[dt][1]
# 如果已经越过边界了，则需要转向
if x_ < condition[0] or x_ > condition[2] or y_ < condition[3] or y_ > condition[1]:
# 更新边界
if dt in (1, 2):
condition[dt] -= 1
else:
condition[dt] += 1
# 转向，并且重新移动
dt = (dt + 1) % 4
x_, y_ = x+fx[dt][0], y+fx[dt][1]
# print(x_, y_)
x, y = x_, y_
return ret
Давайте посмотрим на код, и есть еще одна деталь, которую мы сейчас не упомянули. Когда мы перемещаемся, мы не изменяем напрямую исходную переменную, потому что, если мы выходим за пределы или запускаем другие недопустимые ситуации, то мыНе могу откатиться. Поэтому мы создадим новые переменные x и y для представления позиции после перемещения, даже если она переместится в недопустимую позицию, это не повлияет на предыдущие результаты. Это также распространенный трюк, в Python мы ставим подчеркивание в конце переменной, чтобы указать, что это теневая (клонированная) переменная.
Суммировать
Я лично считаю, что сегодняшняя тема хороша, и новичкам нужно сделать ее самостоятельно. Потому что в процессе решения проблемы мы можем изучить очень полезный навык решения проблем массива направлений, Он широко используется в задаче поиска и, можно сказать, является одним из навыков, которые должны быть известны в задаче алгоритма. .
Вы можете подумать, что наша логика для решения, нужно ли нам поворачивать через границу, выглядит немного сложной, но это не обязательно. Мы также можем использовать некоторые другие методы вместо этого, например, мы можем открыть массив для записи пройденных позиций, чтобы заменить определение границы, по сравнению с методом с использованием определения границы, это занимает больше места и пропускает граница.Метод суждения больше тест мышления, так что я лично рекомендую его. Конечно, есть и другие методы решения этого вопроса, такие как поиск правил или что-то в этом роде, которые не особенно умны, поэтому они не будут отнимать у всех время.
На сегодняшней статье все. Если вы чувствуете, что что-то приобрели, пожалуйста, нажмитеПодпишитесь или сделайте ретвитЧто ж, твое маленькое усилие много значит для меня.