LeetCode 54. Spiral Matrix 59. Spiral Matrix II

题解

螺旋遍历矩阵大总结,给出一个优雅清晰的解法。
大概思路是模拟移动方向,计算xy位置。
比如n*m的矩阵,按右下左上的顺序,依次移动的步数是
{ m, n-1 , m-1 , n-2, …, 0 } 直到遇到第一个0。
其中左右的步数 { m, m-1 , m-2 … }
上下的步数 { n-1, n-2, n-3, … }
所以可以用个 step[2] = {m,n-1} 来记录剩余步数
每走完一行列就-1,直到遇到0。

看代码吧,思路清楚。


Code
class Solution {
public:
    int dx[4]={0,1,0,-1};
    int dy[4]={1,0,-1,0};
    vectorint spiralOrder(vectorvectorint matrix) {
        vectorint res;
        if(matrix.empty()) return res;
        int n=matrix.size(),m=matrix[0].size();
        if(n==0||m==0) return res;
        
        int step[2]={m,n-1};// steps need to move
        
        int D=0;// direction
        int nx,ny;
        nx=0,ny=-1;
        while(step[D%2]!=0){
            for(int i=0;istep[D%2];i++){
                nx+=dx[D];
                ny+=dy[D];
                res.push_back(matrix[nx][ny]);
            }
            step[D%2]--;
            D=(D+1)%4;
        }
        return res;
    }
};
vectorvectorint generateMatrix(int n) {
        vectorvectorint res(n,vectorint(n));
        
        int step[2]={n,n-1};
        int D=0;
        int nx,ny,k=1;
        nx=0,ny=-1;
        while(step[D%2]!=0){
            for(int i=0;istep[D%2];i++){
                nx+=dx[D];
                ny+=dy[D];
                res[nx][ny]=k++;
            }
            step[D%2]--;
            D=(D+1)%4;
        }
        return res;
    }
最新回复(0)
/jishulJ0cH13nLek90LxaAqSQkh3OGNweLIpBcNMP8lgoqDo_3D4858366
8 简首页