首页 > 代码库 > [C++]LeetCode: 110 Spiral Matrix II (螺旋写入矩阵)

[C++]LeetCode: 110 Spiral Matrix II (螺旋写入矩阵)

2024-11-09 10:56:39   203人阅读

题目：

Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

For example,
Given n = 3,

You should return the following matrix:
[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

思路：这道题和Spiral Matrix的模型和解法一样。要求我们将1~n^2的数字螺旋写入矩阵中。我们依然维护四个变量，rowBegin, rowEnd, colBegin, colEnd。然后去界定螺旋的边界。我们需要注意的是，如果n 为0，我们应该返回空的数组。并且在写入数字时，我们也需要判断目前的数字是否超过最大数字N^2，如果超过，说明我们不需要遍历了。还有最重要的一点，数组在未初始化时，是不允许使用下标操作符来改变数组元素的，所以我们一定要先初始化数组，这里初始化为N行N列，元素都为0的数组。

Attention：

1. 返回空数组 别忘了括号。

if(n == 0) return vector<vector<int>>();

2. 初始化数组

vector<vector<int>> ret(n, vector<int>(n, 0));


3. 要记得判断是否达到数字最大值。每次遍历都需要判断

if (num <= n^2)
            {
                //向右遍历添加
                for (int j = colBegin; j <= colEnd; j++)
                {
                    ret[rowBegin][j] = num;
                    num++;
                }
            }

复杂度：O(n^2) n为输入数字

AC Code:

class Solution {
public:
    vector<vector<int> > generateMatrix(int n) {
        if(n == 0) return vector<vector<int>>();
        vector<vector<int>> ret(n, vector<int>(n, 0));
        
        int rowBegin = 0;
        int rowEnd = n - 1;
        int colBegin = 0;
        int colEnd = n - 1;
        int num = 1;
        
        while (rowBegin <= rowEnd && colBegin <= colEnd)
        {
            if (num <= n^2)
            {
                //向右遍历添加
                for (int j = colBegin; j <= colEnd; j++)
                {
                    ret[rowBegin][j] = num;
                    num++;
                }
            }
            rowBegin++;
            
            if (num <= n^2)
            {
                //向下遍历添加
                for (int i = rowBegin; i <= rowEnd; i++)
                {
                    ret[i][colEnd] = num;
                    num++;
                }
            }
            colEnd--;
            
            if (num <= n^2)
            {
                //向左遍历添加
                for (int j = colEnd; j >= colBegin; j--)
                {
                    ret[rowEnd][j] = num;
                    num++;
                }
            }
            rowEnd--;
            
            if (num <= n^2)
            {
                //向上遍历添加
                for (int i = rowEnd; i >= rowBegin; i--)
                {
                    ret[i][colBegin] = num;
                    num++;
                }
            }
            colBegin++;
        }
        
        return ret;
    }
};

 


[C++]LeetCode: 110 Spiral Matrix II (螺旋写入矩阵)


联系
我们