漫画:一文看懂螺旋矩阵求解

栏目: IT技术 · 发布时间: 5年前

内容简介:今天为大家分享一道关于话不多说,直接看题目。

漫画:一文看懂螺旋矩阵求解

今天为大家分享一道关于 螺旋矩阵 的问题。

话不多说,直接看题目。

01

第54题:螺旋矩阵

第54题:定一个包含 m x n 个元素的矩阵(m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素。

示例 1:

输入:

[

[ 1, 2, 3 ],

[ 4, 5, 6 ],

[ 7, 8, 9 ]

]

输出: [1,2,3,6,9,8,7,4,5]

示例 2:

输入:

[

[1, 2, 3, 4],

[5, 6, 7, 8],

[9,10,11,12]

]

输出: [1,2,3,4,8,12,11,10,9,5,6,7]

漫画:一文看懂螺旋矩阵求解

(题目有一定难度,如果没有思路,可以先打两把王者...)

02

题目分析

本题的思路,在于 模拟螺旋的移动轨迹

问题的难点,在于 想明白模拟过程中会遇到什么问题

那模拟的过程中会遇到什么样的问题? 边界处理

因为只有我们能找到边界(边界包括:1、数组的边界 2、已经访问过的元素),才可以通过“ 右,下,左,上 ”的方向来进行移动。同时,每一次 碰壁 ,就可以调整到下一个方向。

思路明确了,我们看一下整个过程。假如我们的数组为:

[

[1, 2, 3, 4],

[5, 6, 7, 8],

[9,10,11,12]

]

长成这样:

漫画:一文看懂螺旋矩阵求解

我们首先对其设置好四个边界:

up := 0
down := len(matrix) - 1
left := 0
right := len(matrix[0]) - 1

长成这样:

漫画:一文看懂螺旋矩阵求解

同时,我们定义x和y,来代表行和列。

如x=2,y=1,则 arr[2][1]=10(第3行第2列)

漫画:一文看懂螺旋矩阵求解

然后我们从第一个元素开始行军(y=left),完成第一行的遍历,直到碰壁。(y<=right)

漫画:一文看懂螺旋矩阵求解

下面关键的一步来了, 因为第一行已经走过了,我们将上界下调 (up++) ,同时转弯向下走。

漫画:一文看懂螺旋矩阵求解

直到碰到底部时(x<=down),我们将 右界左调 (right--) ,转弯向左走。

漫画:一文看懂螺旋矩阵求解

后面向左和向上,分别完成 下界上调(down--)左界右调(left++)

漫画:一文看懂螺旋矩阵求解

最后,对剩下的矩阵重复整个过程,直到上下、左右的壁与壁碰在一起 (up <= down && left <= right,这是避免碰壁的条件)

漫画:一文看懂螺旋矩阵求解

03

Go语言示例

所以这道题很简单,只要会碰壁,就可以顺利得到代码(很漂亮,不是吗?):

 1func spiralOrder(matrix [][]int) []int {
 2    var result []int
 3    if len(matrix) == 0 {
 4        return result
 5    }
 6    left, right, up, down := 0, len(matrix[0])-1, 0, len(matrix)-1
 7    var x, y int
 8    for left <= right && up <= down {
 9        for y = left; y <= right && avoid(left, right, up, down); y++ {
10            result = append(result, matrix[x][y])
11        }
12        y--
13        up++
14        for x = up; x <= down && avoid(left, right, up, down); x++ {
15            result = append(result, matrix[x][y])
16        }
17        x--
18        right--
19        for y = right; y >= left && avoid(left, right, up, down); y-- {
20            result = append(result, matrix[x][y])
21        }
22        y++
23        down--
24        for x = down; x >= up && avoid(left, right, up, down); x-- {
25            result = append(result, matrix[x][y])
26        }
27        x++
28        left++
29    }
30    return result
31}
32
33func avoid(left, right, up, down int) bool {
34    return up <= down && left <= right
35}

最后再自恋一把:

漫画:一文看懂螺旋矩阵求解

注:本系列所有教程中都不会用到复杂的语言特性,大家不需要担心没有学过相关语法。 算法思想最重要,使用各语言纯属本人爱好。 同时,所有代码均在leetcode上进行过测试运行,保证其严谨性!

每天一道图解算法,如需进群 ↓↓↓

欢迎加微信 llhaohao

温馨提示

小浩算法~

每天一起学习图解漫画算法。

一起刷题,一起成长!

~ 长按下方二维码进行关注吧~

漫画:一文看懂螺旋矩阵求解

关注领取 "GeekTime" 全部资源


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Automate This

Automate This

Christopher Steiner / Portfolio / 2013-8-9 / USD 25.95

"The rousing story of the last gasp of human agency and how today's best and brightest minds are endeavoring to put an end to it." It used to be that to diagnose an illness, interpret legal docume......一起来看看 《Automate This》 这本书的介绍吧!

SHA 加密
SHA 加密

SHA 加密工具

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具

RGB HSV 转换
RGB HSV 转换

RGB HSV 互转工具