LeetCode Spiral Matrix II

LeetCode Spiral Matrix II

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 ]
]

要求按螺旋方式把n阶方阵填满,和LeetCode Spiral Matrix几乎一样,而且还是方阵。直接一圈一圈填就好了。

完整代码如下:

class Solution {
public:
	vector<vector<int>> generateMatrix(int n) {
		vector<vector<int>> vMatrix(n, vector<int>(n, 0));
		int sx = 0, sy = 0, tx = n, ty = n, k = 1;
		while (k <= n*n) {
			for (int j = sy; j < ty; j++)
				vMatrix[sx][j] = k++;
			for (int i = sx + 1; i < tx; i++)
				vMatrix[i][ty - 1] = k++;
			for (int j = ty - 2; sx + 1 < tx && j >= sy; j--) // 满足上一个条件sx+1<tx
				vMatrix[tx - 1][j] = k++;
			for (int i = tx - 2; ty - 2 >= sy && i > sx; i--) // 满足上一个条件ty-2>=sy
				vMatrix[i][sy] = k++;
			sx++;
			sy++;
			tx--;
			ty--;
			if (sx >= tx || sy >= ty)break;
		}
		return vMatrix;
	}
};

本代码提交AC,用时3MS。

二刷。和LeetCode Spiral Matrix类似,更安全的方法,如下:

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> ans(n, vector<int>(n, 0));
        int cnt = 1;
        int start_row = 0, start_col = 0, end_row = n - 1, end_col = n - 1;
        while(start_row <= end_row && start_col <= end_col) {
            for(int j = start_col; j <= end_col; ++j) {
                ans[start_row][j] = cnt++;
            }
            ++start_row;
            for(int i = start_row; i <= end_row; ++i) {
                ans[i][end_col] = cnt++;
            }
            --end_col;
            if(start_row <= end_row) {
                for(int j = end_col; j >= start_col; --j) {
                    ans[end_row][j] = cnt++;
                }
            }
            --end_row;
            if(start_col <= end_col) {
                for(int i = end_row; i >= start_row; --i) {
                    ans[i][start_col] = cnt++;
                }
            }
            ++start_col;
        }
        return ans;
    }
};

本代码提交AC,用时6MS。

Leave a Reply

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