天天看点

[59] Spiral Matrix II

1. 题目描述

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 ]

]

题目的意思是,给定一个数字n,输出一个以螺旋方式填满的n*n的二维数组

2. 解题思路

采用螺旋排列时的顺序为,右->下->左->上,都是走到头后换下一个方向,直到四个方向都无法前进则数组填充完成。

3. Code

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector <int> > matrix(n ,vector<int>(n,));    //n*n的二维vector,所有元素为0
        if(n == )
            return matrix;
        // 右下左上
        bool flag = true;  // 标记当前填充是否完成
        string des[] = {"right", "down", "left", "up"}; // right->down->left->up
        int choose = ;  // 当前方向
        string curDes = des[choose%];
        int i(), j();  // i->行 j->列
        int count();
        matrix[][] = ;
        if(n == )
            return matrix;
        while(flag)
        {
            int num();
            while(curDes == "right")
            {
                // 没有越界且右边是0
                if(j < n- && (matrix[i][j+] == ))
                {
                    matrix[i][++j] = ++count;
                    num++;
                }
                else
                {
                    curDes = des[++choose%];  // 换方向
                }
                if(num == )
                    return matrix;
            }
            while(curDes == "down")
            {
                // 没有越界且下边是0
                if(i < n- && (matrix[i+][j] == ))
                {
                    matrix[++i][j] = ++count;
                }
                else
                {
                    curDes = des[++choose%];  // 换方向
                }
            }
            while(curDes == "left")
            {
                // 没有越界且左边是0
                if(j >  && (matrix[i][j-] == ))
                {
                    matrix[i][--j] = ++count;
                }
                else
                {
                    curDes = des[++choose%];  // 换方向
                }
            }
            while(curDes == "up")
            {
                // 没有越界且上边是0
                if(i >  && (matrix[i-][j] == ))
                {
                    matrix[--i][j] = ++count;
                }
                else
                {
                    curDes = des[++choose%];  // 换方向
                }
            }
        }
    }
};
           

4. 学到的知识

学到了一个创建并初始化m*n的vector二维数组的方式,使用vector的构造函数matrix(int num, int value)

//m*n的二维vector,所有元素为0
vector<vector <int> > matrix(m ,vector<int>(n,));