一、螺旋矩阵
| 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;
}
};