# 2020-09-03：裸写算法：回形矩阵遍历。

2020-11-06 21:50:39

``````package test37_spiralorder

import (
"fmt"
"testing"
)

//https://leetcode-cn.com/problems/spiral-matrix/solution/luo-xuan-ju-zhen-by-leetcode-solution/
//go test -v -test.run TestSpiralOrder
func TestSpiralOrder(t *testing.T) {

const N = 3
matrix := make([][]int, N)
for i := 0; i < N; i++ {
matrix[i] = make([]int, N)
for j := 0; j < N; j++ {
matrix[i][j] = i*N + j + 1
}
}
fmt.Println(matrix)
ret := spiralOrder1(matrix)
fmt.Println(ret, "方法一：模拟，位图")
ret = spiralOrder2(matrix)
fmt.Println(ret, "方法二：模拟")
ret = spiralOrder3(matrix)
fmt.Println(ret, "方法三：按层模拟")

}

//方法一：模拟，位图
func spiralOrder1(matrix [][]int) []int {
if len(matrix) == 0 || len(matrix[0]) == 0 {
return []int{}
}
rows, columns := len(matrix), len(matrix[0])
visited := make([]byte, (rows*columns+7)/8)

var (
total          = rows * columns
order          = make([]int, total)
row, column    = 0, 0
directions     = [][]int{[]int{0, 1}, []int{1, 0}, []int{0, -1}, []int{-1, 0}}
directionIndex = 0
)

for i := 0; i < total; i++ {
order[i] = matrix[row][column]
SetBitMapValue(visited, row*columns+column, true)
nextRow, nextColumn := row+directions[directionIndex][0], column+directions[directionIndex][1]
if nextRow < 0 ||
nextRow >= rows ||
nextColumn < 0 ||
nextColumn >= columns ||
GetBitMapValue(visited, nextRow*columns+nextColumn) {
directionIndex = (directionIndex + 1) % 4
}
row += directions[directionIndex][0]
column += directions[directionIndex][1]
}
return order
}

//方法二：模拟
func spiralOrder2(matrix [][]int) []int {
if len(matrix) == 0 || len(matrix[0]) == 0 {
return []int{}
}
rows, columns := len(matrix), len(matrix[0])
visited := make([][]bool, rows)
for i := 0; i < rows; i++ {
visited[i] = make([]bool, columns)
}

var (
total          = rows * columns
order          = make([]int, total)
row, column    = 0, 0
directions     = [][]int{[]int{0, 1}, []int{1, 0}, []int{0, -1}, []int{-1, 0}}
directionIndex = 0
)

for i := 0; i < total; i++ {
order[i] = matrix[row][column]
visited[row][column] = true
nextRow, nextColumn := row+directions[directionIndex][0], column+directions[directionIndex][1]
if nextRow < 0 || nextRow >= rows || nextColumn < 0 || nextColumn >= columns || visited[nextRow][nextColumn] {
directionIndex = (directionIndex + 1) % 4
}
row += directions[directionIndex][0]
column += directions[directionIndex][1]
}
return order
}

//方法三：按层模拟
func spiralOrder3(matrix [][]int) []int {
if len(matrix) == 0 || len(matrix[0]) == 0 {
return []int{}
}
var (
rows, columns            = len(matrix), len(matrix[0])
order                    = make([]int, rows*columns)
index                    = 0
left, right, top, bottom = 0, columns - 1, 0, rows - 1
)

for left <= right && top <= bottom {
for column := left; column <= right; column++ {
order[index] = matrix[top][column]
index++
}
for row := top + 1; row <= bottom; row++ {
order[index] = matrix[row][right]
index++
}
if left < right && top < bottom {
for column := right - 1; column > left; column-- {
order[index] = matrix[bottom][column]
index++
}
for row := bottom; row > top; row-- {
order[index] = matrix[row][left]
index++
}
}
left++
right--
top++
bottom--
}
return order
}

//获取位图第index元素的值
func GetBitMapValue(data []byte, index int) bool {
return data[index/8]&(1<<(index%8)) != 0
}

//设置位图第index元素的值
func SetBitMapValue(data []byte, index int, v bool) {
if v {
data[index/8] |= 1 << (index % 8)
} else {
data[index/8] &= ^(1 << (index % 8))
}
}``````

https://my.oschina.net/u/4553401/blog/4544055