LeetCode第48题旋转图像

2023年 10月 3日 55.1k 0

继续打卡算法题,今天学习的是LeetCode第48题旋转图像,这道题目是道中等题。算法题的一些解题思路和技巧真的非常巧妙,每天看一看算法题和解题思路,我相信对我们的编码思维和编码能力有一些提升。

image.png

分析一波题目

本题需要将二维数组90度旋转,通过分析例子可以得到规则,从最外层(0,0)元素开始由外向里顺时针遍历,确定好第一个元素旋转90度之后的位置后,其实(0,0)后面的其他元素也确定了。 如果我们使用一个单独的二维数组来存储新的值,那么这个题就很好解了。

本题要求必须 原地 旋转,因此需要想想有没有其他办法。

有一个比较灵活的办法,使用两次翻转,首先是上下水平翻转,第二是对角线对称翻转,非常巧妙的解决此题。

image.png

本题解题技巧

本题如果不需要在本地旋转,解题思路很容易想到,但是要求不使用另外的数组,需要观察每个元素旋转之后的位置关系。本题理解水平翻转和对角线对称翻转的思想很关键。

编码解决


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;
            }
        }

    }
}

总结

哈哈,如果是第一次看到这类题目,这题还是有点难度的,我们见过了,以后有类似的题目,可以想下有没有这种有技巧的方式解决。观察转换前后的位置规律非常重要。

相关文章

JavaScript2024新功能:Object.groupBy、正则表达式v标志
PHP trim 函数对多字节字符的使用和限制
新函数 json_validate() 、randomizer 类扩展…20 个PHP 8.3 新特性全面解析
使用HTMX为WordPress增效:如何在不使用复杂框架的情况下增强平台功能
为React 19做准备:WordPress 6.6用户指南
如何删除WordPress中的所有评论

发布评论