LeetCode 0048 - Rotate Image
# Hints
- 模拟
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Medium |
You are given an 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Note:
You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.
Example 1:
Given input matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
rotate the input matrix in-place such that it becomes:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
Example 2:
Given input matrix =
[
[ 5, 1, 9,11],
[ 2, 4, 8,10],
[13, 3, 6, 7],
[15,14,12,16]
],
rotate the input matrix in-place such that it becomes:
[
[15,13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7,10,11]
]
# 题意
给定一个 的矩阵,要求将其顺时针旋转 度,且不能额外开辟一个 的辅助空间。
# 题解
简单模拟题。由于对额外空间复杂度的限制,我们无法直接解决问题。不难发现在旋转时是每四个点为一组独立旋转的,因此我们只需要找到所有的四点组,然后对每组点进行三次交换即可。
我的实现是从外圈到内圈逐层处理,共 层,每个圈内的坐标变换都是相同的。其他的实现方法亦可。
# AC代码
class Solution {
private:
const int px[4] = {0, 0, 1, 1};
const int py[4] = {0, 1, 1, 0};
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};
public:
void rotate(vector<vector<int>> & matrix) {
// 初始化
int n = matrix.size();
int x[4], y[4];
// 遍历
for (int d = 0; d < n / 2; d ++) {
int len = n - 1 - 2*d;
for (int i = 0; i < len; i ++) {
// 获取坐标
for (int j = 0; j < 4; j ++) {
x[j] = d + len * px[j] + i * dx[j];
y[j] = d + len * py[j] + i * dy[j];
}
// 交换
for (int j = 1; j < 4; j ++) {
swap(matrix[x[0]][y[0]], matrix[x[j]][y[j]]);
}
}
}
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01