LeetCode 54 Spiral Matrix

标签: LeetCode 发布于:2021-05-31 16:20:40 编辑于:2021-05-31 16:33:52 浏览量:1317

分析

将二维数据以螺旋形的方式 flat 成一维数组。

用递归的方式做可能更简单一些,因为每当搞定完一行或一列后,剩下的可以同样处理。

我的解法

0ms 6.8 MB,O(m*n) 复杂度。

总的来说就是绕圈圈,emmmm,每次绕圈要更新:

  1. 新数组的索引 c,
  2. 旧数组的索引 i 和 j,
  3. 方向 d,
  4. 推进距离 w 和 h。
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        auto m = matrix.size();
        auto n = matrix[0].size();
        int i = 0, j = 0, d = 0, c = 0;
        int w = n;
        int h = m;
        vector<int> ans(m*n);
        while (c < m*n) {
            switch (d) {
                case 0:
                    for(int k=0;k<w;k++) {
                        ans[c++] = matrix[i][j++];
                    }
                    j--;
                    i++;
                    h--;
                    break;
                case 1:
                    for(int k=0;k<h;k++) {
                        ans[c++] = matrix[i++][j];
                    }
                    i--;
                    j--;
                    w--;
                    break;
                case 2:
                    for(int k=0;k<w;k++) {
                        ans[c++] = matrix[i][j--];
                    }
                    j++;
                    i--;
                    h--;
                    break;
                case 3:
                    for(int k=0;k<h;k++) {
                        ans[c++] = matrix[i--][j];
                    }
                    i++;
                    j++;
                    w--;
                    break;
            }
            d++;
            d %= 4;
        }
        return ans;
    }
};

一行代码的解法

https://leetcode.com/problems/spiral-matrix/discuss/20571/1-liner-in-Python-%2B-Ruby

def spiralOrder(self, matrix):
    return matrix and [*matrix.pop(0)] + self.spiralOrder([*zip(*matrix)][::-1])

这可太 6 了。

上面代码的思路是每次处理最上面的一行,然后将剩余矩阵向左旋转 90°,这样我们就可以省却方向变化带来的麻烦。

上述链接里有图示。

未经允许,禁止转载,本文源站链接:https://iamazing.cn/