Simple C++ solution(with explaination)


  • 49
    A
    class Solution {
        public:
            vector<vector<int> > generateMatrix(int n) {
                vector<vector<int> > ret( n, vector<int>(n) );
            	int k = 1, i = 0;
            	while( k <= n * n )
            	{
            		int j = i;
                        // four steps
            		while( j < n - i )             // 1. horizonal, left to right
            			ret[i][j++] = k++;
            		j = i + 1;
            		while( j < n - i )             // 2. vertical, top to bottom
            			ret[j++][n-i-1] = k++;
            		j = n - i - 2;
            		while( j > i )                  // 3. horizonal, right to left 
            			ret[n-i-1][j--] = k++;
            		j = n - i - 1;
            		while( j > i )                  // 4. vertical, bottom to  top 
            			ret[j--][i] = k++;
            		i++;      // next loop
            	}
            	return ret;
            }
        };

  • -34
    S

    class Solution {
    public:
    vector<vector<int>> generateMatrix(int n) {
    vector<vector<int>> res(n, vector<int>(n,0));
    int count = 1;
    int row_s = 0, row_e = n - 1, col_s = 0, col_e = n - 1;
    while (row_s <= row_e && col_s <= col_e){
    for (int c = col_s; c <= col_e; ++c ){
    res[row_s][c] = count++;
    }
    for (int r = row_s + 1; r <= row_e; ++r ){
    res[r][col_e] = count++;
    }
    if (row_s < row_e) {
    for (int c = col_e - 1; c >= col_s; --c ){
    res[row_e][c] = count++;
    }
    }
    if (col_s < col_e) {
    for (int r = row_e - 1; r > row_s; --r ){
    res[r][col_s] = count++;
    }
    }
    ++row_s; --row_e; ++col_s; --col_e;
    }
    return res;
    }
    };


  • 0
    B

    Recursive version:

    class Solution {
    public:
        vector<vector<int>> generateMatrix(int n) {
            vector<vector<int>> toReturn(n,vector<int>(n,1));
            int currVal = 1;
            aux(toReturn, 0, currVal, n);
            return toReturn;
        }
        
        void aux(vector<vector<int>>& v, int topLeft, int currVal, int n){
            if (topLeft > n/2) return;
            int endIndex = n - topLeft - 1;
            for (int i = topLeft; i <= endIndex; ++i) v[topLeft][i] = currVal++;
            for (int i = topLeft + 1; i <= endIndex; i++) v[i][endIndex] = currVal++;
            for (int i = endIndex-1; i >= topLeft; --i) v[endIndex][i] = currVal++;
            for (int i = endIndex-1; i >= topLeft+1; --i) v[i][topLeft] = currVal++;
            aux(v, ++topLeft, currVal, n);
        }
    };

  • 0
    Z

    really clean logic, LIKE IT


  • 1
    D

    My solution ^_^.

    class Solution {
    public:
        vector<vector<int> > generateMatrix(int n) {
            vector<vector<int> > res(n,vector<int>(n));
            int i=0,j=0,cur=1;
            while(n>0){
                res[i][j]=cur++;
                n--;
                int step=n;
                while(step>0){
                    res[i][++j]=cur++;
                    step--;
                }
                step=n;
                while(step>0){
                    res[++i][j]=cur++;
                    step--;
                }
                step=n--;
                while(step>0){
                    res[i][--j]=cur++;
                    step--;
                }
                step=n;
                while(step>0){
                    res[--i][j]=cur++;
                    step--;
                }
                j++;
            }
            return res;
        }
    };
    

  • 0
    D
    This post is deleted!

  • 0
    S

    Very clean handling the loops!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.