python5种算法模拟螺旋、分层填充、递归、迭代、分治实现螺旋矩阵ll【力扣题59】

简介: python5种算法模拟螺旋、分层填充、递归、迭代、分治实现螺旋矩阵ll【力扣题59】

作者介绍:10年大厂数据\经营分析经验,现任大厂数据部门负责人。

会一些的技术:数据分析、算法、SQL、大数据相关、python

欢迎加入社区:码上找工作

作者专栏每日更新:

LeetCode解锁1000题: 打怪升级之旅

python数据分析可视化:企业实战案例

备注说明:方便大家阅读,统一使用python,带必要注释,公众号 数据分析螺丝钉 一起打怪升级

题目描述

给你一个正整数 n,生成一个包含 1n^2 所有元素的 n x n 正方形矩阵,数组的元素按螺旋顺序依次填充。

输入格式
  • n:一个正整数,表示矩阵的大小。
输出格式
  • 返回一个 n x n 的数组,按螺旋顺序填充从 1n^2 的整数。
示例 1
输入: n = 3
输出: [[1,2,3],[8,9,4],[7,6,5]]

方法一:模拟螺旋填充

解题步骤
  1. 初始化矩阵:创建一个 n x n 的矩阵,初始填充值为 0
  2. 螺旋遍历:定义四个方向,模拟螺旋遍历的过程,按顺序填入数字。
  3. 边界条件处理:在填充过程中,需要不断检查下一个位置是否超出边界或已被填充。
完整的规范代码
def generateMatrix(n):
    """
    使用模拟螺旋遍历的方法生成螺旋矩阵
    :param n: int, 矩阵的大小
    :return: List[List[int]], 螺旋矩阵
    """
    matrix = [[0] * n for _ in range(n)]
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # right, down, left, up
    row, col, di = 0, 0, 0
    for i in range(1, n*n + 1):
        matrix[row][col] = i
        dr, dc = directions[di]
        if not (0 <= row + dr < n and 0 <= col + dc < n and matrix[row + dr][col + dc] == 0):
            di = (di + 1) % 4  # Change direction
            dr, dc = directions[di]
        row, col = row + dr, col + dc
    return matrix
# 示例调用
print(generateMatrix(3))  # 输出: [[1, 2, 3], [8, 9, 4], [7, 6, 5]]
算法分析
  • 时间复杂度:(O(n^2)),其中 n 是矩阵的维度,需要填充 n^2 个元素。
  • 空间复杂度:(O(n^2)),用于存储生成的矩阵。

方法二:分层填充法

解题步骤
  1. 定义边界:设置上下左右四个边界,控制填充范围。
  2. 外层到内层填充:按层模拟填充过程,每完成一圈缩小填充范围。
  3. 逐层填充:按照右下左上的顺序逐层填充,每填完一全圈,四个边界向内缩进。
完整的规范代码
def generateMatrix(n):
    """
    使用分层填充法生成螺旋矩阵
    :param n: int, 矩阵的大小
    :return: List[List[int]], 螺旋矩阵
    """
    matrix = [[0] * n for _ in range(n)]
    left, right, top, bottom = 0, n-1, 0, n-1
    num = 1
    while left <= right and top <= bottom:
        for i in range(left, right + 1):
            matrix[top][i] = num
            num += 1
        top += 1
        for i in range(top, bottom + 1):
            matrix[i][right] = num
            num += 1
        right -= 1
        if top <= bottom:
            for i in range(right, left - 1, -1):
                matrix[bottom][i] = num
                num += 1
            bottom -= 1
        if left <= right:
            for i in range(bottom, top - 1, -1):
                matrix[i][left] = num
                num += 1
            left += 1
    return matrix
# 示例调用
print(generateMatrix(3))  # 输出: [[1, 2, 3], [8, 9, 4], [7, 6, 5]]
算法分析
  • 时间复杂度:(O(n^2)),必须填充所有 n^2 个元素。
  • 空间复杂度:(O(n^2)),用于存储生成的矩阵。

方法三:递归填充

解题步骤
  1. 递归函数定义:定义一个递归函数用于填充每一层。
  2. 递归填充:从外层向内层递归填充,每次递归填充一圈。
  3. 终止条件:当填充完成或只剩下一行/一列时终止递归。
完整的规范代码
def generateMatrix(n):
    """
    使用递归方法生成螺旋矩阵
    :param n: int, 矩阵的大小
    :return: List[List[int]], 螺旋矩阵
    """
    matrix = [[0] * n for _ in range(n)]
    fill(matrix, 0, n, 1)
    return matrix
def fill(matrix, start, n, val):
    if n <= 0:
        return
    if n == 1:
        matrix[start][start] = val
        return
    for i in range(n - 1):
        matrix[start][start + i] = val
        val += 1
    for i in range(n - 1):
        matrix[start + i][start + n - 1] = val
        val += 1
    for i in range(n - 1):
        matrix[start + n - 1][start + n - 1 - i] = val
        val += 1
    for i in range(n - 1):
        matrix[start + n - 1 - i][start] = val
        val += 1
    fill(matrix, start + 1, n - 2, val)
# 示例调用
print(generateMatrix(3))  # 输出: [[1, 2, 3], [8, 9, 4], [7, 6, 5]]
算法分析
  • 时间复杂度:(O(n^2)),需要填充所有 n^2 个元素。
  • 空间复杂度:(O(n^2)),用于存储生成的矩阵,加上递归栈的开销(最坏情况下为 (O(n)))。

方法四:迭代展开

