Bài 59 Leetcode: Spiral Matrix II

Đề bài:

Cho một số nguyên dương n, tạo ra một ma trận kích thước n x n được điền các phần tử từ 1 đến n² theo thứ tự xoắn ốc.

Input: n = 3
Output: [[1,2,3],[8,9,4],[7,6,5]]

Ví dụ 2:

Input: n = 1
Output: [[1]]

Ràng buộc:

• 1 <= n <= 20

Giải thích thuật toán bằng C ++

class Solution {
 public:
  vector<vector<int>> generateMatrix(int n) {
    vector<vector<int>> ans(n, vector<int>(n));
    int count = 1;

    for (int min = 0; min < n / 2; ++min) {
      const int max = n - min - 1;
      for (int i = min; i < max; ++i)
        ans[min][i] = count++;
      for (int i = min; i < max; ++i)
        ans[i][max] = count++;
      for (int i = max; i > min; --i)
        ans[max][i] = count++;
      for (int i = max; i > min; --i)
        ans[i][min] = count++;
    }

    if (n & 1)
      ans[n / 2][n / 2] = count;

    return ans;
  }
};

Đoạn mã trên là một phương thức trong lớp `Solution` được viết bằng ngôn ngữ C++ để tạo ra một ma trận kích thước n x n được điền các phần tử từ 1 đến n^2 theo thứ tự xoắn ốc.

Phương thức `generateMatrix` nhận đầu vào là một số nguyên `n`. Nó trả về một ma trận hai chiều `ans` có kích thước n x n.

Trước tiên, một ma trận `ans` được khởi tạo với kích thước n x n và các phần tử ban đầu được đặt là 0.

Biến `count` được khởi tạo với giá trị 1 để đếm và gán các phần tử vào ma trận.

Vòng lặp for đầu tiên điều khiển việc điều chỉnh giới hạn min của ma trận. Vòng lặp này sẽ chạy từ 0 đến n/2 (lấy phần nguyên). Biến `min` đại diện cho chỉ số hàng và cột tối thiểu mà ta đang xem xét.

Trong vòng lặp for thứ hai, các phần tử từ ans[min][min] đến ans[min][max-1] sẽ được gán giá trị từ `count` và tăng `count` lên 1 sau mỗi lần gán.

Tiếp theo, trong vòng lặp for thứ ba, các phần tử từ ans[min][max] đến ans[max-1][max] sẽ được gán giá trị từ `count` và tăng `count` lên 1 sau mỗi lần gán.

Sau đó, trong vòng lặp for thứ tư, các phần tử từ ans[max][max] đến ans[max][min+1] sẽ được gán giá trị từ `count` và tăng `count` lên 1 sau mỗi lần gán.

Cuối cùng, trong vòng lặp for thứ năm, các phần tử từ ans[max][min] đến ans[min+1][min] sẽ được gán giá trị từ `count` và tăng `count` lên 1 sau mỗi lần gán.

Nếu n là số lẻ, phần tử ở giữa ma trận ans[n/2][n/2] sẽ được gán giá trị là `count`.

Cuối cùng, phương thức trả về ma trận `ans` đã được điền đầy đủ các phần tử từ 1 đến n^2 theo thứ tự xoắn ốc.

Đây là một cách tiếp cận để tạo ra ma trận xoắn ốc bằng cách điều khiển việc gán giá trị các phần tử theo chiều xoắn ốc theo chiều kim đồng hồ từ ngoài vào trong.

Giải thích thuật toán bằng Java

class Solution {
  public int[][] generateMatrix(int n) {
    int[][] ans = new int[n][n];
    int count = 1;

    for (int min = 0; min < n / 2; ++min) {
      final int max = n - min - 1;
      for (int i = min; i < max; ++i)
        ans[min][i] = count++;
      for (int i = min; i < max; ++i)
        ans[i][max] = count++;
      for (int i = max; i > min; --i)
        ans[max][i] = count++;
      for (int i = max; i > min; --i)
        ans[i][min] = count++;
    }

    if (n % 2 == 1)
      ans[n / 2][n / 2] = count;

    return ans;
  }
}

Giải thích thuật toán bằng Python

class Solution:
  def generateMatrix(self, n: int) -> List[List[int]]:
    ans = [[0] * n for _ in range(n)]
    count = 1

    for min in range(n // 2):
      max = n - min - 1
      for i in range(min, max):
        ans[min][i] = count
        count += 1
      for i in range(min, max):
        ans[i][max] = count
        count += 1
      for i in range(max, min, -1):
        ans[max][i] = count
        count += 1
      for i in range(max, min, -1):
        ans[i][min] = count
        count += 1

    if n & 1:
      ans[n // 2][n // 2] = count

    return ans