Leetcodeアルゴリズム——59、螺旋行列II(square matrix II)


正の整数nを与えるには、1〜n^2の要素が螺旋順に配列された方形行列を生成する必要がある.
例:
Input: 3
Output:
[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

構想
Leetcodeアルゴリズム--54、スパイラルマトリクス(spiral matrix)を参照することができ、54題は1つのマトリクスを与え、スパイラル順序のシーケンスを求めることである.本題は,スパイラル順にマトリクスを生成するシーケンスを与える.
再帰法:
1、n*nマトリクス2を初期化し、まず時計回りの順序で、最外輪に値を付与する.
最外輪の時計回りの順番は、1、一番上の行、左から右へ2、一番右の列、上から下へ3、一番下の行、右から左へ4、一番左の列、下から上へ
3、そして、再帰法を用いて、マトリクスの最中間の1周が与えられるまで、第2周、第3周などを処理する(これも再帰終了条件である).
python実装
def generateMatrix(n):
    """
    :type n: int
    :rtype: List[List[int]]
       。
    """
    board = [[0 for i in range(n)] for i in range(n)]
    
    def generate(k, nextvalue):
        '''
           k           。
        '''
        nonlocal board
        #             
        minr = k-1 #   、  
        maxr = n-k #   、  
        #       
        if minr > maxr:
            return
        if minr == maxr:
            board[minr][minr] = nextvalue
            return
        #        
        for i in range(4): #      4 
            #        
            board[minr][minr:maxr] = list(range(nextvalue, nextvalue + maxr - minr))
            nextvalue = board[minr][maxr-1] + 1
            board = [list(x) for x in zip(*board)][::-1] #      
        #         
        generate(k+1, nextvalue)
    
    generate(1, 1)
    return board

if '__main__' == __name__:
    n = 3
    print(generateMatrix(n))