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

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

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

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

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

话不多说,直接看题目。

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" 全部资源


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

查看所有标签

猜你喜欢:

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

游戏化革命:未来商业模式的驱动力

游戏化革命:未来商业模式的驱动力

[美]盖布·兹彻曼、[美]乔斯琳·林德 / 应皓 / 中国人民大学出版社有限公司 / 2014-8-1 / CNY 59.00

第一本植入游戏化理念、实现APP互动的游戏化商业图书 游戏化与商业的大融合、游戏化驱动未来商业革命的权威之作 作者被公认为“游戏界的天才”,具有很高的知名度 亚马逊五星级图书 本书观点新颖,游戏化正成为最热门的商业新策略 游戏化是当今最热门的商业新策略,它能帮助龙头企业创造出前所未有的客户和员工的参与度。商业游戏化策略通过利用从游戏设计、忠诚度计划和行为经济学中所汲取......一起来看看 《游戏化革命:未来商业模式的驱动力》 这本书的介绍吧!

CSS 压缩/解压工具
CSS 压缩/解压工具

在线压缩/解压 CSS 代码

URL 编码/解码
URL 编码/解码

URL 编码/解码

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

在线 XML 格式化压缩工具