矩阵一类题（考验你的代码控制能力如何）

转x33g5p2x  于2022-03-29 转载在 其他  
字(6.2k)|赞(0)|评价(0)|浏览(313)

一 螺旋矩阵I

二.螺旋矩阵II

三.旋转图像

四对角线遍历

五.矩阵置零

六 .有序矩阵中第k小的数

一 螺旋矩阵I

54. 螺旋矩阵 - 力扣（LeetCode） (leetcode-cn.com)

题目描述：

解题思路：

这道题呢跟我们日常生活中剥洋葱一样，我们首先把皮给剥了然后再剥里面的。这道题也是类似的我们定义一个开始点和一个结束点将其边界全部遍历。然后都往里面走。具体请看代码：

  1. class Solution {
  2. public:
  3.     vector<int> spiralOrder(vector<vector<int>>& matrix) {
  4.       vector<int>ans;  //记录答案                                              
  5.         int row1=0;//边界开始位置的行
  6.         int col1=0;//边界结束开始位置的列
  7.         int row2=matrix.size()-1;//边界结束的列
  8.         int col2=matrix[0].size()-1;//边界结束的列
  9.         while(row1<=row2&&col1<=col2)//如果两个点错过了说明已经遍历结束了
  10.         {
  11.             Print(matrix,ans,row1++,col1++,row2--,col2--);
  12.         }
  13.             
  14.          return ans;
  15.     }
  16.     void Print(vector<vector<int>>&matrix,vector<int>&ans,int row1,int col1,int row2,int col2)
  17.     {
  18.         if(row1==row2)//两个点的行变成一样了直接从这一行遍将其放入答案中
  19.         {
  20.            for(int i=col1;i<=col2;i++)
  21.            {
  22.                ans.push_back(matrix[row1][i]);
  23.            }
  24.            return;
  25.         }
  26.          //列相等
  27.          if(col1==col2)
  28.          {//直接将这一列遍历放入答案中
  29.             for(int i=row1;i<=row2;i++)
  30.             {
  31.                 ans.push_back(matrix[i][col1]);
  32.             }
  33.             return;
  34.          }
  35.         //说明行和列不相等将边框打印
  36.         //提前记录一下方便后序遍历
  37.          int rowStart=row1;
  38.          int colStart=col1;
  39.         while(colStart<col2)//打印最上层的边框
  40.         {
  41.             ans.push_back(matrix[row1][colStart++]);
  42.         }
  43.         //打印往下走的边框
  44.         while(rowStart<row2)
  45.         {
  46.             ans.push_back(matrix[rowStart++][col2]);
  47.         }
  48.         //打印往左走的
  49.         while(colStart>col1)
  50.         {
  51.             ans.push_back(matrix[row2][colStart--]);
  52.         }
  53.         //往上走
  54.         while(rowStart>row1)//注意这里是大于防止重复遍历
  55.         {
  56.             ans.push_back(matrix[rowStart][col1]);
  57.           
  58.             rowStart--;
  59.         }
  61.     }
  62. };

二.螺旋矩阵II

59. 螺旋矩阵 II - 力扣（LeetCode） (leetcode-cn.com)

题目描述：

解题思路：会了上一题这题就直接秒杀了只需要提前开好空间将值放入数组即可，和上题基本不变。具体请看代码

  1. class Solution {
  2. public:
  3.      int num=1;
  4.     vector<vector<int>> generateMatrix(int n) {
  5.         vector<vector<int>>ans(n,vector<int>(n));
  6.         int row1=0;
  7.         int col1=0;
  8.         int row2=n-1;
  9.         int col2=n-1;
  10.         while(row1<=row2&&col1<=col2)
  11.         {
  12.             Print(ans,row1++,col1++,row2--,col2--);
  13.         }
  14.         return ans;
  15.     }
  16.      void Print(vector<vector<int>>&ans,int row1,int col1,int row2,int col2)
  17.     {
  18.         if(row1==row2)//两个点的行变成一样了直接从这一行遍将其放入答案中
  19.         {
  20.            for(int i=col1;i<=col2;i++)
  21.            {
  22.                ans[row1][i]=num++;
  23.            }
  24.            return;
  25.         }
  26.          //列相等
  27.          if(col1==col2)
  28.          {//直接将这一列遍历放入答案中
  29.             for(int i=row1;i<=row2;i++)
  30.             {
  31.                 ans[i][col1]=num++;
  32.             }
  33.             return;
  34.          }
  35.         //说明行和列不相等将边框打印
  36.         //提前记录一下方便后序遍历
  37.          int rowStart=row1;
  38.          int colStart=col1;
  39.         while(colStart<col2)//打印最上层的边框
  40.         {
  41.             ans[row1][colStart++]=num++;
  42.         }
  43.         //打印往下走的边框
  44.         while(rowStart<row2)
  45.         {
  46.             ans[rowStart++][col2]=num++;
  47.         }
  48.         //打印往左走的
  49.         while(colStart>col1)
  50.         {
  51.             ans[row2][colStart--]=num++;
  52.         }
  53.         //往上走
  54.         while(rowStart>row1)//注意这里是大于防止重复遍历
  55.         {
  56.             ans[rowStart][col1]=num++;
  57.           
  58.             rowStart--;
  59.         }
  61.     }
  62.     
  63. };

