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]
多变量同时赋值