按圈螺旋遍历矩阵

思路

观察可知螺旋遍历每圈的遍历模式是一样的,每一圈一般可以分解为下图的四步，这样就方便放入for循环。设每一圈遍历的起始点为matrix[z][z]，可以总结出每圈的遍历模式如下，其中r c分别为本圈行列数：

for(int i = 0; i < c - 1; i++) res.push_back(matrix[z][z+i]); //左上到右上
for(int i = 0; i < r - 1; i++) res.push_back(matrix[z+i][z+c-1]);//右上到右下
for(int i = c - 1; i > 0; i--) res.push_back(matrix[z+r-1][z+i]);//右下到左下
for(int i = r - 1; i > 0; i--) res.push_back(matrix[z+i][z]);//左下到左上

这样一来只需要找到每圈起始点的坐标z变化的范围和每圈的r与c的规律即可，显然z从0开始一直可以到达矩阵的中心最小的圈，而每一圈相比上一圈行数r列数c都减少2

int center = min((m-1)/2, (n-1)/2);
for(int z = 0; z <= center; z++) {
    ...
    r -= 2;
    c -=2;
}

剩下的就是考虑特殊情况，是否有不符合这种遍历模式的圈呢？可以发现当r=1或c=1时上述遍历模式会出错，因此要对r,c为1的情况进行判断

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int> > &matrix) {
        vector<int> res;
        int m = matrix.size();
        if(!m) return res;
        int n = matrix[0].size();
        int center = min((m-1)/2, (n-1)/2);
        int r = m, c = n;
        int z;
        for(z = 0; z <= center ; z++){
            for(int i = 0; i < c - 1; i++) res.push_back(matrix[z][z+i]);
            for(int i = 0; i < r - 1; i++) res.push_back(matrix[z+i][z+c-1]);
            // 当r=1或c=1时，只需要左上到右上和右上到右下的两步遍历，
            // 但会漏掉matrix[z+r-1][z+c-1]，因此补上
            if(r == 1 || c == 1) res.push_back(matrix[z+r-1][z+c-1]);
            else {
                for(int i = c - 1; i > 0; i--) res.push_back(matrix[z+r-1][z+i]);
                for(int i = r - 1; i > 0; i--) res.push_back(matrix[z+i][z]);
            }
            r -= 2;
            c -= 2;
        }
        return res;
    }
};