Leetcode矩阵-day7

Leetcode矩阵-day7记录自己刷力扣备战秋招的刷题笔记❤️​ ——wosz矩阵矩阵简单来说就是二维数组在C中可以通过二维数组的形式进行创建vectorvectorintmatrix在刷题中对于矩阵的操作主要有创建矩阵直接使用 vector 进行创建即可vectorvectorintmatrix遍历矩阵两层 for 循环进行遍历for(inti0;im;i){for(intj0;jn;j){coutmatrix[i][j] ;}}矩阵转置让行转换成列列转换成行res[j][i]matrix[i][j];先把最基础的掌握了再刷题中我再总结吧。矩阵置零给定一个m x n的矩阵如果一个元素为0则将其所在行和列的所有元素都设为0。请使用原地算法**。****输入**matrix [[1,1,1],[1,0,1],[1,1,1]]输出[[1,0,1],[0,0,0],[1,0,1]]自己的题解classSolution{public:voidsetZeroes(vectorvectorintmatrix){intmmatrix.size();//行intnmatrix[0].size();//列vectorintrow(m,0);//行标记数组vectorintcol(n,0);//列标记数组for(inti0;im;i){for(intj0;jn;j){if(matrix[i][j]0)//标记{row[i]1;col[j]1;}}}//处理for(inti0;im;i){for(intj0;jn;j){if(row[i]1||col[j]1)//通过那个行列标记进行计算{matrix[i][j]0;}}}}};我的思路就是直接进行遍历每一个元素进行遍历然后在内层直接进行判断然后去将我们的标记数组置1进行标记之后再进行一次遍历通过行列标记进行置0操作即可感觉确实是暴力做法。官方题解classSolution{public:voidsetZeroes(vectorvectorintmatrix){intmmatrix.size();intnmatrix[0].size();vectorintrow(m),col(n);for(inti0;im;i){for(intj0;jn;j){if(!matrix[i][j]){row[i]col[j]true;}}}for(inti0;im;i){for(intj0;jn;j){if(row[i]||col[j]){matrix[i][j]0;}}}}};官方的思路也是通过标记数组的形式先对我们的数组进行遍历标记然后利用标记数组进行那个再次遍历置0即可。螺旋矩阵给你一个m行n列的矩阵matrix请按照顺时针螺旋顺序返回矩阵中的所有元素。**输入**matrix [[1,2,3],[4,5,6],[7,8,9]]输出[1,2,3,6,9,8,7,4,5]自己的题解classSolution{public:vectorintspiralOrder(vectorvectorintmatrix){vectorinttag;if(matrix.empty()||matrix[0].empty())returntag;inttop0;intleft0;intbottonmatrix.size()-1;intrightmatrix[0].size()-1;while(topbottonleftright){// 向右for(intileft;iright;i){tag.push_back(matrix[top][i]);}top;// 向下for(intitop;ibotton;i){tag.push_back(matrix[i][right]);}right--;// 向左if(topbotton){for(intiright;ileft;i--){tag.push_back(matrix[botton][i]);}botton--;}// 向上if(leftright){for(intibotton;itop;i--){tag.push_back(matrix[i][left]);}left;}}returntag;}};我的思路是我看到这个我就只找到一个规律就是我们的这个走向都是确定的1.首先就是这个走向时固定的段数是4段 2.然后这个的每一段的走向也固定的向右向下向左向上。但是怎么连接起来呢最简单的就是不断收缩进行每次移动之后进行收缩。官方题解classSolution{public:vectorintspiralOrder(vectorvectorintmatrix){if(matrix.size()0||matrix[0].size()0){return{};}introwsmatrix.size(),columnsmatrix[0].size();vectorintorder;intleft0,rightcolumns-1,top0,bottomrows-1;while(leftrighttopbottom){for(intcolumnleft;columnright;column){order.push_back(matrix[top][column]);}for(introwtop1;rowbottom;row){order.push_back(matrix[row][right]);}if(leftrighttopbottom){for(intcolumnright-1;columnleft;column--){order.push_back(matrix[bottom][column]);}for(introwbottom;rowtop;row--){order.push_back(matrix[row][left]);}}left;right--;top;bottom--;}returnorder;}};官方的两种题解这个方法就是和我们的做法类似就是进行按照行进路线收缩。旋转图像给定一个n×n的二维矩阵matrix表示一个图像。请你将图像顺时针旋转 90 度。你必须在** 原地** 旋转图像这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。**输入**matrix [[1,2,3],[4,5,6],[7,8,9]]输出[[7,4,1],[8,5,2],[9,6,3]]自己的题解classSolution{public:voidrotate(vectorvectorintmatrix){intnmatrix.size();for(inti0;in/2;i){// 控制层数for(intji;jn-1-i;j){// 控制当前层的列inttempmatrix[i][j];matrix[i][j]matrix[n-1-j][i];matrix[n-1-j][i]matrix[n-1-i][n-1-j];matrix[n-1-i][n-1-j]matrix[j][n-1-i];matrix[j][n-1-i]temp;}}}};我的思路就是既然不能新开矩阵进行变化那一定存在规律可以发现**m,n→(nsize-1-m)** 我们就可以利用这个规律来进行变化。就根据这个来让四个位置的进行轮换就行。matrix[i][j]matrix[n-1-j][i];matrix[n-1-j][i]matrix[n-1-i][n-1-j];matrix[n-1-i][n-1-j]matrix[j][n-1-i];matrix[j][n-1-i]temp;还有一种想法就是我直接先进行转置然后再进行列平移就行转置直接就坐标交换比较简单方便。这个方法的遍历思路就是分为几个层外层和内层进行变化然后每一层又要依次减少一个头和尾。列平移就直接每一行进行反转就行classSolution{public:voidrotate(vectorvectorintmatrix){intnmatrix.size();for(inti0;in;i){//转置for(intji;jn;j){swap(matrix[i][j],matrix[j][i]);}}for(inti0;in;i){//每一行反转reverse(matrix[i].begin(),matrix[i].end());}}};我做这个题的时候明显感觉到矩阵中的难点就是对于遍历的时候那个遍历的范围。官方题解classSolution{public:voidrotate(vectorvectorintmatrix){intnmatrix.size();for(inti0;in/2;i){for(intj0;j(n1)/2;j){inttempmatrix[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;}}}};官方的思路也是通过找规律发现这几个中的一个坐标规律和联系来进行的解题。搜索二维矩阵II编写一个高效的算法来搜索*m* x *n*矩阵matrix中的一个目标值target。该矩阵具有以下特性每行的元素从左到右升序排列。每列的元素从上到下升序排列。**输入**matrix [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target 5**输出**true自己的题解classSolution{public:boolsearchMatrix(vectorvectorintmatrix,inttarget){intmmatrix.size();intnmatrix[0].size();for(inti0;im;i){for(intj0;jn;j){if(matrix[i][j]target)returntrue;}}returnfalse;}};我的思路是不管了先暴力一手然后我们再进行根据这个规律进行找更优的方法。让AI大哥说了一下这题经典做法是从右上角开始找时间复杂度O(mn)。如果当前值target那这一列下面都更大这一列不用看了往左走如果当前值target那这一行左边都更小这一行不用看了往下走如果相等直接返回 trueclassSolution{public:boolsearchMatrix(vectorvectorintmatrix,inttarget){intmmatrix.size();intnmatrix[0].size();//从右上角开始查找inti0,jn-1;while(imj0){if(matrix[i][j]target){returntrue;}elseif(matrix[i][j]target)//行不用看了{i;}else//大于目标的话就是这一列不用看了{j--;}}returnfalse;}};官方题解classSolution{public:boolsearchMatrix(vectorvectorintmatrix,inttarget){for(constautorow:matrix){autoitlower_bound(row.begin(),row.end(),target);if(it!row.end()*ittarget){returntrue;}}returnfalse;}};官方也有上面的从右上角开始查找我们学习一下官方的二分查找法。就是每一行都做一次二分查找。介绍一下C使用二分查找法的API。二分查找为什么这一题可以对每一行做二分查找这一题已经告诉我们每一行都是从左到右升序排列所以我们可以把每一行都看成一个有序数组。既然是有序数组就可以在每一行里用一次二分查找去找target。C 中常用的二分查找 API在 C 里二分查找相关 API 主要在#include algorithm里面最常用的有这几个lower_bound(begin, end, target)返回第一个大于等于target的位置upper_bound(begin, end, target)返回第一个大于target的位置binary_search(begin, end, target)直接返回true或false表示目标值是否存在这题官方题解使用的是lower_bound因为它不只是告诉你“有没有”还会返回一个迭代器位置这样我们就能继续判断这个位置上的值是不是正好等于target。lower_bound怎么理解假设有一个有序数组vectorintrow{1,4,7,11,15};如果我们写autoitlower_bound(row.begin(),row.end(),7);那么it就会指向值为7的位置。如果写autoitlower_bound(row.begin(),row.end(),8);因为数组里没有8它会返回第一个大于等于8的位置也就是指向11。所以这一题里要这样判断autoitlower_bound(row.begin(),row.end(),target);if(it!row.end()*ittarget){returntrue;}这里分成两步理解it ! row.end()先判断有没有越界*it target再判断当前位置是不是真的等于目标值为什么不能只判断it ! row.end()因为lower_bound找到的是第一个大于等于target的位置不一定就是target本身。