【程序员面试金典】 01.07. 旋转矩阵
1. 题目
作者：有限自动机
给定一幅由N × N矩阵表示的图像，其中每个像素的大小为4字节，编写一种方法，将图像旋转90度。
不占用额外内存空间能否做到？
示例 1:
给定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
原地旋转输入矩阵，使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
示例 2:
给定 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]
]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/rotate-matrix-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public:
void rotate(vector<vector>& matrix) {
int i, j, a, b;
for(i = 0; i < matrix.size(); ++i)
{ //对角线交换
for(j = 0; j < i; ++j)
swap(matrix[i][j], matrix[j][i]);
}
for(i = 0; i < matrix.size(); ++i)
{ //每行反转
a = 0, b = matrix[0].size()-1;
while(a < b)
swap(matrix[i][a++], matrix[i][b--]);
}
}
};
2.2一次遍历
class Solution {
public:
void rotate(vector<vector>& matrix) {
int i, j, n = matrix.size();
for(i = 0; i < n/2; ++i)
{
for(j = i; j < n-i-1; ++j)
{
swp(matrix[i][j], matrix[n-1-j][i]);
swp(matrix[n-1-j][i], matrix[n-1-i][n-1-j]);
swp(matrix[n-1-i][n-1-j], matrix[j][n-1-i]);
}
}
}
inline void swp(int&a, int&b)
{
// b = a^b;
// a = a^b;
// b = a^b;
//或者一行代替
a ^= b ^= a ^= b;
}
};
这里所说的不占用任何额外空间交换两个数的值，这里可以有两种方法来实现。
方法一int x = 5;
int y = 10;
x = x + y;
y = x - y;
x = x - y;
先将两个数之和附给x，接着x-y自然就是原本x的值，这时候赋值给y，y就拿到了x原本的值。此时x依然是两个数之和，再进行x-y自然就是原本x的值。
这种方法比较直观，也好理解，但是可能存在溢出的情况
方法二int x = 5;
int y = 10;
x = x ^ y;
y = x ^ y;
x = x ^ y;
第二种方法利用了异或运算的性质：
相同的两个数异或结果为0 任何数与0异或结果还是其自身 异或运算满足交换律和结合律于是将x ^ y的结果赋予x，接着再将x与y异或，此时y的值就是x ^ y ^ y = x ^ (y ^ y) = x，也就是说y拿到了x原本的值。
此时x依然是两数异或的结果，而y是x原本的值，接着进行 x^ y就等同于x ^ y ^ x = y， 于是x就拿到了y原本的值。
这种方法很巧妙，也不太好理解，但是不存在溢出的情况。
参考：https://blog.csdn.net/qq_21201267/article/details/104516295#comments
作者：有限自动机
相关文章
Agatha
2020-05-15
Acacia
2021-06-08
Serafina
2020-03-27
Chloe
2020-10-28
Alexandra
2023-07-20
Rayna
2023-07-20
Orianna
2023-07-20
Cain
2023-07-20
Adelle
2023-07-20
Dabria
2023-07-20
Isoke
2023-07-21
Phoebe
2023-07-21
Bonita
2023-07-21
Rabia
2023-07-21
Linnea
2023-07-21
Jennifer
2023-07-21
Jayne
2023-07-21
Maleah
2023-07-21
Bella
2023-07-21