59. Spiral Matrix II

Medium (Trung bình) C++ 🔗 Xem trên LeetCode

📋 Đề Bài

Given a positive integer n, generate an n x n matrix filled with elements from 1 to n² in spiral order.

Example 1:

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

Example 2:

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

Constraints:

1 <= n <= 20

🧠 Thuật Toán & Kỹ Thuật

Bit Manipulation (Thao tác bit)Matrix (Ma trận)

⏱️ Thời gian O(n²)

💾 Không gian O(n)

💻 Lời Giải

C++ 0059-spiral-matrix-ii.cpp

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        int u = 0, d = n - 1, l = 0, r = n - 1;
        int val = 0;
        vector<vector<int>> ans(n, vector<int>(n));
        
        while (u <= d and l <= r) {
            for (int col = l; col <= r; ++col) {
                ans[l][col] = (++val);
            }
            u++;
            if (u > d) {
                break;
            }
            for (int row = u; row <= d; ++row) {
                ans[row][r] = (++val);
            }
            r--;
            if (r < l) {
                break;
            }
            for (int col = r; col >= l; --col) {
                ans[d][col] = (++val);
            }
            d--;
            if (d < u) {
                break;
            }
            for (int row = d; row >= u; --row) {
                ans[row][l] = (++val);
            }
            l++;
            if (l > r) {
                break;
            }
        }
        
        return ans;  
    }
};