Bài 54 Leetcode: Spiral Matrix

Đề bài:

Cho một ma trận có kích thước m x n, hãy trả về tất cả các phần tử của ma trận theo thứ tự xoắn ốc.

Ví dụ 1:

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

Ví dụ 2:

Spiral Matrix
Spiral Matrix
Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

Ràng buộc:

  • m == độ dài của ma trận
  • n == độ dài của mỗi hàng trong ma trận
  • 1 <= m, n <= 10
  • -100 <= matrix[i][j] <= 100

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

class Solution {
 public:
  vector<int> spiralOrder(vector<vector<int>>& matrix) {
    if (matrix.empty())
      return {};

    const int m = matrix.size();
    const int n = matrix[0].size();
    vector<int> ans;
    int r1 = 0;
    int c1 = 0;
    int r2 = m - 1;
    int c2 = n - 1;

    // Repeatedly add matrix[r1..r2][c1..c2] to ans
    while (ans.size() < m * n) {
      for (int j = c1; j <= c2 && ans.size() < m * n; ++j)
        ans.push_back(matrix[r1][j]);
      for (int i = r1 + 1; i <= r2 - 1 && ans.size() < m * n; ++i)
        ans.push_back(matrix[i][c2]);
      for (int j = c2; j >= c1 && ans.size() < m * n; --j)
        ans.push_back(matrix[r2][j]);
      for (int i = r2 - 1; i >= r1 + 1 && ans.size() < m * n; --i)
        ans.push_back(matrix[i][c1]);
      ++r1, ++c1, --r2, --c2;
    }

    return ans;
  }
};

Đây là một đoạn mã C++ để trả về tất cả các phần tử của một ma trận theo thứ tự xoắn ốc.

Hàm `spiralOrder` nhận đầu vào là một vector 2D `matrix` và trả về vector `ans` chứa các phần tử của ma trận theo thứ tự xoắn ốc.

Trước tiên, hàm kiểm tra xem ma trận có rỗng không. Nếu là ma trận rỗng, hàm trả về một vector trống.

Tiếp theo, hàm khai báo biến `m` và `n` để lưu kích thước của ma trận. Biến `ans` được khởi tạo là một vector rỗng để lưu trữ các phần tử theo thứ tự xoắn ốc.

Các biến `r1`, `c1`, `r2`, `c2` đại diện cho các chỉ số hàng và cột để xác định phạm vi của ma trận con hiện tại.

Trong vòng lặp `while`, các vòng lặp `for` được sử dụng để thêm các phần tử của ma trận vào vector `ans` theo thứ tự xoắn ốc.

– Vòng lặp đầu tiên duyệt qua hàng đầu tiên của ma trận từ `c1` đến `c2`.

– Vòng lặp thứ hai duyệt qua cột cuối cùng của ma trận từ `r1 + 1` đến `r2 – 1`.

– Vòng lặp thứ ba duyệt qua hàng cuối cùng của ma trận từ `c2` đến `c1`.

– Vòng lặp thứ tư duyệt qua cột đầu tiên của ma trận từ `r2 – 1` đến `r1 + 1`.

Sau mỗi vòng lặp xoắn ốc, ta điều chỉnh các chỉ số hàng và cột `r1`, `c1`, `r2`, `c2` để thu hẹp phạm vi của ma trận con.

Cuối cùng, hàm trả về vector `ans` chứa các phần tử của ma trận theo thứ tự xoắn ốc.

Đây là một cách tiếp cận để truy cập các phần tử trong ma trận theo hình xoắn ốc bằng cách điều chỉnh các chỉ số hàng và cột theo từng vòng lặp.

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

class Solution {
  public List<Integer> spiralOrder(int[][] matrix) {
    if (matrix.length == 0)
      return new ArrayList<>();

    final int m = matrix.length;
    final int n = matrix[0].length;
    List<Integer> ans = new ArrayList<>();
    int r1 = 0;
    int c1 = 0;
    int r2 = m - 1;
    int c2 = n - 1;

    // Repeatedly add matrix[r1..r2][c1..c2] to the `ans`.
    while (ans.size() < m * n) {
      for (int j = c1; j <= c2 && ans.size() < m * n; ++j)
        ans.add(matrix[r1][j]);
      for (int i = r1 + 1; i <= r2 - 1 && ans.size() < m * n; ++i)
        ans.add(matrix[i][c2]);
      for (int j = c2; j >= c1 && ans.size() < m * n; --j)
        ans.add(matrix[r2][j]);
      for (int i = r2 - 1; i >= r1 + 1 && ans.size() < m * n; --i)
        ans.add(matrix[i][c1]);
      ++r1;
      ++c1;
      --r2;
      --c2;
    }

    return ans;
  }
}

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

class Solution:
  def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
    if not matrix:
      return []

    m = len(matrix)
    n = len(matrix[0])
    ans = []
    r1 = 0
    c1 = 0
    r2 = m - 1
    c2 = n - 1

    # Repeatedly add matrix[r1..r2][c1..c2] to the `ans`.
    while len(ans) < m * n:
      j = c1
      while j <= c2 and len(ans) < m * n:
        ans.append(matrix[r1][j])
        j += 1
      i = r1 + 1
      while i <= r2 - 1 and len(ans) < m * n:
        ans.append(matrix[i][c2])
        i += 1
      j = c2
      while j >= c1 and len(ans) < m * n:
        ans.append(matrix[r2][j])
        j -= 1
      i = r2 - 1
      while i >= r1 + 1 and len(ans) < m * n:
        ans.append(matrix[i][c1])
        i -= 1
      r1 += 1
      c1 += 1
      r2 -= 1
      c2 -= 1

    return ans

 

Leave a Reply

Your email address will not be published. Required fields are marked *

PHP Code Snippets Powered By : XYZScripts.com
.
.
.
.