三.旋转图像

面试题 01.07. 旋转矩阵 - 力扣（LeetCode） (leetcode-cn.com)

题目描述：

解题思路：

本题的实现思路和上题差不多首先将外面的旋转弄好，在往里面旋转直到行和行相等了。

如上图所示，由于第 11 步 D \rightarrow AD→A 已经将 AA 覆盖（导致 AA 丢失），此丢失导致最后第 44 步 A \rightarrow BA→B 无法赋值。为解决此问题，考虑借助一个「辅助变量 tmptmp 」预先存储 AA ，此时的旋转操作变为：

暂存 \ tmp = A \ A \leftarrow D \leftarrow C \leftarrow B \leftarrow tmp
暂存 tmp=A
A←D←C←B←tmp

对应代码：

  1. class Solution {
  2. public:
  3.     void rotate(vector<vector<int>>& matrix) {
  4.             int row1=0;
  5.             int col1=0;
  6.             int row2=matrix.size()-1;
  7.             int col2=matrix[0].size()-1;
  8.             while(row1<row2)//如果他们相等了说明不用旋转了
  9.             {
  10.                 Rotate(matrix,row1++,col1++,row2--,col2--);
  11.             }
  12.             
  14.     }
  15.     void Rotate(vector<vector<int>>&matrix,int row1,int col1,int row2,int col2)
  16.     {
  17.             for(int i=0;i<col2-col1;i++)
  18.             {
  19.             int tmp=matrix[row1][col1+i];//旋转的第一个元素
  20.              matrix[row1][col1+i] =matrix[row2-i][col1];//这一组最后一个元素覆盖第一个位置
  21.              matrix[row2-i][col1]=matrix[row2][col2-i];//依次覆盖
  22.              matrix[row2][col2-i]=matrix[row1+i][col2];
  23.              matrix[row1+i][col2]=tmp;//将第一个元素放到正确的位置
  24.             }
  25.             
  26.     }
  27. };

四对角线遍历

498. 对角线遍历 - 力扣（LeetCode） (leetcode-cn.com)

题目描述：

解题思路：

正对角线有一个性质：同一条对角线上每个点的(x，y)坐标之和相等。通过观察易知矩阵一共有 m + n - 1 条对角线，每条对角线要么从左下到右上，要么从右上到左下，先求出这两个端点，再根据当前循环的方向进行遍历。
根据对角线性质，只要知道端点的横纵坐标之一，就可以得到另一维坐标，图例中我们只关心横坐标。

对应代码：

  1. class Solution {
  2. public:
  3.     vector<int> findDiagonalOrder(vector<vector<int>>& mat) {
  4.              int endRow=mat.size()-1;
  5.              int endCol=mat[0].size()-1;
  6.              int row1=0;
  7.              int col1=0;
  8.              int row2=0;
  9.              int col2=0;
  10.              vector<int>ans;
  11.              bool fromUp=false;
  12.              while(row1<=endRow)
  13.              {
  14.                  Print(mat,ans,row1,col1,row2,col2,fromUp);
  15.                  row1=col1==endCol?row1+1:row1;//
  17.                  col1=col1==endCol?col1:col1+1;
  19.                   col2=row2==endRow?col2+1:col2;
  20.                   //注意这里要先判断否则会错过最后一些数据老铁可以思考一下
  22.                  row2=row2==endRow?row2:row2+1;
  23.                 
  24.                  fromUp=!fromUp;//方向每次取反
  25.              }
  26.              return ans;
  27.     }
  28.     void Print(vector<vector<int>>&mat,vector<int>&ans,int row1,int col1,int row2,int col2,bool fromUp)
  29.     {
  30.            if(fromUp)//如果为true说明是从上面往下面遍历
  31.            {
  32.                while(row1<=row2)
  33.                {
  34.                    ans.push_back(mat[row1++][col1--]);
  35.                }
  37.            }
  38.            else//说明是从下面往上面遍历
  39.            {
  40.                  while(row2>=row1)
  41.                  {
  42.                      ans.push_back(mat[row2--][col2++]);
  43.                  }
  44.            }
  45.     }
  46. };

五.矩阵置零

面试题 01.08. 零矩阵 - 力扣（LeetCode） (leetcode-cn.com)

题目描述：

解题思路：

