54.md

【中规中矩】54. 螺旋矩阵 (多语言多解法实现）

解题思路

纯考验代码功底。定义4个变量top, bottom, left, right分别表示当前的上下左右起始位置。从第top行开始，输出[left, right]下标位置的元素。自增top为下一次输出top行做准备。同样地，输出第right列，从[top, bottom]行，自减right。然后输出第bottom 行，从[right, left]的元素（注意是逆序）。自减bottom，输出left列，从[bottom, top]行，（也是逆序）。注意中间若是出现了top > bottom 或者right < left就提前跳出。

易错点： 下面提前退出的条件写反了： if (bottom < top) { // !!! Not bottom > top!!!! bottom should be > top in normal!

代码

class Solution1 {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int M = matrix.size();
        int N = matrix[0].size();
        vector<int> res;

        int top = 0;
        int bottom = M - 1;
        int left = 0;
        int right = N - 1;
        while (true) {
            // top row
            for (int i = left; i <= right; i++) {
                res.push_back(matrix[top][i]);
            }

            top++;
            if (top > bottom) {
                break;
            }

            // right col
            for (int j = top; j <= bottom; j++) {
                res.push_back(matrix[j][right]);
            }

            right--;
            if (right < left) {
                break;
            }

            // bottom row
            for (int k = right; k >= left; k--) {
                res.push_back(matrix[bottom][k]);
            }

            bottom--;
            if (bottom < top) {
                break;
            }

            // left col 
            for (int l = bottom; l >= top; l--) {
                res.push_back(matrix[l][left]);
            }

            left++;
            if (left > right) {
                break;
            }
        }

        return res;
    }
};

class Solution2 {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int M = matrix.size();
        int N = matrix[0].size();
        vector<int> res;

        int top = 0;
        int bottom = M - 1;
        int left = 0;
        int right = N - 1;
        while (left <= right && top <= bottom) {
            // top row
            for (int i = left; i <= right; i++) {
                res.push_back(matrix[top][i]);
            }

            // right col
            for (int j = top + 1; j <= bottom; j++) {
                res.push_back(matrix[j][right]);
            }

            if (left < right && top < bottom) { // essential
                // bottom row
                for (int k = right - 1; k > left; k--) {
                    res.push_back(matrix[bottom][k]);
                }

                // left col 
                for (int l = bottom; l > top; l--) {
                    res.push_back(matrix[l][left]);
                }
            }

            top++;
            right--;
            bottom--;
            left++;
        }

        return res;
    }
};

class Solution1(object):
    def spiralOrder(self, matrix):
        if matrix is None or matrix[0] is None:
            return None

        M = len(matrix)
        N = len(matrix[0])
        top = 0
        bottom = M - 1
        left = 0
        right = N - 1
        res = list()
        while (len(res) < M * N):
            for i in range(left, right + 1):
                res.append(matrix[top][i])
            top += 1
            if (top > bottom):
                break
            
            for j in range(top, bottom + 1):
                res.append(matrix[j][right])
            right -= 1
            if (right < left):
                break

            for k in range(right, left - 1, -1):
                res.append(matrix[bottom][k])
            bottom -= 1
            if (bottom < top):
                break
            
            for l in range(bottom, top - 1, -1):
                res.append(matrix[l][left])
            left += 1
            if (left > right):
                break
        
        return res

class Solution2(object):
    def spiralOrder(self, matrix):
        if matrix is None or matrix[0] is None:
            return None

        M = len(matrix)
        N = len(matrix[0])
        top = 0
        bottom = M - 1
        left = 0
        right = N - 1
        res = list()
        while (left <= right and top <= bottom):
            # top row
            for i in range(left, right + 1): 
                res.append(matrix[top][i])

            # right col
            for j in range (top + 1, bottom + 1):
                res.append(matrix[j][right])
        

            if (left < right and top < bottom): # essential
                # bottom row
                for k in range(right - 1, left, -1):
                    res.append(matrix[bottom][k])

                # left col 
                for l in range(bottom, top, -1): 
                    res.append(matrix[l][left])

            top += 1;
            right -= 1;
            bottom -= 1;
            left += 1;

        
        return res;

点我赞赏作者

github 题解