0059._spiral_matrix_ii.md

59. Spiral Matrix II

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/spiral-matrix-ii/

内容描述

Given a positive integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

Example:

Input: 3
Output:
[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

解题方案

思路 1 - 时间复杂度: O(m * n)- 空间复杂度: O(1)******

和Spiral Matrix的思路基本一致

也许还有待挖掘trick

class Solution(object):
    def generateMatrix(self,n):
        """
        :type n: int
        :rtype: List[List[int]]
        """
        curNum = 0
        matrix = [[0 for i in range(n)] for j in range(n)]
        maxUp = maxLeft = 0 
        maxDown = maxRight = n - 1
        direction = 0                
        while True:
            if direction == 0: #go right
                for i in range(maxLeft, maxRight+1):
                    curNum += 1
                    matrix[maxUp][i] = curNum
                maxUp += 1
            elif direction == 1: # go down
                for i in range(maxUp, maxDown+1):
                    curNum += 1
                    matrix[i][maxRight] = curNum
                maxRight -= 1
            elif direction == 2: # go left
                for i in reversed(range(maxLeft, maxRight+1)):
                    curNum += 1 
                    matrix[maxDown][i] = curNum
                maxDown -= 1
            else: #go up
                for i in reversed(range(maxUp, maxDown+1)):
                    curNum += 1
                    matrix[i][maxLeft] = curNum
                maxLeft +=1
            if curNum >= n*n:
                return matrix
            direction = (direction + 1 ) % 4

class Solution:
    def generateMatrix(self, n):
        """
        :type n: int
        :rtype: List[List[int]]
        """
        res = []
        l = n * n + 1
        while l > 1:
            l, r = l - len(res), l
            res = [list(range(l, r))] + list(zip(*res[::-1]))
        return res