螺旋矩阵

螺旋矩阵 :grinning:

坚持循环不变量原则(左闭右开)

模拟顺时针画矩阵的过程: O(n^2)

  • 填充上行从左到右
  • 填充右列从上到下
  • 填充下行从右到左
  • 填充左列从下到上

leetcode 59 螺旋矩阵2

题目

给你一个正整数 n ,生成一个包含 1 到 n^2 所有元素,且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix

code

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
class Solution {
public:
vector<vector<int>> generateMatrix(int n)
{
int i = 0;
int j = 0;
int count = 1; //从1到n*n
int column = n; //每一个循环中的列数
int line = n; //每一个循环中的行数
int circle = n / 2;//循环n/2圈
vector<vector<int>> matrix(n, vector<int>(n, 0));//vector创建二维数组
while (circle--)
{

for (int c = 0;c < column - 1;c++)
matrix[i][j++] = count++;
for (int l = 0;l < line - 1;l++)
matrix[i++][j] = count++;
for (int c = 0;c < column - 1;c++)
matrix[i][j--] = count++;
for (int l = 0;l < line - 1;l++)
matrix[i--][j] = count++;
column -= 2; //每循环一圈,需要排列的行数和列数都 -2
line -= 2;
j++; //第二圈的列的起始位置要从第一圈的终点右移动一格,因此 j + 1
i++; //虽然第二圈行的起始位置 = 第一圈终点的行的位置,但是最后一个for循环使行数多减去了1,因此 i + 1
}
if (n % 2 != 0) //n为奇数时,中间的单独赋值
matrix[n / 2][n / 2] = n * n;
return matrix;

}
};

leetcode 54 螺旋矩阵1

题目

给你一个 m 行 n 列的矩阵 matrix ,请按照 顺时针螺旋顺序 ,返回矩阵中的所有元素。

code

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
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix)
{

int row = matrix.size(); //每一个循环中的行数
int column = matrix[0].size(); //每一个循环中的列数
vector<int> result(row * column, 0);//指定容器的大小,否则可能出现空指针
if (matrix.size() == 0 || matrix[0].size() == 0) //首先判断matrix是否为0
return result;

int count = 0;
int i = 0; //实时位置
int j = 0;
int circle = min(column, row)/2; //由于不是方块,取最小值的一半
while (circle--)
{
for(int c = 0;c < column - 1;c++)
result[count++] = matrix[i][j++];
for (int r = 0;r < row - 1;r++)
result[count++] = matrix[i++][j];
for(int c = 0;c < column - 1;c++)
result[count++] = matrix[i][j--];
for (int r = 0;r < row - 1;r++)
result[count++] = matrix[i--][j];
column -= 2;
row -= 2;
j++; //第二圈的列的起始位置要从第一圈的终点右移动一格,因此 j + 1
i++;//虽然第二圈行的起始位置 = 第一圈终点的行的位置,但是最后一个for循环使行数多减去了1,因此 i + 1

}
if (min(matrix[0].size(), matrix.size()) % 2 != 0)
{
if (column < row)
for (int k = 0;k < row;k++)
result[count++] = matrix[i++][j]; //此处是i++还是j++别搞混了
else
for (int k = 0;k < column;k++)
result[count++] = matrix[i][j++];
}
return result;
}
};
  • Copyrights © 2023-2025 Hexo

请我喝杯咖啡吧~

支付宝
微信