算法leetcode|48. 旋转图像(rust重拳出击)

这篇具有很好参考价值的文章主要介绍了算法leetcode|48. 旋转图像(rust重拳出击)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。



48. 旋转图像:

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像,这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

样例 1:

算法leetcode|48. 旋转图像(rust重拳出击)

输入:
	matrix = [[1,2,3],[4,5,6],[7,8,9]]
	
输出:
	[[7,4,1],[8,5,2],[9,6,3]]

样例 2:

算法leetcode|48. 旋转图像(rust重拳出击)

输入:
	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]]

提示:

  • n == matrix.length == matrix[i].length
  • 1 <= n <= 20
  • -1000 <= matrix[i][j] <= 1000

分析:

  • 面对这道算法题目,二当家的陷入了沉思。
  • 一般最容易想到的就是遍历矩阵的每个值,放到一个新矩阵里面。
  • 使用原矩阵最大的问题就是,我们知道一个位置的值旋转后应该放到哪里去,但是新的位置上同样有值,不能直接覆盖掉。
  • 有经验的大佬们可以想到用翻转代替旋转,把旋转分解为2步,翻转的特点是两两交换,不会覆盖丢失原值。
  • 事实上还有一个很好的办法,矩阵,一个正方形,中心对称,可以均分为4份(边长为奇数时,中心点不需要移动,可以排除,其他点仍然可以4等分),然后遍历其中一份,将4份中对应位置的值做顺序交换。
    算法leetcode|48. 旋转图像(rust重拳出击)算法leetcode|48. 旋转图像(rust重拳出击)

题解:

rust:

  • 两次翻转:
impl Solution {
    pub fn rotate(matrix: &mut Vec<Vec<i32>>) {
        let n = matrix.len();

        // 水平翻转
        (0..n / 2).for_each(|i| {
            (0..n).for_each(|j| {
                let temp = matrix[i][j];
                matrix[i][j] = matrix[n - i - 1][j];
                matrix[n - i - 1][j] = temp;
            });
        });

        // 主对角线翻转
        (0..n).for_each(|i| {
            (0..i).for_each(|j| {
                let temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            });
        });
    }
}
  • 原地旋转:
impl Solution {
    pub fn rotate(matrix: &mut Vec<Vec<i32>>) {
        let n = matrix.len();

        (0..n / 2).for_each(|i| {
            (0..(n + 1) / 2).for_each(|j| {
                let temp = 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] = temp;
            });
        });
    }
}

go:

func rotate(matrix [][]int)  {
    n := len(matrix)

	// 水平翻转
	for i := 0; i < n/2; i++ {
		matrix[i], matrix[n-1-i] = matrix[n-1-i], matrix[i]
	}

	// 主对角线翻转
	for i := 0; i < n; i++ {
		for j := 0; j < i; j++ {
			matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
		}
	}
}

c++:

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();

        // 水平翻转
        for (int i = 0; i < n / 2; ++i) {
            for (int j = 0; j < n; ++j) {
                swap(matrix[i][j], matrix[n - i - 1][j]);
            }
        }

        // 主对角线翻转
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                swap(matrix[i][j], matrix[j][i]);
            }
        }
    }
};

c:

void rotate(int** matrix, int matrixSize, int* matrixColSize){
    // 水平翻转
    for (int i = 0; i < matrixSize / 2; ++i) {
        for (int j = 0; j < matrixSize; ++j) {
            int temp = matrix[i][j];
            matrix[i][j] = matrix[matrixSize - i - 1][j];
            matrix[matrixSize - i - 1][j] = temp;
        }
    }

    // 主对角线翻转
    for (int i = 0; i < matrixSize; ++i) {
        for (int j = 0; j < i; ++j) {
            int temp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = temp;
        }
    }
}

