济宁 创意大厦 网站建设,ai免费logo设计一键生成,广告公司简介怎么写,深圳搜索竞价账户托管一、48. 旋转图像
1.1#xff1a;题目
48. 旋转图像
1.2#xff1a;解题思路 题型#xff1a;顺/逆时针旋转矩阵#xff1b; ❗❗核心思想/ 关键#xff1a;不可暴力模拟#xff0c;先镜像#xff0c;后水平翻转 这题的意思很简单#xff0c;就是让我们把矩阵顺时…一、48. 旋转图像
1.1题目
48. 旋转图像
1.2解题思路 题型顺/逆时针旋转矩阵 ❗❗核心思想/ 关键不可暴力模拟先镜像后水平翻转 这题的意思很简单就是让我们把矩阵顺时针选择90°,但是难点在于如何原地旋转。 寻常的思路有以下两种可能会误认为去模拟一下一圈一圈的去遍历然后进行旋转又或者是想去找出当前坐标和旋转后像素对应坐标位置之间的关系结果发现都想不出来很好的解决方法。 这题的关键就在于不走寻常路。它用了另外一种比较巧妙的方法对于计算机比较好理解但对于我们可能一下子想不到的方法去解决了。对于这种题只要有个印象以后遇到类似题目就不会懵圈了。
1.3实现代码——c
class Solution {
public:void rotate(vectorvectorint matrix) {//Step1:先对原矩阵逐行遍历进行镜像for(int i 0; i matrix.size() - 1; i){for (int j i 1; j matrix.size(); j){//对角线元素进行交换int temp matrix[i][j];matrix[i][j] matrix[j][i];matrix[j][i] temp;}}//Step2: 每行进行翻转for (int i 0; i matrix.size(); i){//对这一行元素进行翻转for (int j 0; j matrix.size()/2; j){int temp matrix[i][j];matrix[i][j] matrix[i][matrix.size() - j - 1];matrix[i][matrix.size() - j - 1] temp;}}}
};二、54. 螺旋矩阵
2.1题目 1.1解题思路
题型矩阵的螺旋遍历❗❗核心思想/ 关键模拟用四个边界点去控制遍历的边界 这题最开始我的思路是先求出遍历几圈一个圈数的大循环然后根据边界和当前遍历圈数的关系再去一圈一圈的模拟遍历发现真正这种纯模拟的方法很不好把握边界也很容易少加或者多加元素。 其实这题最好的思路如下图设置四个边界标记变量每一次循环完一圈后更新一下四个边界。外面的大循环是结果数组的元素个数控制着这样就不会多加或少加元素 随着数组遍历边界更新收缩 注意在遍历完一条边后边界点也要随之更新
1.3实现代码——c
// 注意cpp 代码由 chatGPT 根据我的 java 代码翻译旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性仅供参考。如有疑惑可以参照我写的 java 代码对比查看。#include vector
#include dequeusing namespace std;vectorint spiralOrder(vectorvectorint matrix) {int m matrix.size(), n matrix[0].size();int upper_bound 0, lower_bound m - 1;int left_bound 0, right_bound n - 1;vectorint res;// res.size() m * n 则遍历完整个数组while (res.size() m * n) {if (upper_bound lower_bound) {// 在顶部从左向右遍历for (int j left_bound; j right_bound; j) {res.push_back(matrix[upper_bound][j]);}// 上边界下移upper_bound;}if (left_bound right_bound) {// 在右侧从上向下遍历for (int i upper_bound; i lower_bound; i) {res.push_back(matrix[i][right_bound]);}// 右边界左移right_bound--;}if (upper_bound lower_bound) {// 在底部从右向左遍历for (int j right_bound; j left_bound; j--) {res.push_back(matrix[lower_bound][j]);}// 下边界上移lower_bound--;}if (left_bound right_bound) {// 在左侧从下向上遍历for (int i lower_bound; i upper_bound; i--) {res.push_back(matrix[i][left_bound]);}// 左边界右移left_bound;}}return res;
}
1.4总结易错点
在这题注意四个边界点每遍历完一边就必须更新因为边界点控制的遍历边界条件是左闭右闭每次遍历一条边之前先判断一下是否满足遍历条件易错否则容易重复遍历元素
像下图这样如果没有在遍历没条边之前进行if可行性判断那么就会重复遍历元素在第二个循环的第三个if不能进去因为遍历完上边之后这一圈的元素都遍历完了
为什么会出现这种情况呢我们不是明明规定好边界了吗因为每次在遍历一条边时的确有边界但是你要保证这个边界是合理的如果边界合理OK你就可以遍历但是在这题中在边界缩小过程中很有可能出现边界不合理的情况
