当前位置: 首页 > news >正文

Python算法题集_旋转图像

 Python算法题集_旋转图像

  • 题目48:旋转图像
  • 1. 示例说明
  • 2. 题目解析
    • - 题意分解
    • - 优化思路
    • - 测量工具
  • 3. 代码展开
    • 1) 标准求解【矩阵复本】
    • 2) 改进版一【矩阵转置+矩阵反转】
    • 3) 改进版二【四值旋转】
  • 4. 最优算法

题目48:旋转图像

本文为Python算法题集之一的代码示例

1. 示例说明

  • 给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

    你必须在原地 旋转图像,这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

    示例 1:

    img

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

    示例 2:

    img

    输入: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].length
    • 1 <= n <= 20
    • -1000 <= matrix[i][j] <= 1000

2. 题目解析

- 题意分解

  1. 本题为矩阵旋转,主要的要求是在空间复杂度上
  2. 本题主要是图像旋转的坐标映射处理
  3. 基本的解法是采用结果矩阵来处理,将会是标准解法【虽然题目不允许】

- 优化思路

  1. 通常优化:减少循环层次

  2. 通常优化:增加分支,减少计算集

  3. 通常优化:采用内置算法来提升计算速度

  4. 分析题目特点,分析最优解

    1. 旋转90度,四个角会同时变换,其他位置也是同样的情形

    2. 通过反转和旋转矩阵,也可以达成旋转图像的目的


- 测量工具

  • 本地化测试说明: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 KB

2) 改进版一【矩阵转置+矩阵反转】

执行一次转置,然后左右反转,空间复杂度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 KB

3) 改进版二【四值旋转】

同时旋转四个值,一次性算完,执行计算最少,代码简洁优雅 极速狂飙,超越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 KB

4. 最优算法

根据本地日志分析,最优算法为第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 ~

相关文章:

Python算法题集_旋转图像

Python算法题集_旋转图像 题目48&#xff1a;旋转图像1. 示例说明2. 题目解析- 题意分解- 优化思路- 测量工具 3. 代码展开1) 标准求解【矩阵复本】2) 改进版一【矩阵转置矩阵反转】3) 改进版二【四值旋转】 4. 最优算法 题目48&#xff1a;旋转图像 本文为Python算法题集之一…...

