54. 螺旋矩阵（定义四个方向然后遍历类）
文章目录
- 54. 螺旋矩阵
- 59. 螺旋矩阵 II
- LCR 146. 螺旋遍历二维数组(剑指offer29题）
54. 螺旋矩阵
54. 螺旋矩阵
给你一个 m 行 n 列的矩阵matrix，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
示例 2：
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]
提示：
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 10
- -100 <= matrix[i][j] <= 100
思路： 按照顺时针遍历矩阵，将二维矩阵看成一维矩阵遍历每个元素，当索引越界或者元素已经被访问过则改变方向，改变方向顺序为右，下，左，上。
Go代码
func spiralOrder(matrix [][]int) []int {
/*剑指offer 面试题29，p161,ACWing 40
按照顺时针遍历矩阵，将二维矩阵看成一维矩阵遍历每个元素，当索引越界或者元素已经被访问过则改变方向，
改变方向顺序为右，下，左，上*/
if len(matrix) == 0 || len(matrix[0]) == 0 {
return []int{}
}
res := make([]int,len(matrix) * len(matrix[0]))
// 定义四个方向 上，右，下，左 (上即行号减一，右即列号加1，以此类推)
dx := []int{-1,0,1,0}
dy := []int{0,1,0,-1}
x,y,d := 0,0,1 // 从起点开始往右移动
// 定义是否访问过的数组，并初始化
isVisited := make([][]bool,len(matrix))
for i,_ := range isVisited {
isVisited[i] = make([]bool,len(matrix[0]))
}
for i := 0;i < len(matrix) * len(matrix[0]);i++ {
res[i] = matrix[x][y] // 当前节点加入结果数组
isVisited[x][y] = true // 标记当前节点已经访问过
// 继续遍历下一个节点，但需要用下临时变量，不要用x = x + dx[d],因为等下可能还要用到原x
a := x + dx[d]
b := y + dy[d]
// 如果当前节点越界了，或者已经遍历过了，则可以换方向了
if a < 0 || a >= len(matrix) || b < 0 || b >= len(matrix[0]) || isVisited[a][b] {
d = (d + 1) % 4
// 新方向算出的下一个节点坐标，用到了原x,y
a = x + dx[d]
b = y + dy[d]
}
// 已经明确找到下一个节点位置了，可以继续遍历了
x = a
y = b
}
return res
}
59. 螺旋矩阵 II
给你一个正整数 n ，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
示例 1：
输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]
示例 2：
输入：n = 1
输出：[[1]]
提示：
- 1 <= n <= 20
Go代码
func generateMatrix(n int) [][]int {
/*思路和54题完全一样*/
if n == 0 {
return [][]int{}
}
// 定义相关切片并初始化
res := make([][]int,n)
isVisited := make([][]bool,n)
for i := 0;i < n;i++ {
res[i] = make([]int,n)
isVisited[i] = make([]bool,n)
}
// 定义四个方向 右，下，左，上，右边就是列号加1，以此类推
dx := []int{0,1,0,-1}
dy := []int{1,0,-1,0}
x,y,d := 0,0,0 // 起点和初始方向向右
for i := 1; i <= n * n ;i++ {
res[x][y] = i
isVisited[x][y] = true
a := x + dx[d]
b := y + dy[d]
// 越界了，或者已经访问过了，可以换方向了
if a < 0 || a >= n || b < 0 || b >= n || isVisited[a][b] {
d = (d + 1) % 4
a = x + dx[d]
b = y + dy[d]
}
x = a
y = b
}
return res
}
LCR 146. 螺旋遍历二维数组(剑指offer29题）
LCR 146. 螺旋遍历二维数组(剑指offer29题）
给定一个二维数组 array，请返回「螺旋遍历」该数组的结果。
螺旋遍历：从左上角开始，按照 向右、向下、向左、向上 的顺序 依次 提取元素，然后再进入内部一层重复相同的步骤，直到提取完所有元素。
示例 1：
输入：array = [[1,2,3],[8,9,4],[7,6,5]]
输出：[1,2,3,4,5,6,7,8,9]
示例 2：
输入：array = [[1,2,3,4],[12,13,14,5],[11,16,15,6],[10,9,8,7]]
输出：[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]
限制：
- 0 <= array.length <= 100
- 0 <= array[i].length <= 100
注意：本题与主站 54 题相同：https://leetcode-cn.com/problems/spiral-matrix/
Go代码
func spiralArray(array [][]int) []int {
/*
按照顺时针遍历矩阵，将二维矩阵看成一维矩阵遍历每个元素，当索引越界或者元素已经被访问过则改变方向，
改变方向顺序为右，下，左，上
*/
if len(array) == 0 || len(array[0]) == 0 {
return []int{}
}
res := make([]int,len(array) * len(array[0]))
// 定义方向，右，下，左，上
dx := []int{0,1,0,-1}
dy := []int{1,0,-1,0}
x,y,d := 0,0,0 // 起始位置和其实方向（向右）
// 记录位置是否访问过
isVisited := make([][]bool,len(array))
for i:= 0;i < len(isVisited);i++ {
isVisited[i] = make([]bool,len(array[0]))
}
for i := 0;i < len(array) * len(array[0]);i++ {
res[i] = array[x][y]
isVisited[x][y] = true
a,b := x + dx[d],y + dy[d] // 下一个需要遍历的位置
if a < 0 || a >= len(array) || b < 0 || b >= len(array[0]) || isVisited[a][b] {
d = (d + 1) % 4
a = x + dx[d]
b = y + dy[d]
}
x,y = a,b
}
return res
}
