当前位置：首页 > java >正文

每日算法刷题Day2 5.10:leetcode数组1道题3种解法，用时40min

java 2025/5/13 3:37:10

4.LC 旋转矩阵(中等，学习)

面试题 01.07. 旋转矩阵 - 力扣（LeetCode）

思想:

法一:
额外空间数组来回赋值拷贝
法二:
1.翻转90度得到等式a[j][n-i-1]=a[i][j],但是会改变a[j][n-i-1]原始值，再去看该位置变到哪一位置
分析可得,4个位置翻转90度就是4个位置轮换赋值,得到公式
在这里插入图片描述
所以问题变成利用temp变量完成4项原地交换
2.接下来分析i和j的遍历范围，由上述4个位置得，只要遍历1个区域位置即可，所以把正方形划分成4份，取左上角区域,但是不知道n是奇还是偶，所以要分奇偶讨论
在这里插入图片描述
偶数i,j:[0,n/2)

奇数:i:[0,(n+1)/2),j:[0,n/2) 所以综合可得,i:i:[0,(n+1)/2),j:[0,n/2)
法三:
1.先水平翻转:a[i][j]=a[n-i-1][j],遍历范围:i:[0,n/2),j:[0,n)
2.然后再沿着主对角线翻转:a[i][j]=a[j][i],遍历范围:i:[0,n),j:[0,i)

代码

c++:
法一:

class Solution {
public:void rotate(vector<vector<int>>& matrix) {int n = matrix.size();auto temp = matrix;for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {temp[i][j] = matrix[n - j - 1][i];}}matrix = temp;}
};

法二:

class Solution {
public:void rotate(vector<vector<int>>& matrix) {int n = matrix.size();for (int i = 0; i < (n + 1) / 2; i++) {for (int j = 0; j < n / 2; j++) {int 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;}}}
};

法三:

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

python:
法一:

class Solution:def rotate(self, matrix: List[List[int]]) -> None:"""Do not return anything, modify matrix in-place instead."""n = len(matrix)temp=[[0]*n for _ in range(n)]# or temp = [row[:] for row in matrix]for i in range(n):for j in range(n):temp[i][j]=matrix[n-j-1][i]matrix[:]=temp

python对象本质是对象的指针，而不是独立存值的容器。
1.替换原始矩阵
a=b;:让a指向b指向的对象，改变a的同时也改变b的内容
所以列表改变值需要:matrix[:]=temp;
2.深拷贝二维列表
temp=matrix[:]只复制了外层，内层仍共享
temp=[[0]*n for _ in range(n)]创建一个新的nxn数组
temp=[row[:] for row in matrix]才深拷贝二维数组matrix
法二:

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 + 1) // 2):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

整数除法是//，向下取整
法三:

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]

多变量同时赋值