第94期-基础结构：矩阵 旋转图像

Python是一门需要不断实践练习的编程语言，本文档将AI大学堂学员交流群的Python每周练习进行汇总，希望各位小伙伴能够多进行实践练习，逐渐爱上这门神奇的编程语言，掌握它并在生活中能够使用它。

1 问题描述

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。 你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

示例 1:

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

示例 2:

输入: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

示例 3:

输入: matrix = [[1]]
输出: [[1]]

示例 4:

输入: matrix = [[1,2],[3,4]]
输出: [[3,1],[4,2]]

初始代码

from typing import List
class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        #在此之间填写代码

print(Solution().rotate([[1,2,3],[4,5,6],[7,8,9]]))
print(Solution().rotate([[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]))
print(Solution().rotate([[1]]))
print(Solution().rotate([[1,2],[3,4]]))

2 解题思路

• 标签：矩阵
• 思路：递归
• 先对外圈元素进行旋转
• 外圈旋转完成后，使用递归对下一圈进行旋转
• 直到旋转到0圈或1圈为止

3 解题方法

from typing import List
class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        def a(m,n):
            i,x=0,n-m-1
            if x<0:return
            while i<=x:
                matrix[m][m+i],matrix[m+i][n],matrix[n][n-i],matrix[n-i][m]=matrix[n-i][m],matrix[m][m+i],matrix[m+i][n],matrix[n][n-i]
                i+=1
            a(m+1,n-1)
        a(0,len(matrix)-1)
        return matrix


print(Solution().rotate([[1,2,3],[4,5,6],[7,8,9]]))
print(Solution().rotate([[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]))
print(Solution().rotate([[1]]))
print(Solution().rotate([[1,2],[3,4]]))

第1-3，15-18行： 题目中已经给出的信息，运行代码时要根据这些代码进行编辑
第4行： 创建函数a，其中变量m,n为索引
第5行： 定义变量左指针i，右指针x分别为列表x两端索引
第6行： 当右端索引小于0时，结束递归
第7行： 当左指针小于右指针时，执行循环
第8行： 对矩阵相关位置的元素进行旋转操作
第9行： i+=1对下一个元素旋转
第10行： 当这一圈执行完成之后，利用a函数对里面一圈进行旋转
第11-12行： 利用函数a进行操作并返回操作后的矩阵

代码运行结果为：

算法讲解

这里用到了基础算法：递归，简单讲解下这个算法：
什么是递归
程序调用自身的编程技巧称为递归
递归做为一种算法在程序设计语言中广泛应用。

递归算法一般用于解决三类问题：
(1)数据的定义是按递归定义的。（Fibonacci函数）
(2)问题解法按递归算法实现。
(3)数据的结构形式是按递归定义的。

递归函数特征
必须有一个明确的结束条件；
每次进入更深一层递归时，问题规模相比上次递归都应有所减少
相邻两次重复之间有紧密的联系，前一次要为后一次做准备（通常前一次的输出就作为后一次的输入）。
递归效率不高，递归层次过多会导致栈溢出（在计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出）

4 视频解析

高清视频讲解，请查看AI大学堂Python基础实战100例 (opens new window)
关注『讯飞AI大学堂』公众号，发送 python100 即可领取Python基础实战100例源代码