螺旋矩阵

螺旋矩阵

52-螺旋矩阵

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

示例 1：

输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]

Python

解一：

class Solution(object):
    def generateMatrix(self, n):
        """
        :type n: int
        :rtype: List[List[int]]
        """
        resmatrix = [[0] * n for _ in range(n)]
        i = 0
        loop = 0
        count = 1
        num = 4 * (n - 1)
        if n == 1:
            resmatrix[0][0] = 1
            return resmatrix
        while count <= n * n:
            for i in range(num):
                if i <= num / 4 - 1:
                    resmatrix[loop][loop + i] = count
                    count += 1
                elif i > num / 4 - 1 and i <= 2 * num / 4 - 1:
                    resmatrix[int(loop + (i - num/4))][int(loop + num/4)] = count
                    count += 1
                elif i > 2 * num / 4 - 1 and i <= 3 * num / 4 - 1:
                    resmatrix[int(loop + num / 4)][int(loop+num/4-(i-2*num/4))] = count
                    count += 1
                else:
                    resmatrix[int(loop + num / 4 - (i - 3 * num / 4))][loop] = count
                    count += 1
            num -= 8
            loop += 1
            if num == 0:
                resmatrix[loop][loop] = n*n
                count += 1
        return resmatrix

解二：

class Solution(object):
    def generateMatrix(self, n):
        """
        :type n: int
        :rtype: List[List[int]]
        """
        nums = [[0] * n for _ in range(n)]
        startx, starty = 0, 0              
        loop, mid = n // 2, n // 2          
        count = 1                          

        for offset in range(1, loop + 1) :  
            for i in range(starty, n - offset) : 
                nums[startx][i] = count
                count += 1
            for i in range(startx, n - offset) :  
                nums[i][n - offset] = count
                count += 1
            for i in range(n - offset, starty, -1) : 
                nums[n - offset][i] = count
                count += 1
            for i in range(n - offset, startx, -1) : 
                nums[i][starty] = count
                count += 1                
            startx += 1   
            starty += 1

        if n % 2 != 0 :
            nums[mid][mid] = count 
        return nums

笔记

1. 对于此种问题，可以设法将其分解为一个个相似的过程（例如螺旋矩阵中的每一圈），抓住这些过程有哪些要素是相似的（在螺旋矩阵每圈中，四个角的坐标的计算），哪些要素是不变的（每圈中元素之间的关系都是顺时针依次+1），再从不变的因素出发，将相似的部分与变量联系起来，最终达到分析整个过程的目的；
2. 需要特别注意一些特殊情况，例如解一中螺旋矩阵仅有一个元素时和解二中螺旋矩阵的中心（若n为奇数）；
3. 解一解二的思路是相同的，但在一些细节的处理上存在差异例如对每一圈中坐标的计算，解一中每圈起点点初始设置为（loop，loop），而解二中起点坐标则是通过startx，starty不断加1得到。