初级编程通关练习题 #9 – 矩阵几字形遍历

给定一个NxN的矩阵,从左上角索引(0,0)开始遍历矩阵的数值,先后经过右上角(N-1,0),右下角(N-1,N-1),最后到左下角(N-1,0)结束遍历,要求按照这样的顺序一次遍历矩阵里所有的数值。譬如一个4×4的矩阵如下图,按照几字型来遍历,得到的数值列表为:[1,2,3,4,8,12,16,15,11,7,6,5,9,10,14,13]。

Corner Fill

输入样例:

matrix = [[1, 2, 3, 4, 5],
[6, 7, 8, 9, 10],
[11, 12, 13, 14, 15],
[16, 17, 18, 19, 20],
[21, 22, 23, 24, 25]]

输出样例:

[1, 2, 3, 4, 5, 10, 15, 20, 25, 24, 19, 14, 9, 8, 7, 6, 11, 12, 13, 18, 23, 22, 17, 16, 21]

算法思路:

  • 方法一:已经遍历的数值可以删去,来简化循环的过程。
    • 几字型矩阵遍历可以看作是两组遍历反复循环。
    • 第一组顺序遍历:索引从小往大遍历矩阵第一个子数组,加每一个子数组的最后一个数值。
    • 第二组倒序遍历:索引从大往小遍历矩阵每一个子数组最后一个数值,加矩阵第一个子数组。
  • 方法二:不需要删去已经遍历的数值。
    • 循环矩阵的每一行时,如果当前行的索引是 i,读取该行的N-i 个数值以及每一列索引为第 N – i – 1 位置的数值。
    • 如果当前行的索引是偶数,则反转上面读到的数值列表。
    • 把该列表添加到最终结果列表里面。