漫画:一文看懂螺旋矩阵求解
2015 年 12 月 3 日
本题的思路,在于 模拟螺旋的移动轨迹 。
问题的难点,在于 想明白模拟过程中会遇到什么问题 。
那模拟的过程中会遇到什么样的问题? 边界处理 。
因为只有我们能找到边界(边界包括: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 = 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上进行过测试运行,保证其严谨性!