原创音乐网站源码,网站页尾信息,网站建设所需要的材料,天津市住房城乡建设部网站Python算法题集_旋转图像 题目48#xff1a;旋转图像1. 示例说明2. 题目解析- 题意分解- 优化思路- 测量工具 3. 代码展开1) 标准求解【矩阵复本】2) 改进版一【矩阵转置矩阵反转】3) 改进版二【四值旋转】 4. 最优算法 题目48#xff1a;旋转图像
本文为Python算法题集之一… Python算法题集_旋转图像 题目48旋转图像1. 示例说明2. 题目解析- 题意分解- 优化思路- 测量工具 3. 代码展开1) 标准求解【矩阵复本】2) 改进版一【矩阵转置矩阵反转】3) 改进版二【四值旋转】 4. 最优算法 题目48旋转图像
本文为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]]提示 n matrix.length matrix[i].length1 n 20-1000 matrix[i][j] 1000 2. 题目解析
- 题意分解
本题为矩阵旋转主要的要求是在空间复杂度上本题主要是图像旋转的坐标映射处理基本的解法是采用结果矩阵来处理将会是标准解法【虽然题目不允许】
- 优化思路 通常优化减少循环层次 通常优化增加分支减少计算集 通常优化采用内置算法来提升计算速度 分析题目特点分析最优解 旋转90度四个角会同时变换其他位置也是同样的情形 通过反转和旋转矩阵也可以达成旋转图像的目的 - 测量工具
本地化测试说明LeetCode网站测试运行时数据波动很大因此需要本地化测试解决这个问题CheckFuncPerf本地化函数用时和内存占用测试模块已上传到CSDN地址Python算法题集_检测函数用时和内存占用的模块本题很难超时超时测试用例自行生成代码详见【4. 最优算法】 3. 代码展开
1) 标准求解【矩阵复本】
标准代码是双重计算量居然还能超过95%网络波动影响真是大 指标优异超越95%
import CheckFuncPerf as cfpdef rotate_base(matrix):ilen len(matrix)idiv ilen // 2m1 []for iIdx in range(ilen):m1.append([0 for x in range(ilen)])m1[idiv][idiv] matrix[idiv][idiv]for id in range(ilen):for jd in range(idiv):m1[id][jd] matrix[ilen - jd - 1][id]m1[jd][ilen - id - 1] matrix[id][jd]m1[ilen - id - 1][ilen - jd - 1] matrix[jd][ilen - id - 1]m1[ilen - jd - 1][id] matrix[ilen - id - 1][ilen - jd - 1]for id in range(ilen):for jd in range(ilen):matrix[id][jd] m1[id][jd]import random,copy
matrix []
for iIdx in range(1000):matrix.append([random.randint(0, 10) for x in range(1000)])
matrixCopy copy.deepcopy(matrix)
result cfp.getTimeMemoryStr(rotate_base, matrixCopy)
print(result[msg])# 运行结果
函数 rotate_base 的运行时间为 384.08 ms内存使用量为 484.00 KB2) 改进版一【矩阵转置矩阵反转】
执行一次转置然后左右反转空间复杂度O(1)结果达成 虚假指标超越87%
import CheckFuncPerf as cfpdef rotate_ext1(matrix):ilen len(matrix)idiv ilen // 2for iIdx in range(ilen):for jIdx in range(iIdx):matrix[iIdx][jIdx], matrix[jIdx][iIdx] matrix[jIdx][iIdx], matrix[iIdx][jIdx]for iIdx in range(ilen):for jIdx in range(idiv):matrix[iIdx][jIdx], matrix[iIdx][ilen-jIdx-1] matrix[iIdx][ilen-jIdx-1], matrix[iIdx][jIdx]import random,copy
matrix []
for iIdx in range(1000):matrix.append([random.randint(0, 10) for x in range(1000)])
matrixCopy copy.deepcopy(matrix)
result cfp.getTimeMemoryStr(rotate_ext1, matrixCopy)
print(result[msg])# 运行结果
函数 rotate_ext1 的运行时间为 152.03 ms内存使用量为 0.00 KB3) 改进版二【四值旋转】
同时旋转四个值一次性算完执行计算最少代码简洁优雅 极速狂飙超越95%
import CheckFuncPerf as cfpdef rotate_ext2(matrix):m1 matrixilen, idiv len(matrix), ilen // 2for id in range(idiv):for jd in range(id, ilen-id-1):m1[id][jd], m1[jd][ilen-id-1], m1[ilen-id-1][ilen-jd-1], m1[ilen-jd-1][id] \m1[ilen-jd-1][id], m1[id][jd], m1[jd][ilen-id-1], m1[ilen-id-1][ilen-jd-1]import random,copy
matrix []
for iIdx in range(1000):matrix.append([random.randint(0, 10) for x in range(1000)])
matrixCopy copy.deepcopy(matrix)
result cfp.getTimeMemoryStr(rotate_ext2, matrixCopy)
print(result[msg])# 运行结果
函数 rotate_ext2 的运行时间为 146.02 ms内存使用量为 0.00 KB4. 最优算法
根据本地日志分析最优算法为第3种rotate_ext2
import random,copy
matrix []
for iIdx in range(1000):matrix.append([random.randint(0, 10) for x in range(1000)])
matrixCopy copy.deepcopy(matrix)# 算法本地速度实测比较
函数 rotate_base 的运行时间为 384.08 ms内存使用量为 484.00 KB
函数 rotate_ext1 的运行时间为 152.03 ms内存使用量为 0.00 KB
函数 rotate_ext2 的运行时间为 146.02 ms内存使用量为 0.00 KB一日练一日功一日不练十日空
may the odds be ever in your favor ~
