59. 螺旋矩阵 II

Problem: 59. 螺旋矩阵 II

思路

循环赋值,重点是循环的边次序、区间

解题方法

按照循环顺序一层一层的赋值

如下面所示: 一共要赋值n * n次,模拟一个循环

while(num <= tar){
	for(int i = l; i <= r; i++) mat[t][i] = num++; // 从左到右
	t++;// 到下一层
	for(int i = t; i <= b; i++) mat[i][r] = num++; // 从上到下
	r--;// 到左边一层
	for(int i = r; i >= l; i--) mat[b][i] = num++; // 从右到左
	b--;// 到上面一层
	for(int i = b; i >= t; i--) mat[i][l] = num++; // bottom to top.
	l++;// 到左边一层
}

脑瘫的错误

主要是 循环中的i、j值不要写错

复杂度

• 时间复杂度:

$O(n)$

• 空间复杂度:

$O(1)$

Code

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        int l = 0, r = n - 1, t = 0, b = n - 1;
        vector<vector<int>> mat(n,vector<int>(n,0));
        int num = 1, tar = n * n;
        while(num <= tar){
            for(int i = l; i <= r; i++) mat[t][i] = num++; // left to right.
            t++;
            for(int i = t; i <= b; i++) mat[i][r] = num++; // top to bottom.
            r--;
            for(int i = r; i >= l; i--) mat[b][i] = num++; // right to left.
            b--;
            for(int i = b; i >= t; i--) mat[i][l] = num++; // bottom to top.
            l++;
        }
        return mat;
    }
};