LeetCode(48):旋转图像

Stella981
• 阅读 599

Medium!

题目描述:

给定一个 n × n 的二维矩阵表示一个图像。

将图像顺时针旋转 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]
]

解题思路:

在计算机图像处理里,旋转图片是很常见的,由于图片的本质是二维数组,所以也就变成了对数组的操作处理,翻转的本质就是某个位置上数移动到另一个位置上,比如用一个简单的例子来分析:

1  2  3       7  4  1 

4  5  6  -->   8  5  2  

7  8  9       9  6  3

对于90度的翻转有很多方法,一步或多步都可以解,我们先来看一种直接的方法,对于当前位置,计算旋转后的新位置,然后再计算下一个新位置,第四个位置又变成当前位置了,所以这个方法每次循环换四个数字,如下所示:

1  2  3                 7  2  1                  7  4  1

4  5  6      -->      4  5  6   -->    8  5  2  

7  8  9                 9  8  3      9  6  3

C++解法一:

 1 class Solution {
 2 public:
 3     void rotate(vector<vector<int> > &matrix) {
 4         int n = matrix.size();
 5         for (int i = 0; i < n / 2; ++i) {
 6             for (int j = i; j < n - 1 - i; ++j) {
 7                 int tmp = matrix[i][j];
 8                 matrix[i][j] = matrix[n - 1 - j][i];
 9                 matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];
10                 matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];
11                 matrix[j][n - 1 - i] = tmp;
12             }
13         }
14     }
15 };

还有一种解法,首先以从对角线为轴翻转,然后再以x轴中线上下翻转即可得到结果,如下图所示(其中蓝色数字表示翻转轴):

1  2  3       9  6  3       7  4  1

4  5  6  -->   8  5  2   -->     8  5  2  

7  8  9       7  4  1       9  6  3

C++解法二:

 1 class Solution {
 2 public:
 3     void rotate(vector<vector<int> > &matrix) {
 4         int n = matrix.size();
 5         for (int i = 0; i < n - 1; ++i) {
 6             for (int j = 0; j < n - i; ++j) {
 7                 swap(matrix[i][j], matrix[n - 1- j][n - 1 - i]);
 8             }
 9         }
10         for (int i = 0; i < n / 2; ++i) {
11             for (int j = 0; j < n; ++j) {
12                 swap(matrix[i][j], matrix[n - 1 - i][j]);
13             }
14         }
15     }
16 };

最后再来看一种方法,这种方法首先对原数组取其转置矩阵,然后把每行的数字翻转可得到结果,如下所示(其中蓝色数字表示翻转轴):

1  2  3       1  4  7       7  4  1

4  5  6  -->   2  5  8   -->     8  5  2  

7  8  9       3  6  9          9  6  3

C++解法三:

 1 class Solution {
 2 public:
 3     void rotate(vector<vector<int> > &matrix) {
 4         int n = matrix.size();
 5         for (int i = 0; i < n; ++i) {
 6             for (int j = i + 1; j < n; ++j) {
 7                 swap(matrix[i][j], matrix[j][i]);
 8             }
 9             reverse(matrix[i].begin(), matrix[i].end());
10         }
11     }
12 };
点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
Wesley13 Wesley13
3年前
java将前端的json数组字符串转换为列表
记录下在前端通过ajax提交了一个json数组的字符串,在后端如何转换为列表。前端数据转化与请求varcontracts{id:'1',name:'yanggb合同1'},{id:'2',name:'yanggb合同2'},{id:'3',name:'yang
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
待兔 待兔
5个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Jacquelyn38 Jacquelyn38
3年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
Stella981 Stella981
3年前
Opencv中Mat矩阵相乘——点乘、dot、mul运算详解
Opencv中Mat矩阵相乘——点乘、dot、mul运算详解2016年09月02日00:00:36 \牧野(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fme.csdn.net%2Fdcrmg) 阅读数:59593
Wesley13 Wesley13
3年前
00:Java简单了解
浅谈Java之概述Java是SUN(StanfordUniversityNetwork),斯坦福大学网络公司)1995年推出的一门高级编程语言。Java是一种面向Internet的编程语言。随着Java技术在web方面的不断成熟,已经成为Web应用程序的首选开发语言。Java是简单易学,完全面向对象,安全可靠,与平台无关的编程语言。
Stella981 Stella981
3年前
Google地球出现“无法连接到登录服务器(错误代码:c00a0194)”解决方法
Google地球出现“无法连接到登录服务器(错误代码:c00a0194)”解决方法参考文章:(1)Google地球出现“无法连接到登录服务器(错误代码:c00a0194)”解决方法(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fwww.codeprj.com%2Fblo
Wesley13 Wesley13
3年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
10个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这