54. 螺旋矩阵

题目

自己尝试了好几次，才通过了

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> ans;
        int x = matrix.size(), y = matrix[0].size();
        int sx = 0, ex = x - 1, sy = 0, ey = y - 1;
        int cnt = 0;
        while (sx < ex && sx < ey)
        {
            for (ey = y - 1 - cnt; sy != ey; sy++)
                ans.push_back(matrix[sx][sy]);
            for (ex = x - 1 - cnt; sx != ex; sx++)
                ans.push_back(matrix[sx][sy]);
            for (ey = cnt; sy != ey; sy--)
                ans.push_back(matrix[sx][sy]);
            for (ex = cnt; sx != ex; sx--)
                ans.push_back(matrix[sx][sy]);
            cnt++;
            sx = sy = cnt;
            ex = x - 1 - cnt, ey = y - 1 - cnt;
        }
        if (sx == ex)
        {
            for (ey = y - 1 - cnt; sy <= ey; sy++)
                ans.push_back(matrix[sx][sy]);       
        }
        else if (sy == ey)
        {
            for (ex = x - 1 - cnt; sx <= ex; sx++)
                ans.push_back(matrix[sx][sy]);
        }
        return ans;
    }
};

这道题的思路一开始是借助卡哥讲的一道类似题59.螺旋矩阵II里面的一句话：左闭右开填充。

然后就这么盲目的做了，然后当然就是报错啦。

错误的写法：

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> ans;
        int x = matrix.size(), y = matrix[0].size();
        int sx = 0, ex = 0, sy = 0, ey = 0;
        int cnt = - 1, n = 0;

        if (min(x, y) % 2 == 0)
            n = min(x, y) / 2;
        else
            n = min(x, y) / 2 + 1;
        while (++cnt < n)
        {
            sx = sy = cnt;
            for (ey = y - 1 - cnt; sy != ey; sy++)
                ans.push_back(matrix[sx][sy]);
            for (ex = x - 1 - cnt; sx != ex; sx++)
                ans.push_back(matrix[sx][sy]);
            for (ey = cnt; sy != ey; sy--)
                ans.push_back(matrix[sx][sy]);
            for (ex = cnt; sx != ex; sx--)
                ans.push_back(matrix[sx][sy]);
        }
    }
};

这个连样例是matrix = [[1,2,3],[4,5,6],[7,8,9]]都没通过。

为啥，分析了一下，见图：

因此要单独考虑线和点的情况，while循环里面考虑的只是圈的情况，那么为了让while循环里面考虑的只是圈的情况，就要在while循环的控制条件上做文章了，写成while (sx < ex && sx < ey)能保证在while循环里面是个圈。

然后单独考虑线和点的情况的代码如下：

if (sx == ex)
    {
        for (ey = y - 1 - cnt; sy <= ey; sy++)
            ans.push_back(matrix[sx][sy]);       
    }
    else if (sy == ey)
    {
        for (ex = x - 1 - cnt; sx <= ex; sx++)
            ans.push_back(matrix[sx][sy]);
    }

注意不能写成

if (sx == ex)
    {
        for (ey = y - 1 - cnt; sy <= ey; sy++)
            ans.push_back(matrix[sx][sy]);       
    }
    else (sy == ey)
    {
        for (ex = x - 1 - cnt; sx <= ex; sx++)
            ans.push_back(matrix[sx][sy]);
    }

这样的写法会让点的情况下，该点被重复填充两次。