旋转图像
leetcode第48题(中等)
原链接:https://leetcode-cn.com/problems/rotate-image/
问题描述
给定一个 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]]
解法1(我比较容易想到的)
顺时针旋转后的数组,其实就是原数组从左下角开始从下到上,从左到右遍历的结果。第一种解法要用到一个临时数组拷贝原数组,然后从左下角开始从下到上,从左到右遍历临时数组,将值赋给原数组。显然这种方式,要消耗更多的空间。
代码
class Solution {
public void rotate(int[][] matrix) {
int l=matrix.length;
int [][] a=new int[l][];
for(int i=0;i<l;i++){
a[i]=matrix[i].clone();
}
for(int i=0;i<l;i++){
for(int j=l-1;j>=0;j--){
matrix[i][l-j-1]=a[j][i];
}
}
}
}
解法2(别人能想到的)
这种方法是按层遍历,从内到外遍历每一层,将某层的各个位置的数据都赋值完成,在遍历下一层。这种方案不需要临时数组,直接可以在原数组上操作。
代码
class Solution {
public void rotate(int[][] matrix) {
int s = 0, n = matrix.length;
while (s < (n >> 1)) {
int e = n - s - 1;
for (int i = s; i < e; ++i) {
int t = matrix[i][e];
matrix[i][e] = matrix[s][i];
matrix[s][i] = matrix[n - i - 1][s];
matrix[n - i - 1][s] = matrix[e][n - i - 1];
matrix[e][n - i - 1] = t;
}
++s;
}
}
}
猜你喜欢
blog
二叉树的左旋和右旋
数据结构与算法
4734
在关于树的多种算法中都用到了树的旋转来使树保持相对平衡,比如avl树,红黑树等...1.树的左旋(pivot为旋转中心点)2.来个动图3.代码演示:/** *左旋 *p为旋转的中心点
blog
avl树的旋转
数据结构与算法
4064
avl树:AVL树本质上是一颗二叉查找树1.avl树的性质左子树和右子树的高度之差的绝对值不超过1树中的每个左子树和右子树都是AVL树每个节点都有一个平衡因子(balancefactor--bf),任一节点的平衡因子是-1,0,1之一2.avl树的操作AVL树的操作基本和二叉查找树一样,这里我们关注的是两个变化很大的操作:插入和删除!AVL树不仅是一颗二叉查找树,它还有其他的性质。如果我们按照一般
blog
java base64转图片工具
工具
1366
工具类packagecom.dzqc.yx.util;importjava.io.FileInputStream;importjava.io.FileOutputStream;importjava.io.IOException;importjava.io.InputStream;importjava.io.OutputStream;importsun.misc.BASE64Decoder;impo
blog
Aspose实现word转图片、pdf
其他
687
式:Word,Excel,PowerPoint,Project,等office文档以及PDF文档。除了强大的文件操纵组件之外,Aspose.Total还提供了用于制图、写电子邮件、拼写检查、创建条形码、
ofc
手撕红黑树(1)-预备知识
weblog
3130
本篇文章为红黑树的预备知识,暂且不涉及节点颜色。
二叉树左旋
左旋的过程是将x的右子树绕x逆时针旋转,使得x的右子树成为x的父节点,同时修改相关节点的引用。旋转之后,二叉查找树的属性仍然满足
ofc
像素、CMOS与画质的关系
official
1101
《摄影艺术》
50x变焦、超强稳定……今年手机摄影几乎成了各大厂商的必争之地。可问题是,似乎总有一个声音在说:我们家的手机像素多高多高~所以它的拍照就有多好多好……
18年12月,华为首发
blog
Docker的常用命令总结
算法基础
788
关系图基本命令`uname-r`:查看内核`systemctlstartdocker`:启动docker镜像`dockerversion`:查看docker版本`dockerinfo`:查看
算法基础
757
LocalDateTime转Date/***LocalDateTime转Date*@paramlocalDateTime*@return
目录
没有一个冬天不可逾越,没有一个春天不会来临。最慢的步伐不是跬步,而是徘徊,最快的脚步不是冲刺,而是坚持。