LeetCode in Python 48. Rotate Image/Matrix (旋转图像/矩阵)

旋转图像/矩阵的重点是寻找旋转前后对应位置的坐标关系。

示例:

图1 旋转图像/矩阵的输入输出示意图 

代码: 

class Solution:
    def rotate(self, matrix):
        n = len(matrix)
        for i in range(n // 2):
            for j in range(i, n - 1 - i):
                topleft = matrix[i][j]
                matrix[i][j] = matrix[n - 1 - j][i]
                matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j]
                matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i]
                matrix[j][n - 1 - i] = topleft

解释:

1)外层循环控制需要转的大圈圈数,内层循环控制每一圈需要转的小圈圈数,大小圈数的解释见图2,例如n=4,需要循环n // 2 = 2大圈,其中黄色循环箭头为第一大圈,绿色循环箭头为第二大圈。对于第一大圈,5->11->16->15->5为一小圈,同理1->10->12->13->1、9->7->14->2->9各为一小圈。

2)对于如何确定旋转前后位置坐标的对应关系,笔者是通过先确定再确定内层的方法,例如对于第一圈,固定i=0,然后观察大圈位置变化确定对应关系,接着改变i,观察内层圈数与i的对应关系进而修改对应坐标变化,如若先固定外层大圈循环,位置坐标变化应为:

matrix[0][j] = matrix[n - 1 - j][0]
matrix[n - 1 - j][0] = matrix[n - 1 - 0][n - 1 - j]
matrix[n - 1 - 0][n - 1 - j] = matrix[j][n - 1 - 0]
matrix[j][n - 1 - 0] = topleft

接着改变圈数,进入内层大圈循环,修改坐标变化:

matrix[i][j] = matrix[n - 1 - j][i]
matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j]
matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i]
matrix[j][n - 1 - i] = topleft

3)为了使算法空间复杂度为O(1),只需将每一次循环的左上角元素保存下来,接着采用逆向循环的顺序调整元素,最后将左上角元素归位即可,如此便无需重新开辟一个O(n^{2}) 空间来保存原始矩阵。

另外附上另一种实现方式:

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        l, r = 0, len(matrix) - 1
        while l < r:
            for i in range(r - l):
                top, bot = l, r
                topleft = matrix[top][l + i]
                matrix[top][l + i] = matrix[bot - i][l]
                matrix[bot - i][l] = matrix[bot][r - i]
                matrix[bot][r - i] = matrix[top + i][r]
                matrix[top + i][r] = topleft
            l += 1
            r -= 1

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/576059.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

ArcGIS小技巧——由图片创建点符号

一张合格的专题地图&#xff0c;除了内容的准确性和丰富性以外&#xff0c;美观性也是必不可少的。而Arcgis符号库中的符号非常有限&#xff0c;有时并不能很好的展现出地图要素的特点。因此&#xff0c;学会自定义符号就显得尤其重要了。今天&#xff0c;小编将结合实例&#…

AI大模型探索之路-训练篇4:大语言模型训练数据集概览

文章目录 前言一、常用的预训练数据集1、网页2、书籍3、维基百科4、代码5、混合型数据集 二、常用微调数据集1、指令微调数据集1.1 自然语言处理任务数据集1.2 日常对话数据集1.3 合成数据集 2、人类对齐数据集 前言 在人工智能领域&#xff0c;构建强大的AI系统的关键步骤之一…

synchronized 之谜

序言 本文给大家介绍一下 synchronized 关键字的部分原理。 一、内存中的 Java 对象 class A {private String attr; }先引入一个问题&#xff1a;上面类 A 有一个属性 attr。当类 A 实例化之后的对象在内存中是如何表示的呢&#xff1f; 在内存中&#xff0c;Java 对象由三…

Prompt Engineering,提示工程

什么是提示工程&#xff1f; 提示工程也叫【指令工程】。 Prompt发送给大模型的指令。比如[讲个笑话]、[用Python编个贪吃蛇游戏]、[给男/女朋友写情书]等看起来简单&#xff0c;但上手简单精通难 [Propmpt]是AGI时代的[编程语言][Propmpt]是AGI时代的[软件工程][提示工程]是…

Docker与Linux容器:“探索容器化技术的奥秘”

目录 一、Docker概述 二、容器技术的起源&#xff1a; 三、Linux容器 四、Docker的出现 五、Docker容器特点&#xff1a; 六、Docker三大概念&#xff1a; 容器&#xff1a; 镜像&#xff1a; 仓库&#xff1a; 七、Docker容器常用命令 一、Docker概述 在云原生时代&…

漫谈车辆诊断之DTC的状态位

搞车辆诊断测试的&#xff0c;离不开对DTC的状态位的测试 DTC的状态位是8个bit&#xff0c;每个bit代表不同的意思&#xff0c;每个bit置1或者置0都要满足一定的条件 初学者&#xff0c;很容易被这个搞得头很大 今天我们就来详细拆解一下&#xff0c;扫除你心中的疑惑 我们以…

8个拿来即用的Python自动化脚本!

每天你都可能会执行许多重复的任务&#xff0c;例如阅读新闻、发邮件、查看天气、清理文件夹等等&#xff0c;使用自动化脚本&#xff0c;就无需手动一次又一次地完成这些任务&#xff0c;非常方便。而在某种程度上&#xff0c;Python 就是自动化的代名词。 今天分享 8 个非常…

发布自己的Docker镜像到DockerHub