解题步骤
  1. 初始化变量:定义矩阵、起始点、方向等变量。
  2. 迭代填充:通过迭代的方式填充矩阵,类似于方法一但避免了方向切换的复杂判断。
  3. 边界处理:在迭代中处理矩阵边界和已填充元素的情况。
完整的规范代码
def generateMatrix(n):
    """
    使用迭代展开的方法生成螺旋矩阵
    :param n: int, 矩阵的大小
    :return: List[List[int]], 螺旋矩阵
    """
    matrix = [[0] * n for _ in range(n)]
    x, y, dx, dy = 0, 0, 0, 1
    for i in range(1, n*n+1):
        matrix[x][y] = i
        if matrix[(x+dx)%n][(y+dy)%n]:
            dx, dy = dy, -dx
        x, y = x + dx, y + dy
    return matrix
# 示例调用
print(generateMatrix(3))  # 输出: [[1, 2, 3], [8, 9, 4], [7, 6, 5]]
算法分析
  • 时间复杂度:(O(n^2)),需要填充所有 n^2 个元素。
  • 空间复杂度:(O(n^2)),用于存储生成的矩阵。

方法五:分治填充

解题步骤
  1. 定义填充函数:创建一个函数用于填充矩阵的一圈。
  2. 分治递归:递归地填充外圈后,对内层矩阵进行相同操作。
  3. 终止与初始化:当矩阵大小减小到1或0时终止递归。
完整的规范代码
def generateMatrix(n):
    """
    使用分治填充法生成螺旋矩阵
    :param n: int, 矩阵的大小
    :return: List[List[int]], 螺旋矩阵
    """
    matrix = [[0] * n for _ in range(n)]
    fill_layer(matrix, 0, n, 1)
    return matrix
def fill_layer(matrix, start, size, start_val):
    if size <= 0:
        return
    if size == 1:
        matrix[start][start] = start_val
        return
    # Fill the perimeter
    for i in range(size - 1):
        matrix[start][start+i] = start_val
        start_val += 1
    for i in range(size - 1):
        matrix[start+i][start+size-1] = start_val
        start_val += 1
    for i in range(size - 1):
        matrix[start+size-1][start+size-1-i] = start_val
        start_val += 1
    for i in range(size - 1):
        matrix[start+size-1-i][start] = start_val
        start_val += 1
    fill_layer(matrix, start+1, size-2, start_val)
# 示例调用
print(generateMatrix(3))  # 输出: [[1, 2, 3], [8, 9, 4], [7, 6, 5]]
算法分析
  • 时间复杂度:(O(n^2)),需要填充所有 n^2 个元素。
  • 空间复杂度:(O(n^2)),用于存储生成的矩阵,递归栈深度依矩阵大小而定。

不同算法的优劣势对比

特征 方法一: 模拟螺旋填充 方法二: 分层填充法 方法三: 递归填充 方法四: 迭代展开 方法五: 分治填充
时间复杂度 (O(n^2)) (O(n^2)) (O(n^2)) (O(n^2)) (O(n^2))
空间复杂度 (O(n^2)) (O(n^2)) (O(n^2)) (O(n^2)) (O(n^2))
优势 直观易理解 清晰结构化 结构简单 代码简洁 递归清晰,易于理解
劣势 稍微复杂的控制流 多次循环 递归深度问题 边界处理复杂 空间使用多,递归深度

应用示例

游戏开发

在游戏开发中,尤其是需要生成迷宫或特定图案的场景设计里,螺旋矩阵可以用于设计关卡的地图布局,例如生成螺旋迷宫地图,增加游戏的趣味性和挑战性。

通过上述方法,开发者可以选择最适合其应用场景的算法来实现高效、可靠的矩阵生成功能。

欢迎关注微信公众号 数据分析螺丝钉

相关文章
|
2月前
|
供应链 算法
【算法】——快排,分治算法合集
本文主要介绍排序中的快排思想的应用,做到一法通万法的效果
|
3月前
|
算法 Python
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果;贪心算法在每一步选择局部最优解,追求全局最优;动态规划通过保存子问题的解,避免重复计算,确保全局最优。这三种算法各具特色,适用于不同类型的问题,合理选择能显著提升编程效率。
76 2
|
4月前
|
Java 程序员 C++
【Python】链式、嵌套调用、递归、函数栈帧、参数默认值和关键字参数
【Python】链式、嵌套调用、递归、函数栈帧、参数默认值和关键字参数
47 0
【Python】链式、嵌套调用、递归、函数栈帧、参数默认值和关键字参数
|
6月前
|
算法 Python
python函数递归和生成器
python函数递归和生成器
|
6月前
|
算法 数据挖掘 Python
|
6月前
|
存储
LeetCode------递归(爬楼梯)
这篇文章通过LeetCode上的"爬楼梯"问题介绍了递归的基本概念和实现方法,包括递归公式的推导、基本递归实现、使用备忘录优化以避免重复计算,以及自底向上的迭代方法来提高效率。
LeetCode------递归(爬楼梯)
|
6月前
|
数据采集 Java Python
python 递归锁、信号量、事件、线程队列、进程池和线程池、回调函数、定时器
python 递归锁、信号量、事件、线程队列、进程池和线程池、回调函数、定时器
|
6月前
|
算法 搜索推荐
算法设计 (分治法应用实验报告)基于分治法的合并排序、快速排序、最近对问题
这篇文章是关于分治法应用的实验报告,详细介绍了如何利用分治法实现合并排序和快速排序算法,并探讨了使用分治法解决二维平面上的最近对问题的方法,包括伪代码、源代码实现及时间效率分析,并附有运行结果和小结。
|
5月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
6月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
144 2

热门文章

最新文章