Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode Spiral Matrix

Leetcode algorithms 第 54 题:Spiral Matrix。

题目

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].

解答

螺旋矩阵,直接按照题目要求的螺旋形状模拟,逐环进行,每次从最左上角的顶点开始,依次向右、向下、向左、向上旋转一圈,注意,只有行数大于2时才要向走,列数大于2时才要向上,否则会重复输出某些值。

具体代码如下:

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int> > &matrix) {
        vector<int> ans;
        if (matrix.empty() || matrix[0].empty()) return ans;
        
        int m = matrix.size(), n = matrix[0].size(); //行数、列数
        for (int i = 0, dx = m, dy = n; i <= min((m-1)/2, (n-1)/2); ++i, dx -= 2, dy -= 2) //逐环进行
        {
            int x = i, y = i; //起点坐标
            for (int j = 0; j < dy; j++) ans.push_back(matrix[x][y+j]); //向右走
            y += dy - 1;
            for (int j = 1; j < dx; j++) ans.push_back(matrix[x+j][y]); //向下走
            x += dx - 1;
            if (dx > 1) //行数大于2才要往回走
            {
                for (int j = 1; j < dy; j++) ans.push_back(matrix[x][y-j]); //向左走
                y -= dy - 1;
            }
            if (dy > 1) //列数大于2才要往回走
            {
                for (int j = 1; j < dx-1; j++) ans.push_back(matrix[x-j][y]); //向上走
            }
        }
        return ans;
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论