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

旋转图像-leetcode

题目描述

给定一个 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

解法一

思路:

采用辅助数组,一层一层的进行转换,我们读取最外层的一圈数据存入列表中,再将列表中的元素进行后移操作。

代码:

class Solution {public void rotate(int[][] matrix) {int count=(matrix.length+1)/2;int step=0;int n=matrix.length;//方位int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};while(step<count) {List<Integer> numList=new ArrayList<>();int total=4*(n-1);int row=step,col=step;int directionIndex = 0;//读取最外层数据for(int i=0;i<total;i++){//读取数值numList.add(matrix[row][col]);int nextRow = row + directions[directionIndex][0], nextCol = col + directions[directionIndex][1];//出现下列情况就要换方向if (nextRow < step || nextRow >=step+n || nextCol < step || nextCol >=step+n) {directionIndex = (directionIndex + 1) % 4;}row += directions[directionIndex][0];col += directions[directionIndex][1];}int cnt=0;for(int i=numList.size()-n+1;i<numList.size();i++){numList.add(cnt++,numList.get(i));numList.remove(i+1);}row=step;col=step;for(int i=0;i<total;i++){//读取数值matrix[row][col]=numList.get(i);int nextRow = row + directions[directionIndex][0], nextCol = col + directions[directionIndex][1];//出现下列情况就要换方向if (nextRow < step || nextRow >=step+n || nextCol < step || nextCol >=step+n) {directionIndex = (directionIndex + 1) % 4;}row += directions[directionIndex][0];col += directions[directionIndex][1];}step++;n=n-2;numList.clear();} }
}

解法二

思路:

来自官方解答。寻找转换的规律。对于矩阵中的第一行而言,在旋转后,它出现在倒数第一列的位置:

image-20250923210531521

并且,第一行的第 x 个元素在旋转后恰好是倒数第一列的第 x 个元素。

对于矩阵中的第二行而言,在旋转后,它出现在倒数第二列的位置:

image-20250923210549139

对于矩阵中的第三行和第四行同理。这样我们可以得到关键等式

image-20250923210636455

我们观察关键等式

它阻止了我们进行原地旋转,这是因为如果我们直接将matrix[row][col]放到原矩阵中的目标位置 matrix[col][n−row−1]

image-20250923210822904

原矩阵中的 matrix[col][n−row−1] 就被覆盖了!这并不是我们想要的结果。因此我们可以考虑用一个临时变量 temp 暂存 matrix[col][n−row−1] 的值,这样虽然 matrix[col][n−row−1] 被覆盖了,我们还是可以通过 temp 获取它原来的值:

image-20250923210904978

那么 matrix[col][n−row−1] 经过旋转操作之后会到哪个位置呢?我们还是使用方法一中的关键等式,不过这次,我们需要将

image-20250923210929626

带入关键等式,就可以得到:

image-20250923210946707

同样地,直接赋值会覆盖掉 matrix[n−row−1][n−col−1] 原来的值,因此我们还是需要使用一个临时变量进行存储,不过这次,我们可以直接使用之前的临时变量 temp:

image-20250923211019040

我们再重复一次之前的操作,matrix[n−row−1][n−col−1] 经过旋转操作的位置

image-20250923211123655

带入关键等式,就可以得到:

image-20250923211139809

写进去:

image-20250923211156246

matrix[n−col−1][row] 经过旋转操作后的位置:

image-20250923211315422

带入关键等式,就可以得到:

image-20250923211330847

我们回到了最初的起点 matrix[row][col],也就是说:

image-20250923211350291

这四项处于一个循环中,并且每一项旋转后的位置就是下一项所在的位置!因此我们可以使用一个临时变量 temp 完成这四项的原地交换:

image-20250923211410788

当我们知道了如何原地旋转矩阵之后,还有一个重要的问题在于:我们应该枚举哪些位置 (row,col) 进行上述的原地交换操作呢?由于每一次原地交换四个位置,因此

image-20250923211457928

image-20250923211508341

代码:

class Solution {public void rotate(int[][] matrix) {int n = matrix.length;for (int i = 0; i < n / 2; ++i) {for (int j = 0; j < (n + 1) / 2; ++j) {int temp = matrix[i][j];matrix[i][j] = matrix[n - j - 1][i];matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];matrix[j][n - i - 1] = temp;}}}
}

解法三

思路:

来自官方解答。采用翻转的思想,顺时针旋转等效于先水平翻转然后对角线翻转。

作为例子,先将其通过水平轴翻转得到:

image-20250923211631388

再根据主对角线翻转得到:

image-20250923211645829

就得到了答案。对于水平轴翻转而言,我们只需要枚举矩阵上半部分的元素,和下半部分的元素进行交换,即

image-20250923211709250

对于主对角线翻转而言,我们只需要枚举对角线左侧的元素,和右侧的元素进行交换,即

image-20250923211725254

将它们联立即可得到:

image-20250923211738382

和方法一、方法二中的关键等式:

image-20250923211752746

是一致的。

代码:

class Solution {public void rotate(int[][] matrix) {int n = matrix.length;// 水平翻转for (int i = 0; i < n / 2; ++i) {for (int j = 0; j < n; ++j) {int temp = matrix[i][j];matrix[i][j] = matrix[n - i - 1][j];matrix[n - i - 1][j] = temp;}}// 主对角线翻转for (int i = 0; i < n; ++i) {for (int j = 0; j < i; ++j) {int temp = matrix[i][j];matrix[i][j] = matrix[j][i];matrix[j][i] = temp;}}}
}
http://www.hskmm.com/?act=detail&tid=15053

相关文章:

  • 【ChipIntelli 系列】ASR部分——合成语言模型和多网络(多语种)切换
  • 内网环境怎么安装软件(用 yum / apt 下载离线包并搬入内网)
  • tanh函数
  • P13617 [ICPC 2024 APC] Bit Counting Sequence
  • 打一局吗(60pts 解法)
  • 软工9.23
  • 本地部署qwen-0.6b
  • 25分钟小练习
  • 第七章 手写数字识别V2
  • 常用软件下载
  • 实用指南:S 4.1深度学习--自然语言处理NLP--理论
  • PyTorch图神经网络(五)
  • java
  • Jordan块新解
  • [CSP-S 2024] 染色
  • Kerberos 安装和使用
  • 第一次个人编程任务
  • 概率期望总结
  • redis实现秒杀下单的业务逻辑
  • 关于边缘网络+数据库(1)边缘网络数据库模式及选型
  • 题解:B4357 [GESP202506 二级] 幂和数
  • 2025年9月23日 - 20243867孙堃2405
  • 2025.9.23
  • 软件工程学习日志2025.9.23
  • markdown 使用指南
  • 第6.2节 Android Agent制作<三>
  • LVS 服务器 知识
  • 07-django+DRF项目中统一json返回格式 - 详解
  • 软工第二次作业——个人项目