A: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 ] ]
同问题一。 仍然是一层层地剥开设置。 复杂度为n2
class Solution { public: vector<vector<int>> generateMatrix(int n) { vector<vector<int>> V(n, vector<int>(n,0)); int c = 0; for(int layer = 0; layer < (n+1)/2;layer++){ int x0 = layer, y0 = x0, x1 = n-layer-1, y1 = x1; for(int col = y0;col<=y1; col++){ // NEED <= in case x0 == x1 V[x0][col] = ++c; } for(int row = x0+1; row<=x1;row++){ V[row][y1] = ++c; } if(x1>x0){ for(int col = y1-1;col>= y0;col--){ V[x1][col] = ++c; } } if(y0<y1){ for(int row = x1-1; row > x0;row--){ V[row][y0] = ++c; } } } return V; } };上面的是对于 m * n 矩阵的。 而对于 n * n 矩阵, 左右判断的可以省略掉 (当x0==x1时,只会增加第一个for loop)
class Solution { public: vector<vector<int>> generateMatrix(int n) { vector<vector<int>> V(n, vector<int>(n,0)); int c = 0; for(int layer = 0; layer < (n+1)/2;layer++){ int x0 = layer, y0 = x0, x1 = n-layer-1, y1 = x1; for(int col = y0;col<=y1; col++){ // NEED <= in case x0 == x1 V[x0][col] = ++c; } for(int row = x0+1; row<=x1;row++){ V[row][y1] = ++c; } for(int col = y1-1;col>= y0;col--){ V[x1][col] = ++c; } for(int row = x1-1; row > x0;row--){ V[row][y0] = ++c; } } return V; } };
Mistakes:
-------------------------------------3 rd Pass -----------------------------------
当n 是奇数,判断中心点的时候, 一开始写成了 if(n%2 == 1 && layer +1 = n/2) 这样当n ==1的时候是不对的。
public class Solution { public int[][] generateMatrix(int n) { int[][] A = new int[n][n]; helper(A,0,n-1,1); return A; } private void helper(int[][] A , int l, int r, int k){// l is the top left, r is down right corner if(l>r) return; if(l==r){ A[l][l] = k++; return; } for(int j=l;j<r;j++) A[l][j]=k++; for(int i = l;i<r;i++) A[i][r] = k++; for(int j = r;j> l; j--) A[r][j] = k++; for(int i = r;i>l;i--) A[i][l] = k++; helper(A,l+1,r-1, k); } }
Learned:
No comments:
Post a Comment