极客算法

LeetCode-59. Spiral Matrix II

2020-09-27

草稿说明

三里屯Apple导购员和他的工作搭档, Respect!!!​

59. 螺旋矩阵 II

给定一个正整数 n,生成一个包含 1 到 n2 所有元素,且元素按顺时针顺序螺旋排列的正方形矩阵。

示例:

输入: 3
输出:
[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

回顾上一题

O(N^2)

之前的解法是,先把第一个填进结果。这次,我们直接遍历,但是把最后一个要记得放入数组

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:

        if len(matrix) == 0 or len(matrix[0]) == 0:
            return []
        
        n = len(matrix)
        m = len(matrix[0])
        
        x_directions = [0, 1, 0, -1]
        y_directions = [1, 0, -1, 0]
            
        bounds = [0, m - 1, n - 1, 0]
        shrink_bounds = [1, -1, -1, 1]
            
        res = []
        x = y = 0
            
        while bounds[0] <= bounds[2] and bounds[3] <= bounds[1]:
            for k in range(4):
                while bounds[0] <= x + x_directions[k] <= bounds[2] and bounds[3] <= y + y_directions[k] <= bounds[1]:
                    res.append(matrix[x][y])
                    x += x_directions[k]
                    y += y_directions[k]

                bounds[k] += shrink_bounds[k]
        
        res.append(matrix[x][y])
        
        return res

模拟法

O(N^2)

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        res = [[0 for j in range(n)] for i in range(n)]
            
        x_directions = [0, 1, 0, -1]
        y_directions = [1, 0, -1, 0]
            
        bounds = [0, n - 1, n - 1, 0]
        shrink_bounds = [1, -1, -1, 1]
            
        x = y = 0
        count = 1
            
        while bounds[0] <= bounds[2] and bounds[3] <= bounds[1]:
            for k in range(4):
                while bounds[0] <= x + x_directions[k] <= bounds[2] and bounds[3] <= y + y_directions[k] <= bounds[1]:
                    res[x][y] = count
                    x += x_directions[k]
                    y += y_directions[k]
                    count += 1
                    
                bounds[k] += shrink_bounds[k]
        
        res[x][y] = count
        
        return res

–End–

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/spiral-matrix-ii/

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


评论

内容:
其他: