模拟法螺旋遍历矩阵：54.螺旋矩阵（Kotlin）
模拟法螺旋遍历矩阵：54.螺旋矩阵（Kotlin）
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
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/spiral-matrix 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路
模拟法。
模拟有一个遍历机器人，按照螺旋轨迹（4个方向：向右，向下，向左，向上）每一步一个格子移动（很显然，遍历完矩阵，要移动 m*n 次）。 已经遍历了的格子，我们标记一下，作为转弯的边界条件： visited[row][col] = true。 另外，在第一层遍历的时候，转弯的边界条件是不得超出矩阵的坐标范围，也就是: 0 < row < m 0 < col < n
关于方向向量： direction[4][2] 4个方向：向右，向下，向左，向上 （行下标，列下标） 向右，(0,+1) 向下，(+1,0) 向左，(0,-1) 向上，(-1,0)
代码
class Solution {
fun spiralOrder(matrix: Array<IntArray>): List<Int> {
val ans = mutableListOf<Int>()
val rows = matrix.size
if (rows == 0) {
return emptyList()
}
val cols = matrix[0].size
var row = 0
var col = 0
val total = rows * cols
val direction = arrayOf(
arrayOf(0, 1), // right, row 不变,col + 1
arrayOf(1, 0), // down, col 不变, row + 1
arrayOf(0, -1), // left, row 不变, col - 1
arrayOf(-1, 0) // up, col 不变, row - 1
)
// 是否已经访问过, 作为转弯的边界条件
val visited: Array<BooleanArray> = Array(rows) {
BooleanArray(cols) { false }
}
// direction 的下标, 取值为: 0, 1, 2, 3
var directionIndex = 0
// visit [ 0 ~ total-1 ] element
for (i in 0 until total) {
ans.add(matrix[row][col])
visited[row][col] = true
val nextRow = row + direction[directionIndex][0]
val nextCol = col + direction[directionIndex][1]
if (shouldTurnDirection(nextRow, nextCol, rows, cols, visited)) {
directionIndex++
directionIndex %= 4
}
// visit next element
row += direction[directionIndex][0]
col += direction[directionIndex][1]
}
return ans
}
fun shouldTurnDirection(nextRow: Int, nextCol: Int, rows: Int, cols: Int, visited: Array<BooleanArray>): Boolean {
return nextRow >= rows // 超过最大行
|| nextCol >= cols // 超过最大列
|| nextRow < 0 // 0行
|| nextCol < 0 // 0列
|| visited[nextRow][nextCol] // 已经遍历过
}
}作者：chenguangjian2020 链接：https://leetcode-cn.com/problems/spiral-matrix/solution/luo-xuan-ju-zhen-mo-ni-fa-kotlin-by-chen-b5e8/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
腾讯云开发者