python:

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """

        n = len(matrix)

        # 水平翻转
        for i in range(n // 2):
            for j in range(n):
                matrix[i][j], matrix[n - i - 1][j] = matrix[n - i - 1][j], matrix[i][j]

        # 主对角线翻转
        for i in range(n):
            for j in range(i):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]


java:

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

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】~
放弃不难,但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子:https://le-yi.blog.csdn.net/ 博客原创~文章来源地址https://www.toymoban.com/news/detail-429759.html


到了这里,关于算法leetcode|48. 旋转图像(rust重拳出击)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法leetcode|89. 格雷编码(rust重拳出击)

    n 位格雷码序列 是一个由 2 n 个整数组成的序列,其中: 每个整数都在范围 [0, 2 n - 1] 内(含 0 和 2 n - 1) 第一个整数是 0 一个整数在序列中出现 不超过一次 每对 相邻 整数的二进制表示 恰好一位不同 ,且 第一个 和 最后一个 整数的二进制表示 恰好一位不同 给你一个整数

    2024年02月04日
    浏览(45)
  • 算法leetcode|79. 单词搜索(rust重拳出击)

    给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中,返回 true ;否则,返回 false 。 单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

    2024年02月09日
    浏览(58)
  • 算法leetcode|70. 爬楼梯(rust重拳出击)

    假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢? 1 = n = 45 面对这道算法题目,二当家的再次陷入了沉思。 可以爬一阶或者两阶台阶,那也就是说,除了初始位置,和第一阶台阶,到达其他阶台阶 n 的方式

    2024年02月12日
    浏览(38)
  • 算法leetcode|71. 简化路径(rust重拳出击)

    给你一个字符串 path ,表示指向某一文件或目录的 Unix 风格 绝对路径 (以 \\\'/\\\' 开头),请你将其转化为更加简洁的规范路径。 在 Unix 风格的文件系统中,一个点( . )表示当前目录本身;此外,两个点 ( .. ) 表示将目录切换到上一级(指向父目录);两者都可以是复杂相

    2024年02月12日
    浏览(44)
  • 算法leetcode|60. 排列序列(rust重拳出击)

    给出集合 [1,2,3,...,n] ,其所有元素共有 n! 种排列。 按大小顺序列出所有排列情况,并一一标记,当 n = 3 时, 所有排列如下: \\\"123\\\" \\\"132\\\" \\\"213\\\" \\\"231\\\" \\\"312\\\" \\\"321\\\" 给定 n 和 k ,返回第 k 个排列。 1 = n = 9 1 = k = n! 面对这道算法题目,二当家的再次陷入了沉思。 如果模拟,按顺序生成k个

    2024年02月12日
    浏览(39)
  • 算法leetcode|54. 螺旋矩阵(rust重拳出击)

    给你一个 m 行 n 列的矩阵 matrix ,请按照 顺时针螺旋顺序 ,返回矩阵中的所有元素。 m == matrix.length n == matrix[i].length 1 = m, n = 10 -100 = matrix[i][j] = 100 面对这道算法题目,二当家的再次陷入了沉思。 可以每次循环移动一步,判断移到边界就变换方向,巧用数组可以减少逻辑判断

    2024年02月08日
    浏览(47)
  • 算法leetcode|72. 编辑距离(rust重拳出击)

    给你两个单词 word1 和 word2 , 请返回将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作: 插入一个字符 删除一个字符 替换一个字符 0 = word1.length, word2.length = 500 word1 和 word2 由小写英文字母组成 面对这道算法题目,二当家的再次陷入了沉思。 编

    2024年02月12日
    浏览(40)
  • 算法leetcode|65. 有效数字(rust重拳出击)

    有效数字 (按顺序)可以分成以下几个部分: 一个 小数 或者 整数 (可选)一个 \\\'e\\\' 或 \\\'E\\\' ,后面跟着一个 整数 小数 (按顺序)可以分成以下几个部分: (可选)一个符号字符( \\\'+\\\' 或 \\\'-\\\' ) 下述格式之一: 至少一位数字,后面跟着一个点 \\\'.\\\' 至少一位数字,后面跟着一个

    2024年02月15日
    浏览(41)
  • 算法leetcode|91. 解码方法(rust重拳出击)

    一条包含字母 A-Z 的消息通过以下映射进行了 编码 : 要 解码 已编码的消息,所有数字必须基于上述映射的方法,反向映射回字母(可能有多种方法)。例如, \\\"11106\\\" 可以映射为: \\\"AAJF\\\" ,将消息分组为 (1 1 10 6) \\\"KJF\\\" ,将消息分组为 (11 10 6) 注意,消息不能分组为 (1 11 06) ,因

    2024年02月05日
    浏览(41)
  • 算法leetcode|75. 颜色分类(rust重拳出击)

    给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums , 原地 对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。 我们使用整数 0 、 1 和 2 分别表示红色、白色和蓝色。 必须在不使用库内置的 sort 函数的情况下解决这个问题。 n == nums.length

    2024年02月10日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包