[LeetCode] Rotate Image
LeetCode Image rotate
2023-09-11 14:17:25 时间
You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Follow up:
Could you do this in-place?
思路一:
b[i][j] = a[n-1-j][i], 构造b,然后将b赋值给a,空间复杂度O(n*n)
class Solution { public: void rotate(vector<vector<int> > &matrix) { size_t n = matrix.size(); vector<vector<int> > re; vector<int> b; b.resize(n); for(int i = 0; i < n; i ++) re.push_back(b); for(int i = 0; i < n; i ++) for(int j = 0; j < n; j ++) { re[i][j] = matrix[n-j-1][i]; } for(int i = 0; i < n; i ++) for(int j = 0; j < n; j ++) matrix[i][j] = re[i][j]; } };
思路二:旋转90°= 第一步, 沿着副对角线翻转+ 第二步,沿着水平中轴线翻转,空间复杂度O(1)
class Solution { public: #if 0 void rotate(vector<vector<int> > &matrix) { size_t n = matrix.size(); vector<vector<int> > re; vector<int> b; b.resize(n); for(int i = 0; i < n; i ++) re.push_back(b); for(int i = 0; i < n; i ++) for(int j = 0; j < n; j ++) { re[i][j] = matrix[n-j-1][i]; } for(int i = 0; i < n; i ++) for(int j = 0; j < n; j ++) matrix[i][j] = re[i][j]; } #endif public: void rotateFromDiagonal (vector<vector<int> > &matrix) { size_t n = matrix.size(); int tmp; for(int i = 0; i < n; i ++) for(int j = 0; j < n-i; j ++) { tmp = matrix[i][j]; matrix[i][j] = matrix[n-j-1][n-i-1]; matrix[n-j-1][n-i-1] = tmp; } } void rotateFromHorizon(vector<vector<int> > &matrix) { size_t n = matrix.size(); int tmp; for(int i = 0; i < n/2; i ++) for(int j = 0; j < n; j ++) { tmp = matrix[i][j]; matrix[i][j] = matrix[n-1-i][j]; matrix[n-1-i][j] = tmp; } } void rotate(vector<vector<int> > &matrix) { rotateFromDiagonal(matrix); rotateFromHorizon(matrix); } };
相关文章
- Leetcode 之Binary Tree Postorder Traversal(44)
- Java实现 LeetCode 835 图像重叠(暴力)
- Java实现 LeetCode 788 旋转数字(暴力)
- Java实现 LeetCode 781 森林中的兔子(分析题)
- Java实现 LeetCode 589 N叉树的前序遍历(遍历树)
- Java实现 LeetCode 403 青蛙过河
- Java实现 LeetCode 334 递增的三元子序列
- Java实现 LeetCode 257 二叉树的所有路径
- Java实现 LeetCode 136 只出现一次的数字
- (LeetCode 72)Edit Distance
- Leetcode学习计划之动态规划入门day14(1314,120)
- leetcode 226. 翻转二叉树
- 已解决Image.open()识别图片抛出异常PIL.UnidentifiedImageError: cannot identify image file的正确解决方法,亲测有效
- PIL Image “image file is truncated“问题分析与解决,添加ImageFile.LOAD_TRUNCATED_IMAGES = True
- [LeetCode] 16. 最接近的三数之和 ☆☆☆(双指针)
- [LeetCode] 24. Swap Nodes in Pairs ☆☆☆(链表,相邻两节点交换)
- 【Leetcode刷题Python】 LeetCode 2038. 如果相邻两个颜色均相同则删除当前颜色