「算法刷题」螺旋矩阵

Posted on Edited on

一、螺旋矩阵

LeetCode题目 相关题目类型 相关链接
54 螺旋矩阵（中等难度） https://leetcode-cn.com/problems/design-linked-list/

题解链接：https://leetcode-cn.com/problems/spiral-matrix/solution/cxiang-xi-ti-jie-by-youlookdeliciousc-3/

这里的方法不需要记录已经走过的路径，所以执行用时和内存消耗都相对较小

1、首先设定上下左右边界。

2、其次向右移动到最右，此时第一行因为已经使用过了，可以将其从图中删去，体现在代码中就是重新定义上边界。
3、判断若重新定义后，上下边界交错，表明螺旋矩阵遍历结束，跳出循环，返回答案。

4、若上下边界不交错，则遍历还未结束，接着向下向左向上移动，操作过程与第一，二步同理
不断循环以上步骤，直到某两条边界交错，跳出循环，返回答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        // 定义结果数组
        vector <int> ans;
        if(matrix.empty()) return ans; //若数组为空，直接返回答案
        //赋值上下左右边界
        int u = 0; 
        int d = matrix.size() - 1;// 行的数目-1
        int l = 0;
        int r = matrix[0].size() - 1;// 列的数目-1
        // 右下左上 。。
        while(true)
        {
            for(int i = l; i <= r; ++i) ans.push_back(matrix[u][i]); //向右移动直到最右
            if(++ u > d) break; //重新设定上边界，若上边界大于下边界，则遍历遍历完成，下同
            for(int i = u; i <= d; ++i) ans.push_back(matrix[i][r]); //向下
            if(-- r < l) break; //重新设定有边界
            for(int i = r; i >= l; --i) ans.push_back(matrix[d][i]); //向左
            if(-- d < u) break; //重新设定下边界
            for(int i = d; i >= u; --i) ans.push_back(matrix[i][l]); //向上
            if(++ l > r) break; //重新设定左边界
        }
        return ans;
    }
};

螺旋矩阵2

LeetCode题目 相关题目类型 相关链接
5459 螺旋矩阵2（中等难度） 59. 螺旋矩阵 II - 力扣（LeetCode） (leetcode-cn.com) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n,vector<int>(n,0));// 定义一个二位数组
        
        int startx = 0, starty = 0; // 定义每循环一个圈的起始位置
        int loop=n/2;//每个圈循环几次，例如n为奇数3，那么loop = 1 只是循环一圈，矩阵中间的值需要单独处理
        int mid=n/2;// 矩阵中间的位置，例如：n为3， 中间的位置就是(1，1)，n为5，中间位置为(2, 2)
        int count = 1; // 用来给矩阵中每一个空格赋值
        int offset = 1; // 每一圈循环，需要控制每一条边遍历的长度
        int i,j;

        while(loop--){
            i= startx;
            j= starty;
            // 下面开始的四个for就是模拟转了一圈
            // 模拟填充上行从左到右(左闭右开)
            for (j = starty; j < starty + n - offset; j++) {
                res[startx][j] = count++;
            }
            // 模拟填充右列从上到下(左闭右开)
            for (i = startx; i < startx + n - offset; i++) {
                res[i][j] = count++;
            }
             // 模拟填充下行从右到左(左闭右开)
            for (; j > starty; j--) {
                res[i][j] = count++;
            }
            // 模拟填充左列从下到上(左闭右开)
            for (; i > startx; i--) {
                res[i][j] = count++;
            }
            // 第二圈开始的时候，起始位置要各自加1， 例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1)
            startx++;
            starty++;
            // offset 控制每一圈里每一条边遍历的长度
            offset += 2;
        }
        // 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
        //,n为偶数不用
        if(n%2){
            res[mid][mid]=count;

        }
        return res;

    }
};