Leetcode 59. 螺旋矩阵(Spiral Matrix II)

这是我的第一篇博客,先随便写写,后续会补充更多内容。

注:本文表示数组位置(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

 

上一篇:1105 Spiral Matrix(二刷)


下一篇:1105 Spiral Matrix (25分)