题目链接:https://leetcode.com/problems/spiral-matrix-ii/description/
Given a positive integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.
Example:
Input: 3
Output:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]
思路:
- 本题和54.Spiral Matrix思路上基本一致,只不过本题是要求在矩阵中填入数据,但两者对矩阵的遍历方式一样;
- 遍历矩阵的思路可以查看这篇博文:54.Spiral Matrix
注意:这种方式定义容器vector<vector<int>> matrix(n * n); 容器元素的值是未定义的随机值,编译会导致:EXC_BAD_ACCESS (code=1, address=0x0)错误。
处理方式有两种:
// 第一种方式:
vector<vector<int>> matrix(n, vector<int>(n)); // 第二种方式:
vector<vector<int> > matrix(n);
for ( int i = ; i < n ; i++ )
matrix[i].resize(n);
这样就能保证matrix中的每个元素初值为:0;
编码如下:
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
// vector<vector<int> > matrix(n);
// for ( int i = 0 ; i < n ; i++ )
// matrix[i].resize(n);
vector<vector<int>> matrix(n, vector<int>(n)); int loop = n / + n % ; int i = , j = ; // matrix[i][j]
int num = ;
while (loop-- > )
{
int left_Up = , right_Up = n - j, right_Down = n - i, left_Down = ;
// 从左上角 -> 右上角 (i, left_Up) -> (i, right_Up) == (i, left_Up)
for (left_Up = j; left_Up < right_Up && num <= n * n; ++left_Up)
{
matrix[i][left_Up] = num++;
}
left_Up--; // 从右上角 -> 右下角 (right_Up = i+1, left_Up) -> (right_Down, left_Up) == (right_Up, left_Up)
for (right_Up = i + ; right_Up < right_Down && num <= n * n; ++right_Up)
{
matrix[right_Up][left_Up] = num++;
}
right_Up--; // 从右下角 -> 左下角 (right_Up, right_Down = left_Up - 1) -> (right_Up, j) == (right_Up, right_Down)
for (right_Down = left_Up - ; right_Down >= j && num <= n * n; --right_Down)
{
matrix[right_Up][right_Down] = num++;
}
right_Down++; // 从左下角 -> 左上角 (left_Up = right_Up - 1, right_Down) -> (i++, right_Down) == (left_Up, right_Down)
i++;
for (left_Up = right_Up - ; left_Up >= i && num <= n * n; --left_Up)
{
matrix[left_Up][right_Down] = num++;
}
j++;
} return matrix;
}
};