[ChatGPT们】ChatGPT 如何辅助编程初探

主页&#xff1a;元存储的博客 全文 9000 字&#xff0c; 原创请勿转载。 我没有写过诗&#xff0c;但有人说我的代码像诗一样优雅 -- 雷军 图片来源&#xff1a;https://www.bilibili.com/video/BV1zL411X7oS/ 1. 引言 作为一个程序员&#xff0c;我们不仅要熟悉各种编程语…...

深入Spring MVC的工作流程

深入Spring MVC的工作流程 在Spring MVC的面试问题中&#xff0c;常常被询问到的一个问题。Spring MVC的程序中&#xff0c;HTTP请求是如何从开始到结束被处理的。为了研究这个问题&#xff0c;我们将需要深入学习一下Spring MVC框架的核心过程和工作流程。 1. 启动请求生命周…...

我的数据结构c(给自己用的)

目录 顺序表&#xff1a; 链表&#xff1a; 栈&#xff1a; 队列&#xff1a; 我想在之后的大学数据结构课上需要自己写来做题&#xff0c;但每次都自己写&#xff0c;那太麻烦了&#xff0c;所以我就将这个博客来把所有的C语言的数据结构弄上去&#xff0c; 问我为什么不…...

使用Arcgis对欧洲雷达高分辨率降水数据重投影

当前需要使用欧洲高分辨雷达降水数据&#xff0c;但是这个数据的投影问题非常头疼。实际的投影应该长这样&#xff08;https://gist.github.com/kmuehlbauer/645e42a53b30752230c08c20a9c964f9?permalink_comment_id2954366https://gist.github.com/kmuehlbauer/645e42a53b307…...

[Python] scikit-learn中数据集模块介绍和使用案例

sklearn.datasets模块介绍 在scikit-learn中&#xff0c;可以使用sklearn.datasets模块中的函数来构建数据集。这个模块提供了用于加载和生成数据集的函数。 API Reference — scikit-learn 1.4.0 documentation 以下是一些常用的sklearn.datasets模块中的函数 load_iris() …...

Qt-互斥量-临界区-QMutex-QMutexLocker-QReadWriteLock

文章目录 1.QMutex2.QMutexLocker3.QReadWriteLock 在Qt中&#xff0c;互斥量&#xff08;Mutex&#xff09;是用于同步多线程访问共享资源的一种机制。临界区&#xff08;Critical Section&#xff09;是指一段必须由单个线程执行的代码区域&#xff0c;防止多个线程同时执行这…...

《PCI Express体系结构导读》随记 —— 第II篇 第4章 PCIe总线概述(6)

接前一篇文章&#xff1a;《PCI Express体系结构导读》随记 —— 第II篇 第4章 PCIe总线概述&#xff08;5&#xff09; 4.1 PCIe总线的基础知识 与PCI总线不同&#xff0c;PCIe总线使用端到端的连接方式&#xff0c;在一条PCIe链路的两端只能各连接一个设备&#xff0c;这两个…...

uniapp 高德地图显示

1. uniapp 高德地图显示 使用前需到**高德开放平台&#xff08;https://lbs.amap.com/&#xff09;**创建应用并申请Key   登录 高德开放平台&#xff0c;进入“控制台”&#xff0c;如果没有注册账号请先根据页面提示注册账号   打开 “应用管理” -> “我的应用”页面…...

2024年最新幻兽帕鲁服务器搭建教程

玩转幻兽帕鲁服务器&#xff0c;阿里云推出新手0基础一键部署幻兽帕鲁服务器教程&#xff0c;傻瓜式一键部署&#xff0c;3分钟即可成功创建一台Palworld专属服务器&#xff0c;成本仅需26元&#xff0c;阿里云服务器网aliyunfuwuqi.com分享2024年新版基于阿里云搭建幻兽帕鲁服…...

重新配置vue项目时出现的:连接已断开问题

在新机器上配置完node.js、vue-cli&#xff0c;配置了node_modules后&#xff0c;命令行运行vue ui后&#xff0c;出现了如下报错&#xff1a; C:\Users\LEN>vue ui &#x1f680; Starting GUI... &#x1f320; Ready on http://localhost:8000 node:events:496throw e…...

四、Redis之配置文件

redis配置文件的名称 redis.conf 通过命令 find / -name redis.confvim redis.conf通过 : set nu 设置行号: set nonu 取消行号/关键字 搜索关键字: set noh 取消高亮选择4.1 Units 配置大小单位&#xff0c;开头定义了一些基本的度量单位&#xff0c;只支持 bytes&#…...

libevent源码解析--event,event_callback,event_base

1.概述 实现一个基础tcp网络库&#xff0c;以基于tcp网络库构建服务端应用&#xff0c;客户端应用为起点&#xff0c;我们的核心诉求有&#xff1a; a. tcp网络库管理工作线程。 b. tcp网络库产生服务端对象&#xff0c;通过启动接口&#xff0c;开启服务端监听。进一步&…...

C语言进阶之文件操作

一、什么是文件 磁盘上的文件是文件。 但是在程序设计中&#xff0c;我们一般谈的文件有两种&#xff1a;程序文件、数据文件&#xff08;从文件功能的角度来分类的&#xff09;。 1&#xff09;程序文件 包括源程序文件&#xff08;后缀为.c&#xff09;,目标文件&#xff…...

互联网摸鱼日报(2024-02-02)

互联网摸鱼日报(2024-02-02) 博客园新闻 马斯克&#xff1a;Neuralink已探测到神经信号 Linus新年首骂&#xff1a;和谷歌大佬大吵4天&#xff0c;“你的代码就是垃圾” 从零手搓MoE大模型&#xff0c;大神级教程来了 无人出租车深圳中心区收费载客&#xff0c;硅谷同款&am…...

2024美赛C题:网球中的动量

解析&#xff1a;https://mp.weixin.qq.com/s/TOPvJ-5pjgsvjvYXt6E9Fg 2023年温网男篮决赛&#xff0c;20岁的西班牙新星卡洛斯阿尔卡拉斯 击败了36岁的诺瓦克德约科维奇。这场失利是德约科维奇自2013年以来首次在温布尔登输球 并结束了大满贯历史上最伟大的球员之一的非凡表现…...

20.HarmonyOS App(JAVA)表格布局Layout使用方法

ability_main.xml&#xff0c;实现计算器键盘按钮 <?xml version"1.0" encoding"utf-8"?> <TableLayoutxmlns:ohos"http://schemas.huawei.com/res/ohos"ohos:height"match_parent"ohos:width"match_parent"oho…...

Android使用ScrollView导致鼠标点击事件无效

平台 测试平台: RK3288 Android8.1RK3588 Android 12 问题 首先, 这个问题的前提是, 使用的输入设备是**鼠标**, 普通的触摸屏并不会出现这个问题. 大致的流程是APP的UI布局中采用ScrollView作为根容器, 之后添加各类子控件, 在一起准备就绪后, 使用鼠标进行功能测试, 出现…...

【开源】SpringBoot框架开发大学计算机课程管理平台

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 实验课程档案模块2.2 实验资源模块2.3 学生实验模块 三、系统设计3.1 用例设计3.2 数据库设计3.2.1 实验课程档案表3.2.2 实验资源表3.2.3 学生实验表 四、系统展示五、核心代码5.1 一键生成实验5.2 提交实验5.3 批阅实…...

Mac Shift切换输入法 - shift切换中英文 - Karabiner-Elements

转载自 https://www.jianshu.com/p/677ae7d9beda...

Docker 离线安装指南

参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性&#xff0c;不同版本的Docker对内核版本有不同要求。例如&#xff0c;Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本&#xff0c;Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

python打卡day49

知识点回顾&#xff1a; 通道注意力模块复习空间注意力模块CBAM的定义 作业&#xff1a;尝试对今天的模型检查参数数目&#xff0c;并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

ESP32读取DHT11温湿度数据

芯片&#xff1a;ESP32 环境&#xff1a;Arduino 一、安装DHT11传感器库 红框的库&#xff0c;别安装错了 二、代码 注意&#xff0c;DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:

根据万维钢精英日课6的内容&#xff0c;使用AI&#xff08;2025&#xff09;可以参考以下方法&#xff1a; 四个洞见 模型已经比人聪明&#xff1a;以ChatGPT o3为代表的AI非常强大&#xff0c;能运用高级理论解释道理、引用最新学术论文&#xff0c;生成对顶尖科学家都有用的…...

【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论

路径问题的革命性重构&#xff1a;基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中&#xff08;图1&#xff09;&#xff1a; mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...

CSS | transition 和 transform的用处和区别

省流总结&#xff1a; transform用于变换/变形&#xff0c;transition是动画控制器 transform 用来对元素进行变形&#xff0c;常见的操作如下&#xff0c;它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...

华为OD最新机试真题-数组组成的最小数字-OD统一考试(B卷)

题目描述 给定一个整型数组,请从该数组中选择3个元素 组成最小数字并输出 (如果数组长度小于3,则选择数组中所有元素来组成最小数字)。 输入描述 行用半角逗号分割的字符串记录的整型数组,0<数组长度<= 100,0<整数的取值范围<= 10000。 输出描述 由3个元素组成…...

第一篇:Liunx环境下搭建PaddlePaddle 3.0基础环境(Liunx Centos8.5安装Python3.10+pip3.10)

第一篇&#xff1a;Liunx环境下搭建PaddlePaddle 3.0基础环境&#xff08;Liunx Centos8.5安装Python3.10pip3.10&#xff09; 一&#xff1a;前言二&#xff1a;安装编译依赖二&#xff1a;安装Python3.10三&#xff1a;安装PIP3.10四&#xff1a;安装Paddlepaddle基础框架4.1…...