Сложность: medium
Дано положительное целое число n. Сгенерируйте матрицу n на n, заполненную элементами от 1 до n^2 в спиральном порядке.
Пример:
Input: n = 3
Output: [[1,2,3],[8,9,4],[7,6,5]]
👨💻 Алгоритм:
1⃣Определение направлений движения:
Для обхода матрицы используются четыре направления, формирующие слои. Создается массив dir, который хранит изменения координат x и y для каждого направления. Например, при движении слева направо (направление №1) координата x остается неизменной, а y увеличивается (x=0, y=1). При движении справа налево (направление №3) x остается неизменным, а y уменьшается (x=0, y=-1).
2⃣Перемещение по матрице:
Переменные row и col представляют текущие координаты x и y соответственно. Они обновляются в зависимости от направления движения. Применяется предварительно определенный массив dir с изменениями координат x и y для каждого из четырех направлений.
3⃣Изменение направления:
Направление изменяется, когда следующая строка или столбец в определенном направлении имеют ненулевое значение, что указывает на то, что они уже были пройдены. Переменная d представляет текущий индекс направления. Переход к следующему направлению в массиве dir осуществляется с использованием формулы (d+1)%4. Это позволяет вернуться к направлению 1 после завершения одного полного круга от направления 1 до направления 4.
😎 Решение:
class Solution {
func floorMod(_ x: Int, _ y: Int) -> Int {
return ((x % y) + y) % y
}
func generateMatrix(_ n: Int) -> [[Int]] {
var result = Array(repeating: Array(repeating: 0, count: n), count: n)
var cnt = 1
let dir = [(0, 1), (1, 0), (0, -1), (-1, 0)]
var d = 0
var row = 0
var col = 0
while cnt <= n * n {
result[row][col] = cnt
cnt += 1
let r = floorMod(row + dir[d].0, n)
let c = floorMod(col + dir[d].1, n)
if result[r][c] != 0 {
d = (d + 1) % 4
}
row += dir[d].0
col += dir[d].1
}
return result
}
}Ставь 👍 и забирай 📚 Базу знаний