Leetcode 54. Spiral Matrix (cpp)

题目

解法1：layer by layer

一层一层的访问数组，每一层按照四个方向顺序遍历，并且预先定义每个方向访问元素的个数

class Solution {
    
public:vector<int> spiralOrder(vector<vector<int>>& matrix) {
    if(matrix.empty()) return {
    };// pre-define the number of steps needed in each stepint r = matrix[0].size(), l = matrix[0].size() - 1;int u = matrix.size() - 2, d = matrix.size() - 1;pair<int,int> curr{
    0,-1};int unvisited = matrix.size() * matrix[0].size();vector<int> ans;while(unvisited > 0){
    // move towards four direction in clockwise (right -> down -> left -> up), return the ans instantly if all the elements are visited// moving rightfor(int i=0;i<r;i++){
    curr.second += 1;ans.push_back(matrix[curr.first][curr.second]);unvisited -= 1;if(!unvisited) return ans;}// move downfor(int i=0;i<d;i++){
    curr.first += 1;ans.push_back(matrix[curr.first][curr.second]);unvisited -= 1;if(!unvisited) return ans;}// move leftfor(int i=0;i<l;i++){
    curr.second -= 1;ans.push_back(matrix[curr.first][curr.second]);unvisited -= 1;if(!unvisited) return ans;}// move upperfor(int i=0;i<u;i++){
    curr.first -= 1;ans.push_back(matrix[curr.first][curr.second]);unvisited -= 1;if(!unvisited) return ans;}// every circle will cause the four direction steps to decrement 2r -= 2;l -= 2;u -= 2;d -= 2;}return ans;}
};

解法2：seen数组

也是按顺序预定义四个方向，但是通过seen数组来判断每个方向前进的步数

class Solution {
    
public:vector<int> spiralOrder(vector<vector<int>>& matrix) {
    if(matrix.empty()) return {
    };// define the directions defined in a clock wise directionvector<pair<int,int>> dirs{
    {
    0,1},{
    1,0},{
    0,-1},{
    -1,0}};// use seen to keep track of the visited elements in the outer layersvector<vector<int>> seen(matrix.size(),vector<int>(matrix[0].size(),0));int num_ele = matrix.size() * matrix[0].size();int r = 0, c = 0, d_ind = 0;vector<int> ans;for(int i=0;i<num_ele;i++){
    ans.push_back(matrix[r][c]);seen[r][c] = 1;int x = r + dirs[d_ind].first;int y = c + dirs[d_ind].second;// if current directions are not out of bounds, keep in the same directionif(x >= 0 && y >= 0 && x < matrix.size() && y < matrix[0].size() && !seen[x][y]){
    r = x;c = y;}else{
     // if out of bounds, move to the next directionsd_ind = (d_ind + 1) % 4;r = r + dirs[d_ind].first;;c = c + dirs[d_ind].second;}}return ans;}
};

二刷

二刷在第二种解法上作了改进，是的解法更加的直观一些，不需要在一个方向走完的时候手动去加一步来避免重复一个位置

class Solution:def spiralOrder(self, matrix: List[List[int]]) -> List[int]:m,n = len(matrix),len(matrix[0])seen = set()dirs = [[0,1],[1,0],[0,-1],[-1,0]]row = 0col = -1res = []d_ind = 0cnt = 0while cnt < m*n:x = row + dirs[d_ind][0]y = col + dirs[d_ind][1]if x >= 0 and x < m and y >= 0 and y < n and (x,y) not in seen:row = xcol = yres.append(matrix[row][col])seen.add((row,col))cnt += 1else:d_ind = (d_ind+1) % 4return res

下面两道follow up，分别用这边的第一种和第二种解法来解
https://blog.csdn.net/qq_37821701/article/details/123680877
https://blog.csdn.net/qq_37821701/article/details/123680971