这是我的第一篇博客,先随便写写,后续会补充更多内容。
注:本文表示数组位置(index)都是从下标为0开始。
题目描述:
给定一个正整数 n,生成一个包含 1 到 n2 所有元素,且元素按顺时针顺序螺旋排列的正方形矩阵。
解法:
这道题的重点在于找到数组相应位置(index)迭代的关系,观察下面这个例子:
用 i 表示行, j 表示列, n 表示总行数(列数)
[ [ 1, 2, 3, 4 ], [ 12, 13, 14, 5 ], [ 11, 16, 15, 6 ],
[ 10, 9, 8, 7 ],
]
从第一行第一个位置(0, 0)到(0, 3),各个位置的行数一致,列数在不断增加;
当第一行被填满时,剩下的数字会从最后一列第一个位置(0,3)开始往下存放数字,直到到达最后一个位置(3, 3)。
在这个过程中,列数是不变的,行数一直在增加,直到到达位置(3, 3);接下来类似,从位置(3, 3)到位置(3, 0),
行数不变而列数在减少;最后在位置(3, 3)到位置(1, 0),列数不变而行数减少。
可以发现1-12迭代的过程和13-16迭代的过程是类似的,都是从头开始一直迭代到初始位置的下方。
[ [ 1, 2, 3, 4 ], [ 12, 5 ], [ 11, 6 ],
[ 10, 9, 8, 7 ],
]
[ [ 13, 14 ], [ 16, 15 ],
]
将1-12迭代过程中发生变化的四个临界点找出(用代数式表示):
(0, n-1), (n-1, n-1), (n-1, 0), (1, 0)
13-16迭代的临界点:
(1, n-2), (n-2, n-2), (n-2, 1), (2, 1)
容易找到下面这个关系:
h = 0;
(0, n-h-1), (n-h-1, n-h-1), (n-h-1, 0), (h+1, h)
当到达点(h+1, h)时,h++(因为要从内部开始新一轮迭代),并且i,j的递增模式应该恢复到原始状态,即i不变,j递增。
能想到这后面的代码就很容易了,只需要迭代生成n*n个数字,分别存储到相应的数组位置上就可以了。
下面给出Python实现的代码:
def generateMatrix(n): res = [[0 for i in range(n)] for i in range(n)] i, j, flag = 0, 0, 0 h = 0 for k in range(1, n*n+1): if j == n-h-1 and i == h: flag = 1 elif i == n-h-1 and j == n-h-1: flag = 2 elif i == n-h-1 and j == h: flag = 3 elif i == h+1 and j == h: h += 1 flag = 0 res[i][j] = k if flag == 0: j += 1 elif flag == 1: i += 1 elif flag == 2: j -= 1 elif flag == 3: i -= 1 return res