算法训练之 -- 螺旋矩阵

螺旋矩阵

1. 思路

​ 题目：给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。59. 螺旋矩阵 II - 力扣（LeetCode）

思路：

初始化一个 n×n 大小的矩阵 res，然后模拟整个向内环绕的填入过程：填充上行从左到右，填充右列从上到下，填充下行从右到左，填充左列从下到上

1. 定义当前左右上下边界 left,right,top,bottom，初始值 num = 1，迭代终止值 tar = n * n；
2. 当 num <= tar 时，始终按照 从左到右 从上到下 从右到左 从下到上 填入顺序循环，每次填入后：
   • 执行 num += 1：得到下一个需要填入的数字；
   • 更新边界：例如从左到右填完后，上边界 top += 1，相当于上边界向内缩 1。
3. 使用num <= tar 或者 left <= right && top < bottom作为迭代条件。
4. 最终返回 res 即可。

PS：一定要注意区间的开合，四个方向的填充使用同样的开合方式！

2. 解法

Python

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        ans = [[0]*n for _ in range(n)]
        top, bottom, left, right = 0, n-1, 0, n-1
        num = 1			# 从 1 开始
        while num <= n*n:
            for i in range(left, right+1): # 采用左闭右闭的方式，right需要 +1。	
                ans[top][i] = num
                num += 1
            top += 1
            for i in range(top, bottom+1):
                ans[i][right] = num
                num += 1
            right -= 1
            for i in range(right, left-1, -1):	
                ans[bottom][i] = num
                num += 1
            bottom -= 1
            for i in range(bottom, top-1, -1): # 同样的 range()是默认右开区间，所以top需要 -1。
                ans[i][left] = num
                num += 1
            left += 1
        return ans

C++

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n,vector<int>(n,0));
        int left = 0, top = 0, right = n - 1, bottom = n - 1;
        int num = 1;
        while(left<=right && top<= bottom){	// 使用另外一种判断结束的条件
            for(int i=left; i<= right; i++)	// 同样采用左闭右闭的方式
                res[top][i] = num++;
            top++;
            if(left>right || top>bottom)	// 设置一个提前跳出循环的判断（如果有需要的话）
                break;
            for(int i=top; i<=bottom; i++)
                res[i][right] = num++;
            right--;
            if(left>right || top>bottom)
                break;
            for(int i=right; i>=left; i--)
                res[bottom][i] = num++;
            bottom--;
            if(left>right || top>bottom)
                break;
            for(int i=bottom; i>=top; i--)
                res[i][left] = num++;
            left++;
            if(left>right || top>bottom)
                break;
        }
        return res;
    }
};

3. 变种

(1) 题目：给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。54. 螺旋矩阵 - 力扣（LeetCode）

思路：可以将矩阵看成若干层，首先输出最外层的元素，其次输出次外层的元素，直到输出最内层的元素。（和上面的那个相反）

对于每层，从左上方开始以顺时针的顺序遍历所有元素。假设当前层的左上角位于 (top,left)，右下角位于 (bottom,right)，按照如下顺序遍历当前层的元素。

1. 从左到右遍历上侧元素，依次为 (top,left) 到 (top,right)。

2. 从上到下遍历右侧元素，依次为 (top,right) 到 (bottom+1,right)。

3. 从右到左遍历下侧元素，依次为 (bottom, right) 到 (bottom, left-1)

4. 从下到上遍历左侧元素，依次为 (bottom, left) 到 (top-1, left)

5. 每次遍历完都判断一下 (l > r or t > b)，来决定是否结束循环。

PS：也需要注意区间开合，以及结束条件（此题的矩阵不一定为正方形）

Python

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        n = len(matrix[0])
        m = len(matrix)
        l, t = 0, 0
        r, b = n - 1, m - 1
        ans = []
        while l<=r and t <=b:
            for i in range(l, r+1):		# 遍历 从左到右
                ans.append(matrix[t][i])# 存储元素
            t += 1						# 区间减小
            if l > r or t > b:			# 判断是否结束循环 （很重要！否则在n!=m时，行或列会多遍历一次）
                break
            for i in range(t, b+1):
                ans.append(matrix[i][r])
            r -= 1
            if l > r or t > b:
                break
            for i in range(r, l-1, -1):
                ans.append(matrix[b][i])
            b -= 1
            if l > r or t > b:
                break
            for i in range(b, t-1, -1):
                ans.append(matrix[i][l])
            l += 1
            if l > r or t > b:
                break
        return ans