1.使用第0列和第0行来标记某一行和某一列是否要被置0，遍历结束之后在遍历一次更加第0行和第0列来判断某个位置是否要置0，但是问题来了如果第0行和第0列里面就有0了，所以我们要用一个变量记录一下单独拿出来处理即可，具体请看代码。

  1. class Solution {
  2. public:
  3.     void setZeroes(vector<vector<int>>& matrix) {
  4.            bool iscol=false;//标记第一行是否要置0
  5.            bool isrow=false;//标记第一列是否要置0；
  6.            for(int i=0;i<matrix[0].size();i++)
  7.            {
  8.                //遍历第一行是否要置0
  9.                if(matrix[0][i]==0)
  10.                  isrow=true;
  11.            }
  12.            for(int i=0;i<matrix.size();i++)
  13.            {
  14.                if(matrix[i][0]==0)
  15.                {
  16.                    iscol=true;
  17.                }
  18.            }
  19.            //用0行和第0列的元素标记这一行和这一列是否需要置0
  20.            for(int i=1;i<matrix.size();i++)
  21.            {
  22.                for(int j=1;j<matrix[0].size();j++)
  23.                {
  24.                    if(matrix[i][j]==0)
  25.                    {
  26.                        matrix[0][j]=0;
  27.                        matrix[i][0]=0;
  28.                    }
  29.                }
  30.            }
  31.            //在遍历一次完成置0
  32.            for(int i=1;i<matrix.size();i++)
  33.            {
  34.                for(int j=1;j<matrix[0].size();j++)
  35.                {
  36.                    if(matrix[0][j]==0||matrix[i][0]==0)
  37.                    //对应第0行的位置和第一列的位置
  38.                    //只要有一个为0就说明这个位置需要被置为0；
  39.                    {
  40.                        matrix[i][j]=0;
  41.                    }
  42.                }
  43.            }
  44.         //单独判断第一行和第一列是否需要置0
  45.         if(isrow)//说明第0行需要置0
  46.         {
  47.            for(int i=0;i<matrix[0].size();i++)
  48.            {
  49.                matrix[0][i]=0;
  50.            }
  51.         }
  52.         if(iscol)//说明第一列需要置0
  53.         {
  54.           for(int i=0;i<matrix.size();i++)
  55.            {
  56.                 matrix[i][0]=0;
  57.            }
  58.         }
  59.         //处理结束
  60.     }
  62. };

六 .有序矩阵中第k小的数

378. 有序矩阵中第 K 小的元素 - 力扣（LeetCode） (leetcode-cn.com)

题目描述：

解题思路：

思路非常简单：

1.找出二维矩阵中最小的数 left，最大的数 right，那么第 k 小的数必定在 left ~ right 之间mid=(left+right)/2；在二维矩阵中寻找小于等于 mid 的元素个数 count.
2.若这个 count 小于 k，表明第 k 小的数在右半部分且不包含 mid，即 leftd=mid+1, right=right，又保证了第 k小的数在 left ~ right之间
3.若这个 count大于 k，表明第 k 小的数在左半部分且可能包含 mid，即left=left, right=mid，又保证了第 k 小的数在 left ~right 之间
4.因为每次循环中都保证了第 k小的数在 left~ right 之间，当 left==right 时，第 k 小的数即被找出，等于 right

对应代码：

  1. class Solution {
  2. public:
  3.        struct Info
  4.        {
  5.            Info(int n,int cnt)
  6.            {
  7.                near=n;
  8.               num=cnt;
  9.            }
  10.            int near;
  11.            int num;
  12.        };
  13.     int kthSmallest(vector<vector<int>>& matrix, int k) {
  14.         int n=matrix.size();
  15.          int left=matrix[0][0];
  16.          int right=matrix[n-1][n-1];
  17.          int ans=0;
  18.         while(left<=right)
  19.         {
  20.             int mid=(left+right)/2;//取中点二分
  21.             Info* ret=getLessEqualNum(matrix,mid);//看一下小于等于mid的有多少个
  22.             if(ret->num<k)//如果小于k说明二分的中点小了
  23.             {
  24.                 left=mid+1;
  25.             }
  26.             else{//大于等于更新ans；
  27.                 right=mid-1;
  28.                 ans=ret->near;
  29.             }
  30.         }
  31.         return ans;//返回ans
  32.     }
  33.     Info*getLessEqualNum(vector<vector<int>>&matrix,int val)
  34.     {
  35.         int m=0;
  36.         int n=matrix[0].size()-1;
  37.         int num=0;
  38.         int near=INT_MIN;//记录小于等于val离val最近的数
  39.         while(m<matrix.size()&&n>=0)
  40.         {
  41.             if(matrix[m][n]<=val)
  42.             {
  43.               num+=n+1;//把小于val的个数加起来
  44.               near=max(near,matrix[m][n]);//更新near
  45.               m++;
  46.             }
  47.             else
  48.             {
  49.                 n--;
  50.             }
  51.         }
  52.         return new Info(near,num);//返回结果
  53.     }
  54. };

版权说明 : 本文为转载文章, 版权归原作者所有 版权申明

原文链接 : https://blog.csdn.net/qq_56999918/article/details/123790380

内容来源于网络，如有侵权，请联系作者删除！

c++

相关文章

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新文章

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com