Loading [MathJax]/jax/output/CommonHTML/config.js
前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >2020-09-03:裸写算法:回形矩阵遍历。

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

原创
作者头像
福大大架构师每日一题
修改于 2020-09-04 02:05:22
修改于 2020-09-04 02:05:22
54800
代码可运行
举报
运行总次数:0
代码可运行

福哥答案2020-09-03:

方法一:模拟,位图方式。

跟 方法二 一样,区别是辅助矩阵visited用位图节约空间。

方法二:模拟。

可以模拟螺旋矩阵的路径。初始位置是矩阵的左上角,初始方向是向右,当路径超出界限或者进入之前访问过的位置时,则顺时针旋转,进入下一个方向。

判断路径是否进入之前访问过的位置需要使用一个与输入矩阵大小相同的辅助矩阵visited,其中的每个元素表示该位置是否被访问过。当一个元素被访问时,将 visited 中的对应位置的元素设为已访问。

如何判断路径是否结束?由于矩阵中的每个元素都被访问一次,因此路径的长度即为矩阵中的元素数量,当路径的长度达到矩阵中的元素数量时即为完整路径,将该路径返回。

复杂度分析

时间复杂度:O(mn),其中 m 和 n 分别是输入矩阵的行数和列数。矩阵中的每个元素都要被访问一次。

空间复杂度:O(mn)。需要创建一个大小为 m×n 的矩阵 visited 记录每个位置是否被访问过。

方法三:按层模拟

可以将矩阵看成若干层,首先输出最外层的元素,其次输出次外层的元素,直到输出最内层的元素。

定义矩阵的第 k 层是到最近边界距离为 k 的所有顶点。例如,下图矩阵最外层元素都是第 1 层,次外层元素都是第 2 层,剩下的元素都是第 3 层。

复杂度分析

时间复杂度:O(mn),其中 m 和 n 分别是输入矩阵的行数和列数。矩阵中的每个元素都要被访问一次。

空间复杂度:O(1)。除了输出数组以外,空间复杂度是常数。

代码用golang编写,如下:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
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))
    }
}