C++

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int l = 0, r = matrix[0].size() - 1, t = 0, b = matrix.size() - 1;
        vector<int> ans;
        while(l <= r && t <= b){
            for(int i=l; i<=r; i++)
                ans.push_back(matrix[t][i]);
            t++;
            // if(l > r || t > b)
                // break;
            for(int i=t; i<=b; i++)
                ans.push_back(matrix[i][r]);
            r--;
            if(l > r || t > b)
                break;
            for(int i=r; i>=l; i--)
                ans.push_back(matrix[b][i]);
            b--;
            // if(l > r || t > b)
                // break;
            for(int i=b; i>=t; i--)
                ans.push_back(matrix[i][l]);
            l++;
            // if(l > r || t > b)
            //     break;
        }
        return ans;
    }
};

(2) 题目：给定一个二维数组 array，请返回「螺旋遍历」该数组的结果。螺旋遍历：从左上角开始，按照 向右、向下、向左、向上 的顺序 依次 提取元素，然后再进入内部一层重复相同的步骤，直到提取完所有元素LCR 146. 螺旋遍历二维数组 - 力扣（LeetCode）

思路：螺旋矩阵的题目好像都没啥差别，没有很大的改变，记住一个模板就行了。还有一种遍历到矩阵中间的位置，但是用复杂度没有很大差别，没必要特意用。注意一些细节就好了，尤其是边界位置，没很大意思。

Python

# 和上面的同一个模板
class Solution:
    def spiralArray(self, array: List[List[int]]) -> List[int]:
        ans = []
        if not array or not array[0]:
            return ans
        m, n = len(array), len(array[0])
        l, r, t, b = 0, n-1, 0, m-1
        while l<=r and t<=b:
            for i in range(l, r+1):
                ans.append(array[t][i])
            t += 1
            if l > r or t > b:
                break
            for i in range(t, b+1):
                ans.append(array[i][r])
            r -= 1
            if l > r or t > b:
                break
            for i in range(r, l-1, -1):
                ans.append(array[b][i])
            if l > r or t > b:
                break
            b -= 1
            for i in range(b, t-1, -1):
                ans.append(array[i][l])
            l += 1
            if l > r or t > b:
                break       
        return ans

# 遍历到矩阵中间
class Solution:
    def spiralArray(self, array: List[List[int]]) -> List[int]:
        res = []
        h = len(array)
        if h == 0:
            return res
        w = len(array[0])
        for offset in range(min(h, w)//2):
            for i in range(offset, w-1-offset):
                res.append(array[offset][i])
            for i in range(offset, h-1-offset):
                res.append(array[i][w-1-offset])
            for i in range(w-1-offset, offset, -1):
                res.append(array[h-1-offset][i])
            for i in range(h-1-offset, offset, -1):
                res.append(array[i][offset])
        if h >= w:
            if w%2 == 1:
                for i in range(w//2, h-w//2):
                    res.append(array[i][w//2])
        else:
            if h%2 == 1:
                for i in range(h//2, w-h//2):
                    res.append(array[h//2][i])
        return res

C++

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> ans;
        if(matrix.empty()){
            return ans;
        }
        int l = 0, t = 0;
        int r = matrix[0].size() - 1 ; // 列
        int b = matrix.size() - 1;    // 行
        while(true){
            for(int i=l; i<=r; i++) ans.push_back(matrix[t][i]);
            t++;
            if(t>b) break;
            for(int i=t; i<=b; i++) ans.push_back(matrix[i][r]);
            r--;
            if(l>r) break;
            for(int i=r; i>=l; i--) ans.push_back(matrix[b][i]);
            b--;
            if(t>b) break;
            for(int i=b; i>=t; i--) ans.push_back(matrix[i][l]);
            l++;
            if(l>r) break;
        }
        return ans;
    }
};