Учитывая 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 градусов. Повторяйте, пока не дойдете до конца.

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