Учитывая
m x n
matrix
, вернуть все элементыmatrix
в порядке спирали.
Спиральная матрица была одной из первых матричных задач, которые я решил на LeetCode. Это также проблема, о которой я люблю говорить с другими из-за уникального решения, которое я в итоге создал.
Мне нравится думать об этой проблеме как о пустой комнате с четырьмя стенами. Человек начинает с угла комнаты и должен наступить на каждую плитку в этом спиральном узоре. Конечно, основная проблема заключается в том, как выразить этот шаблон в коде.
Output: [1,2,3,6,9,8,7,4,5] (0,0)(0,1)(0,2)(1,2)(2,2)(2,1)(2,0)(1,0)(1,1) y++ y++ x++ x++ y-- y-- x-- y++ I expressed the output as ordered pairs.
В 2D-матрице, если бы я хотел переместиться вверх, моя строка уменьшилась бы на единицу. Переместите вправо, тогда столбец увеличится на единицу. И так далее... Размышление об этом как о направлении заставило меня задуматься об углах. Одно повлекло за собой другое, и вдруг я попытался включить тригонометрию sin и cos в свое решение.
Direction | Angle | cos(A) | sin(A) Right (col++)| 0 | +1 | 0 Down (row++)| 90 | 0 | +1 Left (col--)| 180 | -1 | 0 Up (row--)| 270 | 0 | -1 Right (col++)| 0 | +1 | 0 Down (row++)| 90 | 0 | +1 Left (col--)| 180 | -1 | 0 Up (row--)| 270 | 0 | -1
Чтобы создать спираль, человек в комнате должен идти до тех пор, пока он не сможет, а затем повернуться вправо (угол += 90).
const rows= matrix.length, cols= matrix[0].length, result= [] // initialize result array // save dimension of matrix to variables let x= 0, y= 0, dir= 0, steps=1 // initialize initial position of my person, // direction, and a counter for steps while(steps <= rows*cols){ let nextX= x + Math.sin(dir), nextY= y + Math.cos(dir) if (nextX is invalid || nextY is invalid){ dir+= 90 // if my next position is invalid, then rotate } result.push(matrix[x][y]) x+= Math.cos(dir) y+= Math.sin(dir) steps++ } return result
Этот код/псевдокод почти готов к отправке. Оказывается, триггерные функции sin и cos на самом деле имеют некоторые неточности округления. Я очень расстроился, когда получил 0,99997 вместо 1. Это было бы проблемой, потому что матрица [0,99997] не определена.
То, как я решил эту проблему, было основано на стриме, который я видел на Twitch. Дэн Сальвато — разработчик игр и создатель Doki Doki Literature Club. Он сохранил 360 значений синуса и косинуса в массив. Затем просто обращались к ним по индексам. В моем случае мне нужно только 4 значения вместо 360.
const rows= matrix.length, cols= matrix[0].length, result= [], cos = [1, 0, -1, 0], sin = [0, 1, 0, -1] // initialize our lookup table let x= 0, y= 0, dir= 0, steps=1 while(steps <= rows*cols){ let nextX= x + sin[dir], nextY= y + cos[dir] // updated values if (nextX is invalid || nextY is invalid){ dir= (dir+1) %4 // previously it was fine for dir to // exceed 360 because sine and cosine is periodic // now dir must be an int from 0 to 3 } result.push(matrix[x][y]) x+= sin[dir] y+= cos[dir] steps++ } return result
Не хватает только того, как определить, недействительна ли следующая плитка. Для этого я просто проверяю, находится ли он в сетке и посещался ли он ранее. Я буду использовать набор для этого, но вы можете использовать другую структуру данных.
const rows= matrix.length, cols= matrix[0].length, result= [], cos = [1, 0, -1, 0], sin = [0, 1, 0, -1], visited= new Set() let x= 0, y= 0, dir= 0, steps=1 while(steps <= rows*cols){ let nextX= x + sin[dir], nextY= y + cos[dir] if (nextX < 0 || nextX >= rows || //checking if x,y is invalid nextY < 0 || nextY >= cols || //or if it is already visited visited.has(nextX+","+nextY)){ dir= (dir+1) %4 } result.push(matrix[x][y]) visited.add(x+","+y) // add current spot to the set x+= sin[dir] y+= cos[dir] steps++ } return result
И теперь мы готовы представить! Что я больше всего узнал о решении этой проблемы, так это создание таблицы поиска вместо написания четырех условных выражений для определения моего пути обхода. Вместо перемещения вправо, вниз и т. д. Я прошу свой код пройти как можно дальше, а затем повернуть на 90 градусов. Повторяйте, пока не дойдете до конца.
Надеюсь, вам понравился мой взгляд на решение спиральной матрицы. У меня определенно были отличные моменты. Я надеюсь продолжить делиться интересными решениями, которые могут включать мой опыт работы учителем математики и решения задач.