Leetcodeアルゴリズム——59、螺旋行列II(square matrix II)
正の整数nを与えるには、1〜n^2の要素が螺旋順に配列された方形行列を生成する必要がある.
例:
構想
Leetcodeアルゴリズム--54、スパイラルマトリクス(spiral matrix)を参照することができ、54題は1つのマトリクスを与え、スパイラル順序のシーケンスを求めることである.本題は,スパイラル順にマトリクスを生成するシーケンスを与える.
再帰法:
1、n*nマトリクス2を初期化し、まず時計回りの順序で、最外輪に値を付与する.
最外輪の時計回りの順番は、1、一番上の行、左から右へ2、一番右の列、上から下へ3、一番下の行、右から左へ4、一番左の列、下から上へ
3、そして、再帰法を用いて、マトリクスの最中間の1周が与えられるまで、第2周、第3周などを処理する(これも再帰終了条件である).
python実装
例:
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))