康瑞部落

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

解题思路：

http://blog.csdn.net/kangrydotnet/article/details/44727955的姐妹篇。不停的进行扫描而已。注重分析能力。

源代码：

class Solution {
public:
    vector<vector<int> > generateMatrix(int n) {
        int** d=new int*[n];
        for(int i=0; i<n; i++){
            d[i] = new int[n];
        }

        int x=0, y=0;
        int data=1;
        while(data<=n*n){
            //赋值上边
            for(int i=y; i < n-y; i++){
                d[x][i] = data;
                data++;
            }
            
            //赋值右边
            for(int i=x+1; i< n-x; i++){
                d[i][n-y-1]=data;
                data++;
            }
            
            //赋值下边
            for(int i=n-y-2; i>=y; i--){
                d[n-x-1][i]=data;
                data++;
            }
            
            //赋值左边
            for(int i=n-x-2; i>x; i--){
                d[i][y] = data;
                data++;
            }
            x++;
            y++;
        }
        
        vector<vector<int>> result;
        for(int i=0; i<n; i++){
            vector<int> row;
            for(int j=0; j<n; j++){
                row.push_back(d[i][j]);
            }
            result.push_back(row);
        }
        
        for(int i=0; i<n; i++){
            delete[] d[i];
        }
        delete[] d;
        
        return result;
    }
};

二次刷题（update in 2015-07-29）

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        if(n<=0){
            vector<vector<int>> result;
            return result;
        }
        vector<vector<int>> result(n, vector<int>(n, 0));
        
        int layer = 0;
        int num = 0;
        while(num<n*n){
            //北边
            for(int i=layer; i<n-layer; i++){
                result[layer][i] = ++num;
            }
            //东边
            for(int i=layer+1; i<n-layer; i++){
                result[i][n-1-layer] = ++num;
            }
            if(num>=n*n){
                break;
            }
            //南边
            for(int i=n-1-layer-1; i>=layer; i--){
                result[n-1-layer][i] = ++num;
            }
            //西边
            for(int i=n-1-layer-1; i>layer; i--){
                result[i][layer] = ++num;
            }
            layer++;
        }
        
        return result;
    }
};