学会了Dockerfile生成Docker image 之后&#xff0c;如何上传自己的镜像到 DockerHub呢&#xff1f;下面我以自己制作的 bs-cqhttp 镜像为例&#xff0c;演示一下如何将自己的镜像发布到 Docker 仓库。 1 生成自己的 Docker 镜像 1.1 实例镜像用到的文件 图1 实例镜像制作用到…

stm32f103zet6_ADC_中断_2

1基本配置请查看 ADC_1 1stm32cubeMX配置 与ADC-1 区别在于配置了NVIC 2代码设置 回调函数 void HAL_ADC_ConvCpltCallback(ADC_HandleTypeDef* hadc) 这个回调函数在ADC正常转换完成后被调用。当你启动一个ADC转换&#xff08;使用HAL_ADC_Start_IT()或类似函数&#x…

【数据结构(邓俊辉)学习笔记】绪论04——算法分析

文章目录 0. 前言1. 算法分析2.级数2.1基本形式2.2 收敛级数 3.循环 vs 级数4.示例 0. 前言 通过以基本计算模型作为参照&#xff0c;并且以大O记号的形式在上面添加适当刻度&#xff0c;已经建立一套对DSA进行分析的完整工具和体系。不清楚的可以看看复杂度度量 、复杂度分析…

git 命令怎么回退到指定的某个提交 commit hash 并推送远程分支?

问题 如下图&#xff0c;我要回退到 【002】Babel 的编译流程 这一次提交 解决 1、先执行下面命令&#xff0c;输出日志&#xff0c;主要就是拿到提交 commit 的 hash&#xff0c;上图红框即可 git log或者 vscode 里面直接右击&#xff0c;copy sha 2、执行下面命令回退 g…

【Linux】如何进行用户之间的切换——指令su

&#x1f490; &#x1f338; &#x1f337; &#x1f340; &#x1f339; &#x1f33b; &#x1f33a; &#x1f341; &#x1f343; &#x1f342; &#x1f33f; &#x1f344;&#x1f35d; &#x1f35b; &#x1f364; &#x1f4c3;个人主页 &#xff1a;阿然成长日记 …

【Linux系统编程】基础指令(二)

&#x1f49e;&#x1f49e; 前言 hello hello~ &#xff0c;这里是大耳朵土土垚~&#x1f496;&#x1f496; &#xff0c;欢迎大家点赞&#x1f973;&#x1f973;关注&#x1f4a5;&#x1f4a5;收藏&#x1f339;&#x1f339;&#x1f339; &#x1f4a5;个人主页&#x…

【OceanBase诊断调优】——hpet(高精度时钟源)引起的CPU高问题排查

最近总结一些诊断OCeanBase的一些经验&#xff0c;出一个【OceanBase诊断调优】专题出来&#xff0c;也欢迎大家贡献自己的诊断OceanBase的方法。 1. 前言 昨天在问答区帮忙排查一个用户CPU高的问题&#xff0c;帖子链接&#xff1a;《刚刚新安装的OceanBase集群&#xff0c;…

代码随想录算法训练营第三十六天| 435.无重叠区间、763.划分字母区间、56.合并区间

系列文章目录 目录 系列文章目录435. 无重叠区间贪心算法按左边界排序&#xff08;与【452. 用最少数量的箭引爆气球】思路差不多&#xff09; 763.划分字母区间贪心算法①将字符串映射到哈希数组&#xff0c;用二维数组记录每个字母存在的区间&#xff0c; 转化为重叠区间问题…

手搓单链表(无哨兵位)(C语言)

目录 SLT.h SLT.c SLTtest.c 测试示例 单链表优劣分析 SLT.h #pragma once#include <stdio.h> #include <assert.h> #include <stdlib.h>typedef int SLTDataType;typedef struct SListNode {SLTDataType data;struct SListNode* next; }SLTNode;//打印…

数据治理和数据管理 傻傻分不清楚?

互联网时代&#xff0c;数据&#xff0c;这一无形资产&#xff0c;已成为现代企业的核心竞争力。如何高效地管理和利用数据&#xff0c;成为企业关注的焦点。在这个过程中&#xff0c;数据治理&#xff08;Data Governance&#xff09;和数据管理&#xff08;Data Management&a…

1分钟掌握 Python 函数参数

任何编程语言函数都是非常重要的一部分&#xff0c;而在进行函数调用时&#xff0c;了解函数的参数传递方式是非常有必要的。Python中支持哪些传参方式呢&#xff1f; Python中的传参方式是比较灵活的&#xff0c;主要包括以下六种&#xff1a; 按照位置传参按照关键字传参默…

【算法基础实验】图论-构建无向图

构建无向图 前提 JAVA实验环境 理论 无向图的数据结构为邻接表数组&#xff0c;每个数组中保存一个Bag抽象数据类型&#xff08;Bag类型需要专门讲解&#xff09; 实验数据 我们的实验数据是13个节点和13条边组成的无向图&#xff0c;由一个txt文件来保存&#xff0c;本…

网贷大数据黑名单要多久才能变正常?

网贷大数据黑名单是指个人在网贷平台申请贷款时&#xff0c;因为信用记录较差而被列入黑名单&#xff0c;无法获得贷款或者贷款额度受到限制的情况。网贷大数据黑名单的具体时间因个人信用状况、所属平台政策以及银行审核标准不同而异&#xff0c;一般来说&#xff0c;需要一定…