当前位置:网站首页>September 3, 2020: naked writing algorithm: loop matrix traversal.
September 3, 2020: naked writing algorithm: loop matrix traversal.
2020-11-06 21:50:00 【Daily problem of Fuda big frame constructor】
Fogo's answer 2020-09-03:
Method 1 : simulation , Bitmap mode .
Follow Method 2 equally , The difference is auxiliary matrix visited Save space with bitmaps .
Method 2 : simulation .
You can simulate the path of a spiral matrix . The initial position is the upper left corner of the matrix , The initial direction is to the right , When a path goes out of bounds or enters a previously visited location , Turn clockwise , Go to the next direction .
To determine whether a path enters a previously visited location, an auxiliary matrix of the same size as the input matrix is required visited, Each of these elements indicates whether the location has been accessed . When an element is accessed , take visited Set the element at the corresponding position in the to be accessed .
How to judge whether the path is over ? Because every element in the matrix is accessed once , So the length of the path is the number of elements in the matrix , When the length of the path reaches the number of elements in the matrix, it is a complete path , Return the path .
Complexity analysis
Time complexity :O(mn), among m and n The number of rows and columns of the input matrix . Every element in the matrix is accessed once .
Spatial complexity :O(mn). You need to create a size of m×n Matrix visited Record whether each location has been visited .
Method 3 : Layer by layer simulation
You can think of a matrix as layers , First output the outermost element , Second, output the sub outer elements , Until the innermost element is output .
Define the order of a matrix k The distance from the layer to the nearest boundary is k All the vertices of . for example , The outermost elements of the matrix in the figure below are all the first 1 layer , The sub outer elements are the first 2 layer , The rest of the elements are the first 3 layer .
Complexity analysis
Time complexity :O(mn), among m and n The number of rows and columns of the input matrix . Every element in the matrix is accessed once .
Spatial complexity :O(1). In addition to the output array , Space complexity is a constant .
The code to use golang To write , as follows :
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, " Method 1 : simulation , Bitmap ")
ret = spiralOrder2(matrix)
fmt.Println(ret, " Method 2 : simulation ")
ret = spiralOrder3(matrix)
fmt.Println(ret, " Method 3 : Layer by layer simulation ")
}
// Method 1 : simulation , Bitmap
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
}
// Method 2 : simulation
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
}
// Method 3 : Layer by layer simulation
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
}
// Get bitmap No index The value of the element
func GetBitMapValue(data []byte, index int) bool {
return data[index/8]&(1<<(index%8)) != 0
}
// Set bitmap No index The value of the element
func SetBitMapValue(data []byte, index int, v bool) {
if v {
data[index/8] |= 1 << (index % 8)
} else {
data[index/8] &= ^(1 << (index % 8))
}
}
knock go test -v -test.run TestSpiralOrder command , give the result as follows :
版权声明
本文为[Daily problem of Fuda big frame constructor]所创,转载请带上原文链接,感谢
边栏推荐
- The role of theme music in games
- What is the meaning of sector sealing of filecoin mining machine since the main network of filecoin was put online
- 2020-09-09:裸写算法:两个线程轮流打印数字1-100。
- 2020-08-14:数据任务的执行引擎用的哪些?
- Common syntax corresponding table of mongodb and SQL
- 细数软件工程----各阶段必不可少的那些图
- Qt音视频开发46-视频传输UDP版
- How about small and medium-sized enterprises choose shared office?
- To solve the problem that the data interface is not updated after WPF binding set
- With this artifact, quickly say goodbye to spam messages
猜你喜欢
Some operations kept in mind by the front end foundation GitHub warehouse management
预留电池接口,内置充放电电路及电量计,迅为助力轻松搞定手持应用
移动端像素适配方案
An article will introduce you to HTML tables and their main attributes
What are the highlights of Huawei mate 40 series with HMS?
STM32F030K6T6兼容替换灵动MM32F031K6T6
Epu360: all the H5 templates you want are here, e-book, big turntable, red envelope rain, questionnaire survey
image operating system windows cannot be used on this platform
Zero basis to build a web search engine of its own
How to make characters move
随机推荐
Road to simple HTML + JS to achieve the most simple game Tetris
Those who have worked in China for six years and a million annual salary want to share these four points with you
C and C / C + + mixed programming series 5 - GC collaboration of memory management
An article takes you to understand CSS3 picture border
Bitcoin once exceeded 14000 US dollars and is about to face the test of the US election
Novice guidance and event management system in game development
行为型模式之备忘录模式
Git rebase is in trouble. What to do? Waiting line
The role of theme music in games
迅为iMX6开发板-设备树内核-menuconfig的使用
How about small and medium-sized enterprises choose shared office?
vue3 新特性
DC-1 target
2020-08-19:TCP是通过什么机制保障可靠性的?
An article takes you to understand CSS pagination examples
Small program introduction to proficient (2): understand the four important files of small program development
git远程库回退指定版本
2020-08-30:裸写算法:二叉树两个节点的最近公共祖先。
Using an example to understand the underlying processing mechanism of JS function
An article takes you to understand CSS gradient knowledge