Bài 48 Leetcode: Rotate Image

Đề bài:

Bạn được cho một ma trận 2D có kích thước n x n đại diện cho một hình ảnh. Hãy xoay hình ảnh đi 90 độ theo chiều kim đồng hồ.

Bạn phải xoay hình ảnh trực tiếp trong chỗ, điều này có nghĩa là bạn phải chỉnh sửa ma trận 2D đầu vào trực tiếp. KHÔNG cấp phát một ma trận 2D khác và thực hiện xoay.

Ví dụ 1:

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

Ví dụ 2:

Rotate Image
Rotate Image
Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

Ràng buộc:

  • n == độ dài của ma trận == độ dài của matrix[i]
  • 1 <= n <= 20
  • -1000 <= matrix[i][j] <= 1000

Cách 1: Reverse

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

class Solution {
 public:
  void rotate(vector<vector<int>>& matrix) {
    reverse(matrix.begin(), matrix.end());
    for (int i = 0; i < matrix.size(); ++i)
      for (int j = i + 1; j < matrix.size(); ++j)
        swap(matrix[i][j], matrix[j][i]);
  }
};

Đây là một giải thuật để xoay ma trận 2D đi 90 độ theo chiều kim đồng hồ. Dưới đây là giải thích chi tiết về giải thuật:

1. Sử dụng hàm `reverse` để đảo ngược các hàng của ma trận. Điều này sẽ tạo ra một ma trận mới với các hàng được sắp xếp theo thứ tự ngược lại so với ma trận ban đầu.

2. Sử dụng hai vòng lặp lồng nhau để truy cập các phần tử trong ma trận. Vòng lặp ngoài (`i`) lặp qua các hàng, và vòng lặp trong (`j`) lặp qua các cột, chỉ đi từ cột `i+1` trở đi.

3. Trong mỗi vòng lặp, sử dụng hàm `swap` để hoán đổi giá trị của hai phần tử: `matrix[i][j]` và `matrix[j][i]`. Điều này sẽ hoán đổi các phần tử trên đường chéo chính của ma trận (từ góc trên bên trái đến góc dưới bên phải).

Kết quả là ma trận `matrix` sẽ được xoay đi 90 độ theo chiều kim đồng hồ.

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

class Solution {
  public void rotate(int[][] matrix) {
    for (int i = 0, j = matrix.length - 1; i < j; ++i, --j) {
      int[] temp = matrix[i];
      matrix[i] = matrix[j];
      matrix[j] = temp;
    }

    for (int i = 0; i < matrix.length; ++i)
      for (int j = i + 1; j < matrix.length; ++j) {
        final int temp = matrix[i][j];
        matrix[i][j] = matrix[j][i];
        matrix[j][i] = temp;
      }
  }
}

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

class Solution:
  def rotate(self, matrix: List[List[int]]) -> None:
    matrix.reverse()

    for i in range(len(matrix)):
      for j in range(i + 1, len(matrix)):
        matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

Cách 2: Indexing

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

class Solution {
 public:
  void rotate(vector<vector<int>>& matrix) {
    for (int min = 0; min < matrix.size() / 2; ++min) {
      const int max = matrix.size() - min - 1;
      for (int i = min; i < max; ++i) {
        const int offset = i - min;
        const int top = matrix[min][i];
        matrix[min][i] = matrix[max - offset][min];
        matrix[max - offset][min] = matrix[max][max - offset];
        matrix[max][max - offset] = matrix[i][max];
        matrix[i][max] = top;
      }
    }
  }
};

Đoạn mã trên triển khai thuật toán để xoay ma trận 90 độ theo chiều kim đồng hồ.

Thuật toán này hoạt động như sau:

1. Duyệt qua từng lớp ma trận, bắt đầu từ lớp bên ngoài và tiến vào trong.

– Với mỗi lớp, ta duyệt qua từng phần tử trong lớp đó.

– Lớp thứ `min` là lớp bên ngoài cùng và lớp thứ `max` là lớp bên trong cùng.

2. Trong mỗi lớp, ta thực hiện việc xoay các phần tử theo vòng xoay.

– Tại mỗi vị trí `(min, i)` trong ma trận, ta lưu giá trị của phần tử đó vào biến `top`.

– Gán phần tử tại vị trí `(min, i)` bằng phần tử tại vị trí `(max – offset, min)`.

– Gán phần tử tại vị trí `(max – offset, min)` bằng phần tử tại vị trí `(max, max – offset)`.

– Gán phần tử tại vị trí `(max, max – offset)` bằng phần tử tại vị trí `(i, max)`.

– Gán phần tử tại vị trí `(i, max)` bằng giá trị `top` đã lưu trước đó.

3. Tiếp tục duyệt qua các lớp khác, thực hiện việc xoay tương tự cho mỗi lớp.

4. Khi duyệt qua tất cả các lớp, ma trận sẽ đã được xoay 90 độ theo chiều kim đồng hồ.

Thuật toán này hoạt động bằng cách thực hiện việc hoán đổi các phần tử của ma trận theo cách phù hợp để đạt được hiệu ứng xoay 90 độ. Bằng cách duyệt qua các lớp từ bên ngoài vào trong, ta có thể xoay các phần tử một cách tuần tự và chính xác để đạt được kết quả xoay ma trận mong muốn.

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

class Solution {
  public void rotate(int[][] matrix) {
    for (int min = 0; min < matrix.length / 2; ++min) {
      final int max = matrix.length - min - 1;
      for (int i = min; i < max; ++i) {
        final int offset = i - min;
        final int top = matrix[min][i];
        matrix[min][i] = matrix[max - offset][min];
        matrix[max - offset][min] = matrix[max][max - offset];
        matrix[max][max - offset] = matrix[i][max];
        matrix[i][max] = top;
      }
    }
  }
}

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

class Solution:
  def rotate(self, matrix: List[List[int]]) -> None:
    for min in range(len(matrix) // 2):
      max = len(matrix) - min - 1
      for i in range(min, max):
        offset = i - min
        top = matrix[min][i]
        matrix[min][i] = matrix[max - offset][min]
        matrix[max - offset][min] = matrix[max][max - offset]
        matrix[max][max - offset] = matrix[i][max]
        matrix[i][max] = top

Leave a Reply

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

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