leetcode第48题

简介: 将一个矩阵顺时针旋转 90 度,并且不使用额外的空间。大概属于找规律的题,没有什么一般的思路,观察就可以了。解法一可以先转置,然后把每列对称交换交换一下

image.png

将一个矩阵顺时针旋转 90 度,并且不使用额外的空间。大概属于找规律的题,没有什么一般的思路,观察就可以了。

解法一

可以先转置,然后把每列对称交换交换一下

image.png

publicvoidrotate(int[][] matrix) {
//以对角线为轴交换for (inti=0; i<matrix.length; i++) {
for (intj=0; j<=i; j++) {
if (i==j) {
continue;
            }
inttemp=matrix[i][j];
matrix[i][j] =matrix[j][i];
matrix[j][i] =temp;
        }
    } 
//交换列for (inti=0, j=matrix.length-1; i<matrix.length/2; i++, j--) {
for (intk=0; k<matrix.length; k++) {
inttemp=matrix[k][i];
matrix[k][i] =matrix[k][j];
matrix[k][j] =temp;
        }
    }
}

时间复杂度:O(n²)。

空间复杂度:O(1)。

也可以先以横向的中轴线为轴,对称的行进行交换,然后再以对角线交换。

解法二

我把这个链接的思路贴过来,里边评论有张图也都顺道贴过来吧,写的很好。

image.png

一圈一圈的循环交换,很妙!

publicvoidrotate(int[][] matrix) {
intn=matrix.length;
for (inti=0; i<n/2; i++) 
for (intj=i; j<n-i-1; j++) {
inttmp=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]=tmp;
        }
}

时间复杂度:O(n²)。

空间复杂度:O(1)。

这道题就是对题目的特征进行观察就可以了。


目录
打赏
0
0
0
0
10
分享
相关文章
|
9月前
leetcode-475:供暖器
leetcode-475:供暖器
59 0
单链表反转 LeetCode 206
单链表反转 LeetCode 206
85 0
LeetCode 66. Plus One
给定表示非负整数的非空数字数组,加上整数的1。 存储数字使得最高有效数字位于列表的开头,并且数组中的每个元素包含单个数字。 您可以假设整数不包含任何前导零,除了数字0本身。
114 0
LeetCode 66. Plus One
leetcode第50题
求幂次方,用最简单的想法,就是写一个 for 循环累乘。 至于求负幂次方,比如 2^{-10}2−10,可以先求出 2^{10}210,然后取倒数,1/2^{10}1/210 ,就可以了 double mul = 1; if (n > 0) { for (int i = 0; i < n; i++) { mul *= x; } } else { n = -n; for (int i = 0; i < n; i++) { mul *= x; } mul = 1 / mul; }
115 0
leetcode第50题
leetcode第54题
在 leetcode 的 solution 和 discuss 看了下,基本就是这个思路了,只是实现上有些不同,怎么用来标记是否走过,当前方向,怎么遍历,实现有些不同,但本质上是一样的。就是充分理解题意,然后模仿遍历的过程。
115 0
leetcode第54题
leetcode第39题
对回溯法又有了更深的了解,一般的架构就是一个大的 for 循环,然后先 add,接着利用递归进行向前遍历,然后再 remove ,继续循环。而解法二的动态规划就是一定要找到递进的规则,开始的时候就想偏了,导致迟迟想不出来。
111 0
leetcode第39题
leetcode第55题
当自己按照 45 题的思路写完的时候,看 Solution 的时候都懵逼了,这道题竟然这么复杂?不过 Solution 把问题抽象成动态规划的思想,以及优化的过程还是非常值得学习的。
105 0
leetcode第55题
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等