【lc刷题】59 螺旋矩阵 II_Day20(69/300)

69/300

59. 螺旋矩阵 II
    给定一个正整数 n，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。
     
    示例:
     
    输入: 3
    输出:
    [
    [ 1, 2, 3 ],
    [ 8, 9, 4 ],
    [ 7, 6, 5 ]
    ]

思路：把空matrix建好了，然后一步步走，一步步填充值。
当走到"把角儿"的时候，右拐。

如何确定走到"把角儿"？ 譬如3*3的矩阵第一行，从[0,0]走到[0,2]，继续走[0,3]肯定就报错了，这时候用[0%3,3%3]回到[0,0]，发现已经被填充，遂拐弯。

而从[0,0]走到[0,2]的过程中，走到[0,1]取模[0%3,1%3]=[0,1]还没被填充，遂填充，继续走，[0,2]取模[0%3,2%3] = [0,2]，还没被填充，遂填充，继续走…

同理，3*3的矩阵的最后一行，从[2,2]走到[2,0]，再走就是[2,-1]，取模[2%3,-1%3]回到[2,2]，发现已经被填充，遂拐弯。这里可以复习一下python 负数取模运算。

也就是说，对于3*3的矩阵，3就是边界，取模让其保证在0，1，2三个值之中。

如果本来就不超过边界，则为本体；若超过边界，则回到过去点。

文字说不明白，一会儿画个图。

画了个丑图，配合代码食用：

3*3的矩阵，从红色的[0][0]开始看起

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        matrix = [[0]*n for _ in range(n)]
        
        i, j = 0, 0
        di, dj = 0, 1 #控制direction
        
        for x in range(1, n**2+1):
            matrix[i][j] = x
            if matrix[(i+di)%n][(j+dj)%n]:
                di, dj = dj, -di
            i += di; j += dj
            
        return matrix