存在二种解题思路: 一种是递归解法,一种是层层递进解法
图解递归解法
- 如图所示, 一个5*5的矩阵
- 先打印最外层的圈, 然后剩余最里层3*3的矩阵, 如图.
- 将3*3的矩阵继续打印最外层,思路与打印最外层思路一样,我们就可以考虑使用递归实现.
- 最后只剩余一个元素,也可以看成一个矩阵,不过不同大小的矩阵会出现不同形状的矩阵.共3种情况, 如下图.
- 如图所示, 共三种情况
- 一个方向的情况
- 三个方向的情况
- 四个方向的情况
代码实现思路
- 矩阵用代码表示为二维数据
- 首先遍历第一行所有的元素,即图中的从左到右箭头的数据.
- 然后遍历最右边的元素,即最后一列数据.即图中的从上到下箭头的数据.
- 再遍历最后一行元素,即图中从右到左箭头的数据
- 最后遍历最左列的元素,即图中从下到上箭头的数据.
- 将剩余的矩阵构建成一个子矩阵,即新的二维数组,然后递归传递.这是关键的一步
- 仅剩余1行1列即是递归退出条件
图解非递归解法
- 如图所示,我们可以将矩阵看作层层递进的矩阵,如俄罗斯的套娃一样.
- 第一个套娃的起点坐标,即(0,0)
- 第二个套娃的起点坐标,即(1,1)
- 第三个套娃的起点坐标,即(2,2)
代码实现思路
- 设置一个起点坐标start=0, 然后按方向遍历元素,与递归遍历一样.
- 我们发现55的矩阵, 最后一个圈坐标为(2,2), 44矩阵最后一个圈的坐标是(1,1),得出退出条件X坐标大于2倍起点坐标.Y坐标同理可得.
- for x > 2start && y > 2start, 遍历完第1层圈,再遍历第2层圈, 即start++
代码片段
//解题3思路: 每一次从最左上角打印,即坐标为(0,0),打印最外层一圈. 然后打印第二圈,即坐标:(1,1), 以次类推
//时间复杂度:O(n)
func PrintMatrixLikeSnake(matrix [][]int) []int {
if len(matrix) <= 0 {
return nil
}
rows := len(matrix)
columns := len(matrix[0])
if columns <= 0 {
return nil
}
//定义一个结果集
result := make([]int, 0)
//准备打印第一个最外层的圈,定义一个启始坐标
start := 0
//我们发现5*5的矩阵, 最后一个圈坐标为(2,2), 4*4矩阵最后一个圈的坐标是(1,1),得出退出条件X坐标大于2倍起点坐标.Y坐标同理可得.
for rows > start * 2 && columns > start * 2 {
endX := columns-1-start
endY := rows-1-start
//从左到右打印,即第一行的边
for i := start; i <= endX; i++ {
result = append(result, matrix[start][i])
}
//从最右边从上到下打印,即最右边的边
if start < endY {
for i := start+1;i <= endY; i ++ {
result = append(result, matrix[i][endX])
}
}
//从最右边从右到左打印,即最下面的边
if start < endX && start < endY {
for i := endX-1; i >= start; i -- {
result = append(result, matrix[endY][i])
}
}
//从最左边从下到上打印,即最左边的边
if start < endY - 1 {
for i := endY-1; i >= start+1; i -- {
result = append(result, matrix[i][start])
}
}
start ++
}
return result
}
总结
不管使用递归还是非递归,我们首先要找出解题的思路, 仔细观察,多画图,多演算,假设.一步一步逼进最终解.
完整代码github: 完整代码
)
有疑问加站长微信联系(非本文作者)