LeetCode54/59 Spiral Matrix I/II

悠悠 2022-08-05 13:06 175阅读 0赞

一：Spiral Matrix I

题目：

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example,  
Given the following matrix:

[
     [ 1, 2, 3 ],
     [ 4, 5, 6 ],
     [ 7, 8, 9 ]
    ]

You should return `[1,2,3,6,9,8,7,4,5]`.

链接：https://leetcode.com/problems/spiral-matrix/

分析：看代码，四个while循环形成一个大圈

class Solution {
    public:
        void dfs(int xi, int yi, const int &m, const int &n, vector<vector<int> > &matrix, vector<int> &result, int **visited){
            visited[xi][yi] = 1;
            result.push_back(matrix[xi][yi]);
            while(yi+1 < n && !visited[xi][yi+1]){  // 四个while循环刚好跑了大正圈
                result.push_back(matrix[xi][yi+1]);
                visited[xi][yi+1] = 1;
                yi = yi+1;
            }
            while(xi+1 < m && !visited[xi+1][yi]){
                result.push_back(matrix[xi+1][yi]);
                visited[xi+1][yi] = 1;
                xi = xi +1;
            }
            while(yi-1 >=0 && !visited[xi][yi-1]){
                result.push_back(matrix[xi][yi-1]);
                visited[xi][yi-1] = 1;
                yi = yi-1;
            }
             while(xi-1 >=0 && !visited[xi-1][yi]){
                result.push_back(matrix[xi-1][yi]);
                visited[xi-1][yi] = 1;
                xi = xi-1;
            }
            if(yi+1 < n && !visited[xi][yi+1]) dfs(xi, yi+1, m, n, matrix, result, visited);
        }
        vector<int> spiralOrder(vector<vector<int> > &matrix) {
            vector<int> result;
            int m = matrix.size();
            if(m == 0) return result;
            
            int n = matrix[0].size();
            int **visited= new int*[m];
            for(int i = 0; i < m; i++){
                visited[i] = new int[n];
                memset(visited[i], 0, sizeof(int)*n);
            }
            dfs(0, 0, m, n, matrix, result, visited);
            
            for(int i = 0; i < m; i++)
                delete [] visited[i];
            delete []visited;
            return result;
            
            
        }
    };

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

链接：https://leetcode.com/problems/spiral-matrix-ii/

class Solution {
    public:
        void dfs(int xi, int yi, const int &n, vector<vector<int> > &result, int &value){
            result[xi][yi] = value++;
             while(yi+1 < n && !result[xi][yi+1]){  // 四个while循环刚好跑了大正圈
                result[xi][yi+1] = value++;
                yi = yi+1;
            }
            while(xi+1 < n && !result[xi+1][yi]){  
                result[xi+1][yi] = value++;
                xi = xi+1;
            }
            while(yi-1 >= 0 && !result[xi][yi-1]){  
                result[xi][yi-1] = value++;
                yi = yi-1;
            }
            while(xi-1 >= 0 && !result[xi-1][yi]){  
                result[xi-1][yi] = value++;
                xi = xi-1;
            }
            if(yi+1 < n && !result[xi][yi+1]) dfs(xi, yi+1, n, result, value);
        }
        
        vector<vector<int> > generateMatrix(int n) {
            vector<vector<int> >result;
            if(n == 0) return result;
            for(int i = 0; i < n; i++){  // 初始化result
                vector<int> temp(n, 0);
                result.push_back(temp);
            }
            int value = 1;
            dfs(0,0, n, result, value);
            return result;
            
        }
    };