敲 go test -v -test.run TestSpiralOrder 命令,结果如下:

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
《LeetCode热题100》---<6.①矩阵四道(二维数组)>
用户11288958
2024/09/24
1100
《LeetCode热题100》---<6.①矩阵四道(二维数组)>
顺时针打印矩阵
可以模拟打印矩阵的路径。初始位置是矩阵的左上角,初始方向是向右,当路径超出界限或者进入之前访问过的位置时,则顺时针旋转,进入下一个方向。判断路径是否进入之前访问过的位置需要使用一个与输入矩阵大小相同的辅助矩阵 visited,其中的每个元素表示该位置是否被访问过。当一个元素被访问时,将 visited 中的对应位置的元素设为已访问。
零式的天空
2022/03/28
3400
模拟法螺旋遍历矩阵:54.螺旋矩阵(Kotlin)
给你一个 m 行 n 列的矩阵 matrix ,请按照 顺时针螺旋顺序 ,返回矩阵中的所有元素。
一个会写诗的程序员
2021/04/16
5400
模拟法螺旋遍历矩阵:54.螺旋矩阵(Kotlin)
(Leetcode 2021 刷题计划) 54. 螺旋矩阵
给你一个 m 行 n 列的矩阵 matrix ,请按照 顺时针螺旋顺序 ,返回矩阵中的所有元素。
windism
2021/03/16
3250
LeetCode-面试题29-顺时针打印矩阵
绘制螺旋轨迹路径,我们发现当路径超出界限或者进入之前访问过的单元格时,会顺时针旋转方向。
benym
2022/07/14
3260
LeetCode-54-螺旋矩阵
给定一个包含 m x n 个元素的矩阵(m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素。
benym
2022/07/14
3680
力扣(LeetCode)刷题,简单+中等题(第33期)
力扣(LeetCode)定期刷题,每期10道题,业务繁重的同志可以看看我分享的思路,不是最高效解决方案,只求互相提升。
不脱发的程序猿
2021/05/08
2700
力扣(LeetCode)刷题,简单+中等题(第33期)
剑指offer - 顺时针打印矩阵 - JavaScript
题目描述:输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字,例如,如果输入如下 4 X 4 矩阵: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字 1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
心谭博客
2020/04/21
5780
(Leetcode 2021 刷题计划) 59. 螺旋矩阵 II
给你一个正整数 n ,生成一个包含 1 到 n^2 所有元素,且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
windism
2021/03/16
2230
阿里菜鸟网络一面最新笔试题
大家好,我是来自于华为的程序员小熊。最近熊哥的一位朋友,参加阿里菜鸟网络的面试,一轮面完后,面试官要求考察代码,于是昨天要求朋友参加菜鸟的机考。
程序员小熊
2021/10/20
1.3K0
2020-08-30:裸写算法:二叉树两个节点的最近公共祖先。
时间复杂度 O(N) : 其中 N 为二叉树节点数;最差情况下,需要递归遍历树的所有节点。
福大大架构师每日一题
2020/08/30
4280
2020-08-30:裸写算法:二叉树两个节点的最近公共祖先。
搞定大厂算法面试之leetcode精讲24.其他类型题
搞定大厂算法面试之leetcode精讲24.其他类型题 视频讲解(高效学习):点击学习 目录: 1.开篇介绍 2.时间空间复杂度 3.动态规划 4.贪心 5.二分查找 6.深度优先&广度优先 7.双指针 8.滑动窗口 9.位运算 10.递归&分治 11剪枝&回溯 12.堆 13.单调栈 14.排序算法 15.链表 16.set&map 17.栈 18.队列 19.数组 20.字符串 21.树 22.字典树 23.并查集 24.其他类型题 65. 有效数字 (hard) 图是网络结构的抽象模型,是一组由边连接
全栈潇晨
2021/12/07
4520
Array - 54. Spiral Matrix
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
ppxai
2020/09/23
2950
文心一言 VS 讯飞星火 VS chatgpt (306)-- 算法导论22.2 4题
四、如果将输入的图用邻接矩阵来表示,并修改算法来应对此种形式的输入,请问BFS的运行时间将是多少?如果要写代码,请用go语言。
福大大架构师每日一题
2024/08/16
1000
文心一言 VS 讯飞星火 VS chatgpt (306)-- 算法导论22.2 4题
数组矩阵杂题
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
王脸小
2019/10/30
7180
重中之重的二分查找
There are two sorted arrays nums1 and nums2 of size m and n respectively.
王脸小
2020/07/28
4970
一起刷 leetcode 之螺旋矩阵(头条和美团真题)
给定一个包含 m*n 个元素的矩阵(m 行,n 列),请按顺时针螺旋顺序,返回矩阵中所有元素
每天晒白牙
2020/08/21
4200
一起刷 leetcode 之螺旋矩阵(头条和美团真题)
LeetCode 59. 螺旋矩阵 II && LeetCode 54. 螺旋矩阵
给定一个正整数 n,生成一个包含 1 到 n2 所有元素,且元素按顺时针顺序螺旋排列的正方形矩阵。
Michael阿明
2021/02/20
3360
LeetCode 59. 螺旋矩阵 II && LeetCode 54. 螺旋矩阵
【Day19】LeetCode算法刷题(附带解题思路、代码注释详细) 【777. 在LR字符串中交换相邻字符】 【54. 螺旋矩阵】
解题思路: 为了确定start字符串是否可以通过交换相邻字符获得end字符串,我们可以同时遍历两个字符串,当遇到可以确定两者不能通过交换字符而相等的情况时,返回false即可,完全遍历完说明符合条件,返回true;
.29.
2022/11/15
4940
【Day19】LeetCode算法刷题(附带解题思路、代码注释详细) 【777. 在LR字符串中交换相邻字符】 【54. 螺旋矩阵】
2020-08-26:裸写算法:树的非递归先序遍历。
从根节点开始,每次迭代弹出当前栈顶元素,并将其孩子节点压入栈中,先压右孩子再压左孩子。
福大大架构师每日一题
2020/08/26
4780
2020-08-26:裸写算法:树的非递归先序遍历。
推荐阅读
相关推荐
《LeetCode热题100》---<6.①矩阵四道(二维数组)>
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档