旋转图像

weblog 769 0 0

leetcode48题(中等)

原链接: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;
        }
    }
}

猜你喜欢
数据结构与算法 4734 在关于树的多种算法中都用到了树的来使树保持相对平衡,比如avl树,红黑树等...1.树的左(pivot为中心点)2.来个动3.代码演示:/** *左 *p为的中心点
数据结构与算法 4064 avl树:AVL树本质上是一颗二叉查找树1.avl树的性质左子树和右子树的高度之差的绝对值不超过1树中的每个左子树和右子树都是AVL树每个节点都有一个平衡因子(balancefactor--bf),任一节点的平衡因子是-1,0,1之一2.avl树的操作AVL树的操作基本和二叉查找树一样,这里我们关注的是两个变化很大的操作:插入和删除!AVL树不仅是一颗二叉查找树,它还有其他的性质。如果我们按照一般
工具 1366 工具类packagecom.dzqc.yx.util;importjava.io.FileInputStream;importjava.io.FileOutputStream;importjava.io.IOException;importjava.io.InputStream;importjava.io.OutputStream;importsun.misc.BASE64Decoder;impo
其他 687 式:Word,Excel,PowerPoint,Project,等office文档以及PDF文档。除了强大的文件操纵组件之外,Aspose.Total还提供了用于制、写电子邮件、拼写检查、创建条形码、
weblog 3130 本篇文章为红黑树的预备知识,暂且不涉及节点颜色。 二叉树左的过程是将x的右子树绕x逆时针,使得x的右子树成为x的父节点,同时修改相关节点的引用。之后,二叉查找树的属性仍然满足
official 1101 《摄影艺术》   50x变焦、超强稳定……今年手机摄影几乎成了各大厂商的必争之地。可问题是,似乎总有一个声音在说:我们家的手机素多高多高~所以它的拍照就有多好多好…… 18年12月,华为首发
算法基础 788 关系基本命令`uname-r`:查看内核`systemctlstartdocker`:启动docker镜`dockerversion`:查看docker版本`dockerinfo`:查看
算法基础 757 LocalDateTimeDate/***LocalDateTimeDate*@paramlocalDateTime*@return
目录
没有一个冬天不可逾越,没有一个春天不会来临。最慢的步伐不是跬步,而是徘徊,最快的脚步不是冲刺,而是坚持。