内容简介:今天为大家分享一道关于话不多说,直接看题目。
今天为大家分享一道关于 螺旋矩阵 的问题。
话不多说,直接看题目。
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" 全部资源
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- 动态规划求解最长公共子序列
- Haskell – 优化微分方程求解器
- 最大子序列的求解-算法之一分析
- 八皇后问题分析和 golang 求解
- [经典算法]8皇后问题sql求解(回溯算法)
- python实现求解列表中元素的排列和组合问题
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
游戏化革命:未来商业模式的驱动力
[美]盖布·兹彻曼、[美]乔斯琳·林德 / 应皓 / 中国人民大学出版社有限公司 / 2014-8-1 / CNY 59.00
第一本植入游戏化理念、实现APP互动的游戏化商业图书 游戏化与商业的大融合、游戏化驱动未来商业革命的权威之作 作者被公认为“游戏界的天才”,具有很高的知名度 亚马逊五星级图书 本书观点新颖,游戏化正成为最热门的商业新策略 游戏化是当今最热门的商业新策略,它能帮助龙头企业创造出前所未有的客户和员工的参与度。商业游戏化策略通过利用从游戏设计、忠诚度计划和行为经济学中所汲取......一起来看看 《游戏化革命:未来商业模式的驱动力》 这本书的介绍吧!