59. Spiral Matrix II

public class Solution {
    public int[][] GenerateMatrix(int n) {
        int[][] res = new int [n][];
        for (int i = 0; i < n; i++) res[i] = new int[n];
        int[][] helpers =
            new int [4][] { new int[2] { 0, 1 }, new int[2] { 1, 0 },
                            new int[2] { 0, -1 }, new int[2] { -1, 0 } };
        int val = 1, d = 0, row = 0, col = 0;
        while (val <= n * n) {
            res[row][col] = val++;
            int r = (row + helpers[d][0] + n) % n;
            int c = (col + helpers[d][1] + n) % n;
            if (res[r][c] != 0)
                d = (d + 1) % 4;
            row += helpers[d][0];
            col += helpers[d][1];
        }
        return res;
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int[][] GenerateMatrix(int n) {
        int[][] res = new int [n][];
        for (int i = 0; i < n; i++) res[i] = new int[n];
        int[][] helpers =
            new int [4][] { new int[2] { 0, 1 }, new int[2] { 1, 0 },
                            new int[2] { 0, -1 }, new int[2] { -1, 0 } };
        int val = 1, d = 0, row = 0, col = 0;
        while (val <= n * n) {
            res[row][col] = val++;
            int r = (row + helpers[d][0] + n) % n;
            int c = (col + helpers[d][1] + n) % n;
            if (res[r][c] != 0)
                d = (d + 1) % 4;
            row += helpers[d][0];
            col += helpers[d][1];
        }
        return res;
    }
}

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] result = new int[n][n];
        int cnt = 1;
        int dir[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
        int d = 0;
        int row = 0;
        int col = 0;
        while (cnt <= n * n) {
            result[row][col] = cnt++;
            int r = Math.floorMod(row + dir[d][0], n);
            int c = Math.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;
    }
}

var generateMatrix = function (n) {
    const result = new Array(n).fill(0).map(() => new Array(n).fill(0));
    const dirs = [
        [0, 1],
        [1, 0],
        [0, -1],
        [-1, 0],
    ];
    let d = 0;
    let row = 0;
    let col = 0;
    let cnt = 1;
    while (cnt <= n * n) {
        result[row][col] = cnt++;
        let newRow = (row + (dirs[d][0] % n) + n) % n;
        let newCol = (col + (dirs[d][1] % n) + n) % n;
        if (result[newRow][newCol] != 0) d = (d + 1) % 4;
        row += dirs[d][0];
        col += dirs[d][1];
    }
    return result;
};

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        def idx_convert_1D_2D(idx):
            return idx // n, idx % n

        def is_out_of_bound(row, col):
            return row < 0 or row >= n or col < 0 or col >= n

        dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        result = [[0] * n for _ in range(n)]
        cur_dir_idx = 0
        row, col = 0, 0
        for i in range(1, n * n + 1):
            result[row][col] = i
            dx, dy = dirs[cur_dir_idx]
            if is_out_of_bound(row + dx, col + dy) or result[row + dx][col + dy] > 0:
                cur_dir_idx = (cur_dir_idx + 1) % 4
            dx, dy = dirs[cur_dir_idx]
            row, col = row + dx, col + dy
        return result

func generateMatrix(n int) [][]int {
    result := make([][]int, n)
    for i := range result {
        result[i] = make([]int, n)
    }
    dirs := [4][2]int{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}
    d := 0
    row := 0
    col := 0
    cnt := 1
    for cnt <= n*n {
        result[row][col] = cnt
        cnt++
        newRow := (row + dirs[d][0] + n) % n
        newCol := (col + dirs[d][1] + n) % n
        if result[newRow][newCol] != 0 {
            d = (d + 1) % 4
        }
        row += dirs[d][0]
        col += dirs[d][1]
    }
    return result
}

Algorithm

1️⃣

Definição направлений движения:

Для обхода матрицы используются четыре направления, формирующие слои. Создается array dir, который хранит изменения координат x и y для каждого направления. НаExemplo, при движении слева направо (направление №1) координата x остается неизменной, а y увеличивается (x=0, y=1). При движении справа налево (направление №3) x остается неизменным, а y уменьшается (x=0, y=-1).

2️⃣

Перемещение по матрице:

Переменные row и col представляют текущие координаты x и y соответственно. Они обновляются в зависимости от направления движения. Применяется предварительно определенный array dir с изменениями координат x и y для каждого из четырех направлений.

3️⃣

Изменение направления:

Направление изменяется, когда следующая string или столбец в определенном направлении имеют ненулевое значение, что указывает на то, что они уже были пройдены. Переменная d представляет текущий индекс направления. Переход к следующему направлению в arrayе dir осуществляется с использованием формулы (d+1)%4. Это позволяет вернуться к направлению 1 после завершения одного полного круга от направления 1 до направления 4.

😎