代码随想录算法训练营第二天 | 59.螺旋矩阵

leetcode 59.螺旋矩阵

题目

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

解题思路

构建一个n行n列的二维数组
计算转几圈（注意n为奇数时，转圈结束后会剩余一个中心点）
填充每圈的数值 --最外层循环
每圈按四条边进行赋值，从左到右、从上到下、从右到左、从下到上 --在外侧循环内套四个循环，一条边用一个循环
关键点：所有循环的边界点 统一使用 左闭右开

实现代码

from typing import List

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        # 构建一个n行n列的二维数组
        nums = [[0] * n for _ in range(n)]

        # 定义矩阵的起始点  --起始位置每一圈都会变化，所以要用变量定义起始位置
        startx, starty = 0, 0
        # 定义循环次数
        loop = n // 2
        # 如果n是奇数，循环后会剩余一个中心点  
        # 比如n=3,转一圈后剩余中心点nums[1,1]; n=5 中心点nums[2,2]
        # 当n是奇数时，转loop圈后剩余中心点nums[mid, mid]要单独赋值
        mid = n // 2
        if n %2 == 1:
            nums[mid][mid] = n ** 2
        
        # 每循环一圈，起始点就会偏移，偏移量从1开始 
        # 不转圈和转1圈时，起始点都不偏移，转2圈时起始点从[0,0]偏移为[1,1]
        '''
        n = 1, loop = 0, startx, starty = 0,0
        n = 2, loop = 1, startx, starty = 0,0
        n = 3, loop = 1, startx, starty = 0,0
        n = 4, loop = 2, 第一圈 startx, starty = 0,0 第二圈 startx, starty = 1,1  
        '''
        value = 1 
        for offset in range(1, loop + 1):   # 起始点的偏移量从1开始     
            '''
            假设n = 4, loop = 2, for offset in range(1,3) --offset的值为1,2
            for i in range(0,3)     i=0,1,2 
            循环第一圈            
            从左到右，左闭右开
            startx, starty = 0, 0
            value = 1
            i = 0, nums[0][0] = 1 
            value = 2
            i = 1, nums[0][1] = 2
            value = 3
            i = 2, nums[0][2] = 3
            
            从上到下
            从右到左
            从下到上

            循环第二圈
            startx, starty = 1, 1
            ......

            '''
            for i in range(starty, n - offset): # 从左到右   nums[0][0]、nums[0][1]、nums[0][2]  
                nums[startx][i] = value
                value += 1
            for i in range(startx, n - offset):   # 从上到下  nums[0][3]、nums[1][3]、nums[2][3]
                nums[i][n - offset] = value
                value += 1
            for i in range(n - offset, starty, -1):   # 从右到左  nums[3][3]、nums[3][2]、nums[3][1]
                nums[n - offset][i] = value
                value += 1
            for i in range(n - offset, startx, -1):   # 从下到上  nums[3][0]、nums[2][0]、nums[1][0]
                nums[i][startx] = value
                value += 1
            startx += 1
            starty += 1
        
        return nums
        
test = Solution()
print(test.generateMatrix(4))  # [[1, 2, 3, 4], [12, 13, 14, 5], [11, 16, 15, 6], [10, 9, 8, 7]]

本题涉及的python基础知识

# 1、构造二维矩阵  使用列生成表达式 list = [表达式 for 变量 in 范围 if 条件]
n = 3
arr = [[0] * n for _ in range(n)]
# [0] * n 表示数组重复n次并依次连接形成一个新数组
# for _ in range(n) 等效于for i in range(n)  将循环运行n次  _在后面不会用到，是个占位符
print(arr)  # [[0, 0, 0], [0, 0, 0], [0, 0, 0]]

# 创建一个3行4列数组
nums = [[0] * 4 for _ in range(3)] 
# 给指定行和列给单个元素赋值  给第一行的4个列分别赋值
nums[0][0] = 1
nums[0][1] = 2
nums[0][2] = 3
nums[0][3] = 4
print(nums) # [[1, 2, 3, 4], [0, 0, 0, 0], [0, 0, 0, 0]]

# 整行赋值
nums[0] = [1,2,3,4]
nums[1] = [5,6,7,8]
nums[2] = [9,10,11]
print(nums)

# 2、倒序取值
for i in range(4, 0, -1):
    print(i)    # 4 3 2 1