Wednesday, October 23, 2013

59. Spiral Matrix II ----M

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 ]
]
A:
同问题一。  仍然是一层层地剥开设置。 复杂度为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