LeetCode 54. Spiral Matrix 剑指Offer 29. 顺时针打印矩阵 [Medium]

LeetCode 54. Spiral Matrix & 剑指Offer 29. 顺时针打印矩阵

题目来源:https://leetcode.com/problems/spiral-matrix

题目难度:Medium

解答1[Java]:

核心思想

从外层向内层,一圈一圈地遍历。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List ans = new ArrayList();
if (matrix.length == 0)
return ans;
int r1 = 0, r2 = matrix.length - 1;
int c1 = 0, c2 = matrix[0].length - 1;
while (r1 <= r2 && c1 <= c2) {
for (int c = c1; c <= c2; c++) ans.add(matrix[r1][c]);
for (int r = r1 + 1; r <= r2; r++) ans.add(matrix[r][c2]);
if (r1 < r2 && c1 < c2) {
for (int c = c2 - 1; c > c1; c--) ans.add(matrix[r2][c]);
for (int r = r2; r > r1; r--) ans.add(matrix[r][c1]);
}
r1++;
c1++;
r2--;
c2--;
}
return ans;
}
}

解答2[Java]:

核心思想

这个才是真的全自动顺时针打印。设计了两个数组,一个 directionOfRow,一个directionOfColumn,这样,directionOfRow[i] 和 directionOfColumn[i] 这么一组数就表示下一步该怎么走,如果越界了,那么 ++i,相当于换成下一种走法。第一圈使用数组行数和列数来判定是否越界,第二圈就要靠 seen 数组来判断。

代码

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
import java.util.ArrayList;
import java.util.List;

class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> ans = new ArrayList();
if (matrix.length == 0) return ans;
int R = matrix.length, C = matrix[0].length;
boolean[][] seen = new boolean[R][C];
int[] directionOfRow = {0, 1, 0, -1};
int[] directionOfColumn = {1, 0, -1, 0};
int r = 0, c = 0, dierectionCount = 0;
for (int i = 0; i < R * C; ++i) {
ans.add(matrix[r][c]);
seen[r][c] = true;
int nextR = r + directionOfRow[dierectionCount];
int nextC = c + directionOfColumn[dierectionCount];
if (0 <= nextR && nextR < R && 0 <= nextC && nextC < C && !seen[nextR][nextC]) {
r = nextR;
c = nextC;
} else {
dierectionCount = (dierectionCount + 1) % 4;
r += directionOfRow[dierectionCount];
c += directionOfColumn[dierectionCount];
}
}
return ans;
}
}