[leetcode] Spiral Matrix II


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

和之前的Sparial Matrix挺像。

上次是读,这次是填充。

这次的算法换了一个思路,标记每一圈的左上角起始点,然后一圈一圈地填充。

需要注意,当n为奇数时,我们在最后一圈时只用填充一个元素。需要单独判断。

class Solution {
public:
    vector<vector<int> > generateMatrix(int n) {
        
        vector<int> row(n,0);
        vector<vector<int>> re(n,row);
        //populate the matrix round by round
        int count = 1;
        for(int startP = 0; startP <= (n - 1) / 2; startP++){
            int r = startP;
            int c = startP;
            //move right
            while(c < n - startP){
                re[r][c] = count++;
                c++;
            }
            c--;
            r++;
            if(r * 2 > n){
                break;//end population
            }
            //move down
            while(r < n - startP){
                re[r][c] = count++;
                r++;
            }
            r--;
            c--;
            //move left
            while(c >= startP){
                re[r][c] = count++;
                c--;
            }
            r--;
            c++;
            //move up
            while(r > startP){
                re[r][c] = count++;
                r--;
            }
        }
        return re;
    }
};

 

Selection_031

 

 

 

Leave a comment

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.